A hash table is a form of key, value table with the goal to immediately find an item.
A hashing function is used to calculate the position of an item in a hash table.
Implementation
class HashTable:
def __init__(self, size: int):
self.table = [None for x in range(size)]
self.size = size
def get(self, key: str):
return self.table[self.__hash__(key)]
def put(self, key: str, data: str):
self.table[self.__hash__(key)] = data
def __hash__(self, data: str):
tol = 0
for char in data:
tol += ord(char)
return tol % self.size
ht = HashTable(100)
ht.put("gurt", "yo")
ht.put("darragh", "hi")
ht.put("so", "tuff")
ht.put("tuff", "tuff x2")
print(ht.get("gurt"))
print(ht.get("darragh"))
print(ht.get("so"))
print(ht.get("tuff"))Hashing Function
One-way algorithm which produces a hashed result.
The hashing function is applied to an item to determine a hash value.
A good hashing function should:
- Be calculated quickly
- Result in minimal collisions
- Use minimal memory
Examples:
- MD5
- SHA512, SHA256, SHA128
Resolving Collisions
Linear Probing
Repeatedly checking the next space in a hash table until an empty position is found, iterating in a given interval.
Requires a linear search to be performed when inserting but also searching for the item.
Chaining
When it is possible for a multitude of items to be placed at the same position.
Examples:
- Overflow table
- Linked list
- Two-dimensional table
Usage
Applications
- File systems (file name → file path)
- Identifying keywords (token → token class, data type, etc.)
Operations
- Add
- Delete
- Retrieve