Lecture 13:
Hash Tables
Data Structures So Far
| Insertion | Retrieval | Deletion | Restriction |
Sorted Array | | | | |
Sorted Linked list | | | | |
Stack | | | | |
Queue | | | | |
Binary Search Tree | | | | |
Hash Table | | | | |
O(N)
O(N)
O(1)
O(log N)
O(N)
O(1)
O(N)
O(N)
O(1)
O(1)
O(log N)
O(1)
O(1)
O(log N)
O(1)
O(1)
O(log N)
O(1)
LIFO
FIFO
(if balanced)
Needed for applications that need radically fast operations:
2
Data Indexed Arrays
3
Data Indexed Arrays
Index | [0] | [1] | [2] | [3] |
Value | 2 | 5 | 9 | 10 |
Index | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
Value | F | F | T | F | F | T | F | F | F | T | T |
4
Data Indexed Arrays
Index | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
Value | F | F | F | F | F | F | F | F | F | F | F |
di_array = DataIndexedArray()
di_array.insert(3)
di_array.insert(6)
di_array.delete(3)
T
T
5
Data Indexed Arrays
di_array.insert(“ewha")
di_array.insert(21057381)
😨
😵
6
Strings in Data Indexed Arrays
7
Large Numbers in Data Indexed Arrays
Index | [0] | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | … | [999] |
Value | F | F | F | F | F | F | F | F | F | … | F |
di_array.insert(21057381)
8
Hash Tables
9
Hash Table
Given a key, a function (called hash function) determines where to locate it.
→ As long as this function can compute the address in O(1),� insertion / retrieval / deletion can be still within O(1).
Input range: the data domain�(e.g., string, arbitrarily large integer)
Address calculator should output an integer between 0 and table_size - 1.
10
Hash Functions
Hmm, then what should we do if two different keys coincidently map to the same address?
Modulo operator (%)
x % y is the remainder when we divide x by y.
11
Collision
12
Collision Resolution
Open Addressing
4567
Let’s find another place to put it.
Separate chaining
4567
7597
Let’s put it there together with the existing one(s).
Example: According to our hash function, 4567 needs to be located at [22], but it is already occupied 😨.
13
Open Addressing
14
Open Addressing
15
Open Addressing
h0(58)
h0(14)
h0(91)
58
91
14
h1(14)
h1(91)
16
Separate Chaining
17
Separate Chaining
18
Performance of a Hash Table
19
Efficiency of Hashing
When the load factor is low, hash table achieves ≈O(1), regardless of the collision resolution method.
20
How to Decide the Table Size (M)
21
Resizing Example
0
1
2
3
4
values
index
5
6
7
8
9
M=5
N=0
α=0
0
1
2
3
4
values
index
M=5
N=1
α=0.2
M=5
N=2
α=0.4
M=5
N=3
α=0.6
M=5
N=4
α=0.8
M=5
N=5
α=1.0
M=5
N=6
α=1.2
M=5
N=7
α=1.4
M=5
N=8
α=1.6
Resizing!
Redistributing all items!
M=10
N=8
α=0.8
22
Time Complexity of Resizing
23
Implementations
24
Python Dictionary
>>> tel = {'jerry': 1086, 'jose': 8249}
>>> tel[‘soo'] = 4127
>>> tel
{'jerry': 1086, 'jose': 8249, 'soo': 5564}
>>> tel['jose']
8249
>>> del tel['jerry']
>>> tel['shawn'] = 8080
>>> tel
{'jose': 8249, ‘soo': 5564, 'shawn': 8080}
>>> list(tel)
['jose', ‘soo', 'shawn']
>>> sorted(tel)
['shawn', ‘soo', 'jose']
>>> 'jinri' in tel
False
>>> 'jeongwoo' not in tel
True
Insertion
Retrieval
Deletion
25
Python Set
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a
{'a', 'r', 'b', 'c', 'd'}
>>> a - b
{'r', 'd', 'b'}
>>> a | b
{'a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'}
>>> a & b
{'a', 'c'}
>>> a ^ b
{'r', 'd', 'b', 'm', 'z', 'l'}
Unique letters in a
Set difference
Set OR
Set AND
Set XOR
26
Applications of Hash Tables�(Homework)
27
Homework 1
28
Homework 2 - Smallest Missing Integer
Examples:
# TODO(students): implement this!
def smallest_missing_pos_int(self, list):
for each item in the list:
insert into a hash table (hastset)
for i = 1, 2, 3, ...:
if the hash table contains i: keep going
else: return i
Note: think about how many times we should iterate here.
29
Homework 3
30
Homework 4
31
Homework 5
32