CSCE 434 Lecture 25

« previous | Monday, October 21, 2013 | next »

Lecture Slides

Symbol Table

Requirements:

• fast access (esp. search)
• compactness

Implementations:

• Unordered List (slow search)
• Ordered List (slow insertion)
• Binary Tree ($O(\log n)$ everything)
• Hash Table ($O(1)$ everything)

Hash Table

Size should be prime

Hashing function $h(n)$ should

• depend only on $n$
• be cheap to compute
• be uniform (each output is equally likely)
• randomize order (similar inputs do not map to similar values)

Collisions: Inevitable unless input is known in advance. (all ops are modulo $m$).

• Add the hash: $h(n)$, $2h(n)$, $3h(n)$, ...
• Secondary Hash: $h(n)$, $h(n)+h^{\prime }(n)$, $h(n)+2h^{\prime }(n)$, ...