Hardware Meetup - Sputnik, 24. october 2019
Hash tables
... the 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
Let's fill in the data...
What is a hash table
Sometimes also called associative array or dictionary. It is a data structure used to map key into values
data["Yoda"] gives us all the information stored for Yoda.
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 memory is accessible by addressing the data numerically.
e.g.: Accessing the item at memory location data[0] yields name of the person Yoda and person's phone number: (01)123-1234
Finding phone number of Darth requires linear search through the array, which is not efficient.
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 multitude of ways:
- Closed addressing (chaining)
- Open addressing (linear probing) (million ways how to do it)
- using alternate hash functions (million ways how to do it)
- Resize array ;) (not a scientific way to do it)
Closed addressing
|
data[0] data[1] data[2] data[3] data[4] data[5] data[6] data[7] data[8] data[9] data[10] data[11] data[12] data[13] |
Open addressing
Hash function properties
- Hash function should minimize collisions
- Uniformly distribute hash values
- Are easy to calculate