Hashing

Tom Kelliher, CS23

May 8, 1996

The general idea of hashing:

Hash Functions

A hash function, h(), takes an arbitrary integer, j, and maps into an integer in a specified range, usually 0 to p-1 where p is prime.

h() should have these properties:

  1. Easy and fast to compute.
  2. Place data evenly throughout the table.

Sampler of h()'s ( Always possible to convert a key to an integer/integers):

  1. Selecting digits --- which digits?
  2. Folding --- add digits.
  3. Modulo Arithmetic.

Closed Hashing

Some probe sequences:

  1. Linear probing.
  2. Quadratic probing.
  3. Double hashing --- initial probe position, increment. Table size, increment should be relatively prime.

Open Hashing

(Separate chaining.)

Hash table is array of pointers (array of linked lists.)

Efficiency of Hashing

Inefficiency for Ordered Operations

Hashing randomizes the keys.

Poor performance for retrieving:



Thomas P. Kelliher
Tue May 7 13:13:00 EDT 1996
Tom Kelliher