Hashing
Nishant Mehta Lectures 16 and 17
Warm-up puzzle
We have a deck of n distinct cards (where n is large) and repeatedly sample a card uniformly at random, with replacement. On average, how many cards do we need to draw before we see some card twice (that is, before we
Jhave repeated a card)? (a) !(n2)
(b) !(n) (c)!( n)
(d) !(log n) (e) !(1)
←
”
”
” IBirthday
Paradox
”
Dictionary
A dictionary is a data structure that contains key-value pairs
• •
Keys should be unique
Values can be anything and need not be unique
key t
be f.
could (k, v)
an
image
Dictionary – Operations
SEARCH – Need to specify key k
INSERT – Need to specify object x (obtain key via x.key) DELETE – Need to specify object x
•
We will see later why it is better to take as input x rather than x.key
Unordered list
Suppose that we use an unordered list (let’s make it a doubly linked list)
k3
k1
k6
k4
head
Operation
SEARCH(S, k) INSERT(S, x) DELETE(S, x)
iiext
I previous
Worst-case running time?
0(n) OCD
OCD
n elements
Ordered list
If we use an ordered list (in the form of an array), then searching is fast; other operations are slow
”
” ÷
“”””
O
”
”
÷: .
SEARCH(S, k) – binary search enables O(log n) INSERT(S, x) – O(n)
DELETE(S, x) – O(n)
10 16 19
7 12 15 20 35 39
3
Balanced binary search tree
Another strategy is to use a balanced binary search tree (e.g., red-black tree, AVL tree) nil[T]
26
17 41
14 21 30 47
10 16 19 23 28 38
23 28 38
(b)
7 12 15 20
35 39
3
red-black tree is either red or black, the children of a red node are both black, and every simple path
(c)
Figure 13.1 A red-black tree with black nodes darkened and red nodes shaded. Every node in a
SEARCH(S, k) – O(log n)
from a node to a descendant leaf contains the same number of black nodes. (a) Every leaf, shown
INSERT(S, x) – O(log n)
(b) The same red-black tree but with each NIL replaced by the single sentinel nil[T ], which is always
as a NIL, is black. Each non-NIL node is marked with its black-height; NIL’s have black-height 0.
black, and with black-heights omitted. The root’s parent is also the sentinel. (c) The same red-black
tree but with leaves and the root’s parent omitted entirely. We shall use this drawing style in the
DELETE(S, x) – O(log n)
remainder of this chapter.
Direct-address table
Suppose the keys are in a universe U = {0, 1, . . . , m 1} In a direct-address table, we create an array T of size m
(initialize all entries to NULL) Element with key k is stored in T [k ]
SEARCH(S,k): returnT[k] INSERT(S, x): T [x .key] = x DELETE(S, x): T [x .key] = NULL Space complexity? O Cml
Worst-case running time?
OCH
OCH OCH
Direct-address table – Example 1
Universe {0,1,…,9}
n = 4, with the 4 keys being: 2, 5, 8, 9
° I
1- I=
‘s
2 3
value
2
I
4 J
b
7- 8
9
T
I-5 –
‘s value I
F- Ttp
‘s
8 value
value
‘s
Direct-address table – Example 2
2h- I
Universe {0, 1, . . . ,•2n} where we have only n keys
→ ÷
1 – ←Y
II.
I
n
keys
n=7
storing
”
space
is
2 isahliution
r ⇒μy÷y
F-
.
r i
Hash tables
What if the universe is massive, but the set of keys that
will actually be used is much smaller? (n ⌧ |U| )
Then a direct-address table is really wasteful. Most entries of T will never be used!
Idea: Although |U| is massive, we’ll use a table of size m. How? We use a hash function h : U ! {0, 1, . . . , m 1}
m