Hash Tables

Question 1

Basics

Answer 1

• It’s a very flexible and performant key-value store
• Are built on top of dynamic arrays. A hash function is used to transform the key (a String or any object type) into an array index
• Searching, inserting, and removing operations:
  * Are constant operations on average
  * On collisions they become linear operations
  * Because on actual implementations the hashing functions minimize the collisions, the O(1) is always considered

Question 2

Collisions

Answer 2

• When for two different keys there is the same index value after executing the hash function
• A linked list is created within the same index to store all keys with the same hash function execution value
• Linked Lists support resizing (size down / up) when the underlying array reached its capacity to avoid collisions. It happens very infrequently

Question 3

Space-time complexities

Answer 3

• Looking up a key, inserting, and removing operations depend on the collisions found. It’s O(1) T in the average case, O(N) T in the worst case, O(1) S
• Initializing a hash table is a linear operation. It’s O(N) ST
• Copying a hash table is a linear operation. It’s O(N) ST