This section will only cover non-crypto hash
- Google CityHash
- Google FarmHash
- 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
- Extendible Hashing: use
trieto identify the hash table. Split the trie node if its hash table is full, in this case onlyrehash of this node table rather than all entire tables is required.
- Linear Hashing: split bucket iteratively whenever an overflow detected