Computer Algorithms II Lecture Notes

23 September 2008 • Implementing Hash Tables

Outline

Hash table ADT. Hash functions. Scatter tables. Open addressing. Chaining Dynamic hash tables.

Hash Table ADTs

• A hash table implements an abstract set ADT.

• Start with the usual three operations: add(), delete(), and find().

• There will be others to come, particularly maintenance operations.

• There may or may not be traversal operations.

  • There definitely won't be ordered traversal operations.

ADT Implementation

• There are two parts: the hash function and the scatter table.

• The scatter table (hash table) stores values and maps hash indices to values.

• The scatter table is most naturally based on an array.

Implementation Details

• Two important implementation details are

  1. hash-table size (the value of B), and

  2. the hash functions.

Chained Operations

void add(key k)
  linked-list chain = table[hash(k)]
  if not chain.member(k)
    chain.add(k)

void delete(key k)
  linked-list chain = table[hash(k)]
  if chain.member(k)
    chain.delete(k)

bool find(key k)
  return table[hash(k)].member(k)

Open-Address Hash Tables

Open-address hash table delete is tricky. Use a bit map to mark cluster ends.

Private ADT Operations

• add(), delete(), and find() use the locate() private operation.

  bool locate(key k, int & hi)
    hi = hash(k)
    step = 1 or i2 or hash2(k)
    for i = 1 to B
      if not in-cluster[hi] return false
      if occupied[hi] and table[hi] == k 
        return true
      hi = (hi + step) mod B
    hi = -1
    return false

Public ADT Operations

void add(key k)
  if not locate(k, hi)
    if hi > -1
      table[hi] = k
      occupied[hi] = true
      in-cluster[hi] = true

void delete(key k)
  if locate(k, hi)
    occupied[hi] = false
    in-cluster[hi] = 
      in-cluster[hi + 1 mod B] and
      in-cluster[hi - 1 mod B]

bool find(key k)
  return locate(k, hi)

Hash Table Size

• Hash table size should be

  • large enough to avoid excessive collisions (and non constant access), and

  • small enough to avoid wasting space.

• Hash table size can be fixed at creation (static hash tables) or varied as use demands (dynamic hash tables).

  • Assume static hash tables for now.

Hash Function Issues

• Some important details for hash-function implementation include:

  1. How are they created?

  2. Who provides them?

  3. How good are they?

Hash Functions

• Hash functions fall into one of three classes based on value combination:

  • Multiplication based, division based, or bit-twiddling based.

  • There are also other techniques.

• Random-number generation is a closely-related area.

  • For implementations and evaluations.

Hash Function Sources

• Hash functions can be provided by the ADT, the ADT client or both.

  • There may be other sources, such as a language run-time or a VM.

• The client knows about the data; the ADT knows about the hash table.

  • Good hash functions needs to know about both.

Dual Hash Functions

• Not deciding is a good strategy: have the client and ADT each provide a hash function.

  • The final hash is h_A(h_C(k)).

• Each side can exploit its strengths without bothering the other side.

• The ADT can change its hash function without customer coordination.

Hash Function Mechanics

• A hash function maps arbitrary data (the key) into a small range of integers (the hash-table indexes).

• This can be divided into two steps:

  1. Reduce the key to an integer

  2. Reduce an integer to a hash-table index.

Keys To Integers

• The key-to-integer mapping is data dependent, but has the general form:

  • Treat the key as a sequence of n-byte values for n = 2ⁱ.

  • Use arithmetic to combine the values into a single value.

• There may be other techniques, such as use the key address.

Hashing by Bit Twiddling

• Create rp[], a random permutation of the 256 integers 0 to 255 (byte values).

• Given a sequence v[] of n byte values, hash v into a byte value h with

  byte hash(byte v[], unsigned n)
    byte h = rp[v[0]]
    for i = 1 to n - 1
      h = h xor rp[v[i]]
    return h
  

• Combining several values from hash() produces multi-byte hash values.

Hashing by Division

• This is the typical hash function.

  unsigned hash(unsigned k)
    return k mod B
  

  • B is the bucket count, and "should be prime."

• Linear congruential generators are a variation.

  unsigned hash(unsigned k)
    return (M*k + a) mod B
  

  • This is overkill, most likely.

Hashing by Multiplication

• Hashing by multiplication uses functions of the form

  unsigned hash(unsigned k)
    return floor(B*fraction(k*A))
  

  • A is any value and B need not be prime.

Comments

• Random-permutation hashing is fast, reliable, simple, and general purpose.

  • The key is generating a random permutation, which is easy.

• Multiplication- or division-based hashing is less fast, less reliable, less simple, and less general purpose than random-permutation hashing.

  • Real arithmetic is expensive, and getting the parameters correct is tricky.

Evaluating Hash Functions

