Data Structures and Algorithms Lecture Notes

25 April 2011 • Hashing Basics

---

Outline

• Arrays
• Hash tables.
  • Hash table data types.
  • 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 data type, or by the data type’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 data typess 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 Data Types

• A hash table implements an Abstract-Set data type.
• 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 data type 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.

Open Hashing 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 2010 April 22.