meerkatboss / algopractice6

Hash Table Research

Introduction

This research focuses on performance of various implementations of hash table and hash functions.

The following hash functions are considered:

• For integers:
  • Identity function
  • Multiplicative hash
• For floating-point numbers:
  • Round to nearest integer
  • Interpret IEEE-754 floating point number representation as unsigned integer
• For strings:
  • Length of string
  • Sum of characters
  • Polynomial hash
  • crc64 hash

The following hash table types are considered:

• Hash table with closed addressing (with linked list chaining)
• Hash table with open addressing

Results

Hash functions

Tests for various hash functions yielded the following results:

On uniformly-distributed inputs all functions behave similarly, except for hash_string_length which is limited by maximum length of generated string.

However, hash_string_sum_char will behave poorly on larger table sizes, as it will produce normal distribution of bucket sizes according to Central Limit Theorem.

Hash tables

When generating random queries for hash tables, the following results were obtained:

On this data, hash table with open addressing performs about twice as fast as with closed one.

When increasing the probability of insertion operation to 50%, the results were following:

Now the hash table with open addressing is almost three times faster than another implementation.

Conclusions

Hash functions

On uniform data nearly all function will behave efficiently, as the results show. However, on a more structured data the results might change. For example, if the range of input integers or floating-point numbers is smaller than the size of hash table, the identity and round functions will behave inefficiently, similar to the performance of hash_str_length.

hash_str_sum_char behaves efficiently on relatively small hash tables containing long words, but it will inevitably suffer from the effects of Central Limit Theorem in other cases.

Hash tables

The hash table with open addressing performs much faster than the table with closed addressing due to increased code locality and less frequent memory allocations. This effect becomes more noticeable with larger sample sizes, as spikes in execution time, indicating the occurrence of rehash, are higher for the table with closed addressing. This indicates that the longer insertion times are affecting the performance of a rehash, decreasing the overall hash table performance even further.