Advanced Programming I Lecture Notes

3 April 2007 • Hashing Basics

Outline

• Arrays again.

• Hash tables.

• Hash functions.

• Hash table ADTs.

• Open-address hashing.

  • Collisions, linear and quadratic probing, double hashing.

• Chaining

Arrays Again

• Arrays provide O(1)-time access and no-overhead storage.

• However, finding values in an array can be expensive.

  • It can take O(log n) or O(n).

  • O(log n) search makes value access more expensive.

• There's no relation between a value and its index.

An Idea

• Suppose a value could be uniquely associated with an index.

• Then searching would also be constant time.

  • Is "joe" around?

  • Oh, "joe"'s the same as 2.

  • a[2] == "joe".

• This is the basic idea behind hash tables.

Hash Table Properties

• A hash table is an array-like data structure for storing and retrieving data.

• Constant-time data access and search.

  • And the constant should be close to one.

• Other array-like properties may be sacrificed for the constant-time operations.

  • Ordered sequential access, for example.

• Even so, constant-time operations may be elusive and expensive to achieve.

Hash Table Components

• A hash table has two parts:

  1. A hash function to map values to indices.

  2. A scatter table to map indices to values.

• Both are sensitive to value characteristics.

  • Hash functions to the content of values.

  • Scatter tables to the number of values.

• These sensitivities complicate hash tables.

Hash Functions

• A record is identified with one or more fields collectively called the key.

• A hash function maps keys into a smaller range of hash indices (positive integers).

  • Smaller relative to the key set.

• The hash function may be supplied by the hash-table ADT, or by the ADT's client, or by both.

Hash-Function Properties.

• A hash function is a function.

  • That is, if k₁ = k₂, then h(k₁) = h(k₂).

• A good hash function is one that

  • produces unpredictable hash indices (is random).

  • produces widely and evenly separated hash indices (is uniform).

  • is fast to compute (is efficient).

Hash-Function Properties..

• A hash function maps a large key set to a much smaller index set.

  • All possible strings into 32-bit integers.

• By the pigeon-hole principle, many values will be mapped into the same hash index.

  • Dealing with this is a main concern of hash-table ADTs and their clients.

• Other properties may be important on occasion.

Finding Hash Functions

• A key can be interpreted as a large binary number.

  • Use multi-precision arithmetic to chop it down.

• Structured keys lead to recursive hash functions.

  • Use a hash function on each component, then hash together all the hash indices.

Hash Table ADTs

• 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.

  • For the moment, assume the hash function exists.

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

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

Open-Address Hashing

• Implementing a scatter table with an array results in open-address hashing.

• The array is arranged in B buckets, each containing b array elements.

  

  • B and b are parameters to the create() operator.

  • Assume B = N and b = 1.

Collisions

• Two different values collide when they produce the same hash index.

  • Collisions are guaranteed.

• How do you know when an array element is occupied?

  • The ADT includes an N-element bit vector to keep track.

  • Or have an otherwise unused sentinel value.

Handling Collisions

• Handling collisions involves storing the new value elsewhere in the hash table.

  If h(k) is full, examine (h(k) + 1) % N, then (h(k) + 2) % N, then ..., (h(k) + N - 1) % N.

• This is linear probing.

Linear-Probing Example

Handling Clustering

• Linear probing leads to clustering.

  

• Quadratic probing spreads out successive probes.

  • (h(k) + i²) % N for 0 ≤ i < N.

Quadratic-Probing Example

Double Hashing

• Quadratic probing is still predictable, leading to secondary clustering.

  • Although the clusters are smaller.

• Double hashing (rehashing or quotient-offset hashing) uses a second hash function to add unpredictability.

  • Visit (h₁(k) + u*i) % N
    for 0 ≤ i < N and u = h₂(k).

Double-Hashing Example

Problems

• Scatter tables under open addressing

  • may get full.

  • may have long (O(n)) searches due to clustering.

Chaining

• Let each bucket in the scatter table be the head of a linked list.

• Elements hashing to a bucket are added to the associated list.

  • No more clustering.

  • The table can hold an arbitrary number of elements.

    • At increasingly bad (O(n)) performance.

• This technique is known as chaining.

Chaining Example

Coalescing

• Open addressing imposes clustering costs; chaining imposes storage-management costs.

• Split the difference by reserving some buckets as chain links.

  • Chain management is cheap and fast.

  • Collisions don't cause clustering.

• The result is coalesced hashing.

Coalescing Implemented

• The number of overflow buckets is a design or run-time parameter.

• A free list chains unused overflow buckets.

  • Or use the occupied bit vector at linear cost.

Implementing Hash Table ADTs

• Most dictionary-style hash-table ADTs have straightforward implementations.

  • Dictionaries do add(), delete(), and find().

  • Few or no extra maintenance operations.

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 not 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)

Implementation Details

• Two important implementation details are

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

  2. the hash functions.

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.

Load Factor

• Hash table size can be expressed as the load factor (or just load):

  α = elements stored/total slots

• Load is a measure of chain length.

  • The open-addressing interpretation is “similar”.

• Hash-table search has average-case performance proportional to 1 + α.

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 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.

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.

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.

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.

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(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.

Points to Remember

• Hash tables are probabilistic, general arrays.

  • Betting on constant-time search.

• Table size and hash function have data-sensitive performance.

• Hash functions: don't trust and verify.

  • Eyeball reject, mathematically accept.

• Hashed addressing is highly exploitable.

References

• Hashing, Section 6.4 in The Art of Computer Programming, Vol. 3: Sorting and Searching by Donald Knuth, Addison-Wesley, 1973.

• Hash Tables by Pat Morin, Chapter 9 in Handbook of Data Structures and Algorithms, edited by Dinesh Metha and Sartaj Sahni, Chapman & Hall/CRC, 2005.

• Hashing, Chapter 9 in Algorithms by Robert Sedgewick, Addison-Wesley, 1983.