Hardware Meetup - Sputnik, 24. October 2019
Hash tables
... the basic background of their implementations.
Samo Penič
About me...
- phD in Electrical engineering
- working at the Faculty of electrical engineering, teaching fundamentals of EM fields
- promoting open source since... ever?
- hobby programmer
What is a hash table
Sometimes also called associative array or dictionary. It is a data structure used to map key into values
phone_number["Yoda"]
stores and returns us the information stored for variable, object, ...
It is widely used to build things such us dictionaries, telephone books, book indexes, ...
Hash table provide Insertion, Deletion and Retreival in constant time!
However...
The computer memory is accessible by addressing the data numerically.
e.g.: Accessing the item at memory location phone[0] yields name Yoda and his phone number: (01)321-4321 (order reversed it is)
Finding phone number of Darth requires linear search through the array, which is not efficient.
Building a phonebook...
Mapping key to index
... is performed by so called hash functions. It can be as simple as sum(ascii_code[i]) % array_size
Let's try it out for our phone directory (array_size=13):
Collisions!
They will occur. The probability depends on Load factor (LF=number_of_items/array_size)
We can cope with collisions in different of ways:
- Closed addressing (chaining)
- Open addressing (linear probing)
- using alternate hash functions
- Resize the array ;)
Closed addressing
|
phone[0] phone[1] phone[2] phone[3] phone[4] phone[5] phone[6] phone[7] phone[8] phone[9] phone[10] phone[11] phone[12] phone[13] |
Open addressing
Hash function has to...
- minimize collisions
- uniformly distribute hash values
- be easy to calculate
Python dictionaries
Python relys heavily on dictionaries, so it is important they are efficient. Uses open addressing multihash to minimize collisions.
table = [None] * n;
for hash, key, value in entries:
perturb = hash
i = hash % n
while table[i] is not None:
#collision
i = (5 * i * perturb + 1) % n
perturb >>= 5
table[i] = (key, value)
See talk: Raymond Hettinger -- Modern dictionaries (SF Python 2006)
Hash tables in firmware
- Hash tables have average time complexity around O(1) for I,L,D
- Do not resize tables - plan in advance
- Use the power of prime numbers
- Storing pointers of data in hash is not a bad idea (!)
- to save memory, when data is large
- to get ordered dict if needed