A hash table is a fundamental data structure in computer
science that can offer rapid storage and retrieval of data.
A leading implementation for string keys is the cacheconscious
array hash table. Although fast with strings,
there is currently no information in the research literature
on its performance with integer keys. More importantly,
we do not know how efficient an integer-based array hash
table is compared to other hash tables that are designed for
integers, such as bucketized cuckoo hashing. In this paper,
we explain how to efficiently implement an array hash table
for integers. We then demonstrate, through careful experimental
evaluations, which hash table, whether it be a
bucketized cuckoo hash table, an array hash table, or alternative
hash table schemes such as linear probing, offers
the best performance-with respect to time and space-
for maintaining a large dictionary of integers in-memory,
on a current cache-oriented processor. |
(from crpit.com)
