Hash Table

Question 1

What is a Hash Table?

Answer 1

A hash table (commonly referred to as hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values.

Question 2

How do hash tables work?

Answer 2

A hash table uses a hash function on an element to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

Question 3

What is hashing?

Answer 3

Hashing is the most common example of a space-time tradeoff. Instead of linearly searching an array every time to determine if an element is present, which takes O(n) time, we can traverse the array once and hash all the elements into a hash table.

Question 4

Separate chaining

Answer 4

A linked list is used for each value, so that it stores all the collided items.

Question 5

Open addressing

Answer 5

All entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found.

Question 6

Access

Answer 6

Access N/A Accessing not possible as the hash code is not known

Question 7

Search
Insert
Remove

Answer 7

Search O(1)*
Insert O(1)*
Remove O(1)*