• A good hash function should generate indices that are uniformly and randomly distributed over the buckets.

• There are mathematical (statistical) tests for evaluating randomness.

• A simpler alternative is to plot the hash function and look for patterns.

  • Patterns can indicate non-uniformity and non-randomness.

Bad Hash Example

Good Hash Example

A Good Hash?

• Maybe; probably not.

XOR Hashing

• Somebody told me that XOR (exclusive or) hashing was good.

  • Exclusive or: one or the other, but not both.

    XOR	0	1
    0	0	1
    1	1	0

• XOR bytes together, rather than adding or multiplying.

XOR Hashes

• (x*101 ^ y*97) % B.

Low-Order Bits

• Somebody told me that low-order bits tend to be less random than higher-order bits.

  • Fewer partial sums are involved.

  • Factors of 2 or 5.

• Get better results by throwing away some of the low-order bits.

Does It?

• (round(x*101)*round(y*97))/256 % B.

Does It?

• (round(x*101)*round(y*97))/2 % B.

Linear Congruential Hashing

• Use a random-number generator.

  unsigned point::random(double k)
    return (M*static_cast<int>(k*11) + a) % s
  
  unsigned point::hash()
    return random(x)*random(y);
  
  template <typename T>
  unsigned hash_table(const T & e)
    return e.hash() % size
  

Linear Congruential Results

• M = 25173, a = 13849, s = 65536.

Hash-Table Size

• Hash-table size, and load factor, is crucial for good performance.

• Unfortunately

  • Hash tables are based on static arrays.

  • There may be no useful bound on the number of possible keys.

• For general utility hash tables have to overcome these problems.

The Current State

• Open-address hash tables are static.

• Chaining hash tables are dynamic, but at a performance cost.

  • And don'f forget that "dynamic" means growing and shrinking.

• Never the less, rehashing is one way to get dynamic hash tables.

  • Up to a point.

Dynamic Hash Tables

• A dynamic (or extensible) hash table automatically reconfigures to maintain a given time-space trade-off.

  • The ADT client sets the parameters.

  • The client may explicitly request a resize.

Dynamics In Use

• Databases use dynamic hash tables.

  • Minimizing disk I-O is important.

    • A higher tolerance for poorer hash performance.

  • Relatively small number of buckets (B) of relatively large size (b).

• The STL unordered associated containers are dynamic hash tables.

Dynamic Components

• The important parts of a dynamic-hashing scheme are

  • Addressing and hashing.

  • Storage

  • Growing and shrinking.

Addressing

• As the hash-table size changes, so does the hash function.

• A new hash function forces a complete rehash of the table.

  • Expensive and doesn't amortize well.

• The hashing scheme should adapt but manintain consistency with previous hashes.

Tree-Based Addressing

• Consider storing records in a binary tree.

  	One record can be stored with no hash values at all.
  	Two records require discrimination on (at least) one bit.

• The choice of left-most or right-most bits doesn't matter as long as it's used consistently.

Tree-Based Collisions

When two records collide, use more hash-index bits.

• Choose the smallest unique prefix (or suffix) of the original hash value.

  • This handles expansion and contraction.

Big Buckets

• Excessive expansion and contraction is inefficient.

  • And what about unbalanced trees?

  Large-capacity buckets help smooth out these variations. The bucket size b is a knob for tuning the time-space trade-off.

Storage

• So much for addressing and hashing.

  • Addressing and hashing.

  • Storage

  • Growing and shrinking.

• What about storage?

  • Look to the trees.

Directories

• Collapse the tree into an array called the directory

  

• This is directory-based dynamic hashing.

No Directories

• Directories add a level of indirection, reducing performance.

  • Hash directly to the appropriate bucket.

  This is the directoryless dynamic hashing. It trades space for time.

• Lots of cheap storage may make this trade-off sensible.

Growing and Shrinking

• And finally, growing and shrinking.

  • Addressing and hashing.

  • Storage

  • Growing and shrinking.

• Overflow handling can be used to delay expensive size changes.

  • But the load factor may get too extreme.

Directory Growth

• Growing a directory hash is similar to the special case described previously.

  

• Directory reconfiguration is relatively time and space efficient.

Directoryless Growth

Shrinking

• A per-bucket load factor of less than 0.5 suggests it's time to shrink.

  • If space is tight, contraction may be into overflow buckets.

Summary

References

• Dynamic Hashing Schemes by Richard Enbody and David Du, Computing Surveys, June 1988.

• Hashing for Dynamic and Static Internal Tables by Ted Lewis and Curtis Cook, IEEE Computer, October 1988.

• The Design and Implementation of Dynamic Hashing for Sets and Tables in Icon by William Griswold and Gregg Townsend, Software—Practice and Experience, April 1993.

Credits

• Hash in the Pan by mhaithaca, BY NC SA CC licensed.