0x311 Search

Hash

This section will only cover non-crypto hash

Hash Function

  • MurmurHash
  • Google CityHash
  • Google FarmHash
  • CLHash
  • FNV hash: 34bit to 1024bit, simple and fast, one round of FNA-1 consists of only prime multiplication and xor

Open Addressing Hash Scheme

  • Linear Probe Hashing: resolve collisions by linearly searching for the next free slot
  • Robin Hood Hashing: variant of linear probe hashing. Allow poor keys to steal position from rich keys. try to reduce the std of probing.
  • Cuckoo Hashing: prepare two hash tables

Dynamic Rehashing

  • Extendible Hashing: use trie to identify the hash table. Split the trie node if its hash table is full, in this case only rehash of this node table rather than all entire tables is required.
  • Linear Hashing: split bucket iteratively whenever an overflow detected