Hash Map

Question 1

Properties of Hash Maps

Answer 1

Not sorted
Unique keys

Question 2

Hash Map time complexity

Answer 2

Search, insert, delete all O(1)
Building a Hash Map is O(n)

Question 3

Time complexity vs others

Answer 3

Tree Map is O(logn) for insert/delete while Hash Map is O(1).
Tree Map is O(n) for search while Hash Map is O(1)
Sorted array is O(n) for insert/delete and O(logn) for search.

Question 4

Hash Map implementation

Answer 4

Backed by an array. Array indices are computed by hashing the keys. Hashing generates an integer based on the key. Modding(%) this integer by the size of the array produces an index that is guaranteed to be in-bounds. Collisions can occur and can be mitigated in a variety of ways including increasing the size of the array, chaining (storing a linked list of k/v pairs in under one key), and open indexing (putting it in the next open index).