Hash Times

Subject: Hash Times
From: Matthew Cary (cary@cs.washington.edu)
Date: Fri May 03 2002 - 10:39:02 PDT

• sorted by: [ date ] [ thread ] [ subject ] [ author ]
• Next message: Matthew Cary: "lecture 12 bug"
• Previous message: Kevin Chan: "Remove code"

Here is a handy reference sheet of the expected time to hash; a = load
factor,
  S = S(a) = expected successful search on table w/ load a
  U = U(a) = expected unsuccessful " " "

Seperate Chaining:

S = 2+(a/2)
U = 1+a

Open Addressing, Sequential Probing

S = (1/2)(1+1/(1-a))
U = (1/2)(1+1/(1-a)^2)

Open Addressing, Double Hashing

S = (1/a)ln (1/(1-a))
U = 1/(1-a)

I do not expect you to memorize the Open Addressing formulas. In an exam
situtation, if I ask you to do calculations on open addressing hash times,
I will give you the formulas.

• Next message: Matthew Cary: "lecture 12 bug"
• Previous message: Kevin Chan: "Remove code"

This archive was generated by hypermail 2b25 : Fri May 03 2002 - 10:39:23 PDT