Computer Algorithms II Lecture Notes

16 September 2008 • Hashing Basics

Outline

• Arrays

• Hash tables.

  • Hash table ADTs.

  • Open-address hashing.

    • Collisions and probing.

  • Chaining

• Performance

Arrays

• 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

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

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

Open-Addressing Problems

• Scatter tables under open addressing

  • may get full.

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

• Clusters are imprecise.

  • Keys in a cluster likely have different index values.

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.

Performance

• Analytic results are difficult and assumption ridden.

  • Worst-case is bad; average case is inspiring.

  • Similar to quicksort.

• Analysis is performed in terms of table accesses (probes).

• Fortunately, analysis supports intuition.

  • Don’t let the table get too full.

Load Factor

• Hash-table occupancy is a parameter in the analysis and results.

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

Chaining Analysis

• Unsuccessful searches take Θ(1 + α).

  

• Successful searches take Θ(1 + α).

  

• Uniform distribution, no deletions.

Linear Open Analysis

• An unsuccessful search uses 1/(1 - α) probes on average.

  

• An successful search uses (1/α)(1 + ln(1/(1 - α))) probes on average.

Other Operations

• Other operations are based on search costs.

  • Insert: the cost of a search plus the cast of an insert.

  • Delete: the cost of a search plus the cost of a delete.

• More detailed analysis under more realistic assumptions is hard.

Summary

• Hash tables are probabilistic, general arrays.

  • Betting on constant-time search.

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

  • Good performance requires eternal vigilance.

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

• Hash Tables, Section 12.7 in ADTs, Data Structures, and Problem Solving with C++, second edition, by Larry Nyhoff, Prentice Hall, 2005.

This page last modified on 12 September 2008.