hashtable.md

Hash Table

Hash table complexity: search, insert, delete

All: amortized O(1), worst O(n)

#complexity #hashtable

Hash table implementation

• Array of linked list
• Hash code function to give the array index

Resize the array when a threshold is reached

If extreme nonuniform distribution, could be replaced by array of BST

#hashtable