Authored by Tony Feng
Created on March 26th, 2022
Last Modified on March 26th, 2022
Understanding Hash Tables
Main Concepts
- Hash Table stores data in an associative manner.
- In programming languages, each key is assigned to a memory address by a hash function. The key-value pair is stored in this memory address.
- Hashing is a technique to convert a range of key values into a range of indexes of an array.
- Collision occur when two pieces of data in a hash table share the same hash value. Collisions are pretty difficult to avoid and are bound to happen, so the key to a good hash function is collision resolution. (Linked list could be a good solution.)
Main Characteristics
- In a hash table, data is stored using a key-value storage method.
- Access of data becomes very fast if we know the index of the desired data.
Operations
- Search - O(1)
- If hash collision happens, O(K), where K is number of collisions.
- Insert - O(1)
- Delete - O(1)
Hash Table Implementation in Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
# Create a hash table by Dictionary
D = {}
# Add an element - O(1)
D[1], D[2], D[3] = "a", "b", "d"
# Update an element - O(1)
D[3] = "c"
# Remove an element - O(1)
D.pop(1) # arg is the key
# del D[1]
# Get the value - O(1)
D[2]
# Check if the key exists - O(1)
b in D
# Get the length of the hash table
len(D)
# Traverse
my_dict={'Dave' : '001' , 'Ava': '002' , 'Joe': '003'}
for k in my_dict:
print(k) #prints the keys
for v in my_dict.values():
print(v) #prints values
for k,v in my_dict.items():
print(k, ":" , v) #prints keys and values
|
Hash Table Implementation in Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
// Create
HashMap<Integer, String> m = new HashMap<>();
// Add - O(1)
m.put(1, "alpha");
m.put(2, "b");
m.put(3, "c");
// Update an element - O(1)
m.put(1, "a");
// Remove an element - O(1)
m.remove(1); // arg is the key
// Get the value - O(1)
String tmp = m.get(2); // arg is the key
// Check if the key exists - O(1)
Boolean check = m.containsKey(2);
// Get the length of the hash table
int s = m.size()
|
Reference