Redesigning the string hash table, burst trie, and BST to exploit cache

Abstract

A key decision when developing in-memory computing applications is choice of a mechanism to store and retrieve strings. Themost efficient current data structures for this task are the hash table withmove-to-front chains and the burst trie, both of which use linked lists as a substructure, and variants of binary search tree. These data structures are computationally efficient, but typical implementations use large numbers of nodes and pointers to manage strings, which is not efficient in use of cache. In this article, we explore two alternatives to the standard representation: the simple expedient of including the string in its node, and, for linked lists, the more drastic step of replacing e..