Murmur3 and Lookup3 Hash Introduction - 2023.2 English

Vitis Libraries

Release Date
2023.2 English

For different types of data, some are highly random and the others are high-latitude graph structures. These make it difficult to find a common hash function. Even for a specific type of data, a better hash function is not an easy one. The hash function can be selected from two perspectives:

  1. Data distribution: One kind of measurement is to consider whether a hash function can distribute the set of data very well. To perform this kind of analysis, you need to know the number of hash values for the collision. If linked list is used to process the collision, the average length of the linked list and the number of groups are the features to show the performance of hash function.
  2. The efficiency of the hash function: The other criterion to measure is the efficiency on which the hash function gets a hash value. In general, the computation complexity of hash function is assumed to be O(1), that is why the time complexity of searching data in the hash table is considered to be “comparable with an average of O(1)”. In other data structures, such as graphs (usually implemented as red-black trees), are considered as O(log n) complexity.

The Murmur3 and Lookup3 hash functions are called simple hash functions, and they are usually used for hashing string data. Unlike sha256, sha256 which are encrypted and not password-safe, they can directly generate key for an associative container, such as a hash table.