hash functions

• care about:
  • fast
  • low collision rate
• don’t want cryptographic or reversible hash (e.g. SHA-2)
• existing options:
  • CRC-64: used widely in networking for error detection
  • MurmurHash
  • Google: FarmHash
  • Facebook: XXHash
  • RapidHash

hash schemes

• categories:
  • open addressing: location of hashed key in the data structure can be anywhere
    • hashed value only indicates the “starting point”
    • schemes:
      • linear/quadratic/… probe
      • cuckoo hashing
  • separate chaining….
• storing entries:
  • fixed-length data: store data in place
  • variable length: store entries in a temporary table and store a “record id” in the hash table

linear probe

• single giant table of fixed-length slots
• resolve collisions by searching for the first next free slot
• load factor determines when the table is too full and needs resized
  • load factor = #active slots / #total slots
  • resizing: doubling and rehash entries
• deletes:
  • naively lookup and delete the target entry doesn’t work!
    • create holes in the table → make it hard for later lookup…
  • approaches:
    • move other entries after deletion:
      • this can be expensive because might need to move all other entries!
      • no DBMS does this!
    • tombstone: maintain a bitmap is indicate the entry is logically deleted
      • tombstone slots can be reused for new entries later
      • may need periodic garbage collection

cuckoo hashing

• hash table has multiple hash functions (usually 2??)
  • how many hash functions to use?
    • there is theoretical work that advises on the number of hash funcs to use for a given table size (# slots, …)
• insertion:
  • compute the N hash values with N hash functions, these correspond to N slots in the table
  • check if any of the N slots is free, if yes, put the entry to the slot
  • if no, then pick any of the N slot, evict the occupied entry and put the new entry there
  • now the problem is to insert the evicted entry → recurse!
  • cycle?
    • …
• lookup and deletion: O(1) because there is only 1 location the target entry is placed in
• slower than linear probing…
  • why?….

dynamic hash table

for static hash table, when we resize the table we need to rehash everything → dynamic hash table tries to avoid that