Tag VIII. Hash Table

1. 实现：an array of linked list and hash table function.

1) compute the key's hash code and different key may have same hash code.

2) map the hash code to an index in an array. Two different code may map to same index.

3) use a linked list to store the key and value since the collisions.

假设 lookup time is O(1)

2. 第二种实现：balanced binary search tree -- lookup time O(log N) -- less space

3. Hashing特别高效，search, insert, delete都是O(1)的时间。可以用hashing 实现map/set

4. java.util.Map的接口，三种具体实现：HashMap, LinkedHashMap, TreeMap(Red-Black Tree)

5. The function that maps a key to an index in the hash table is called a hash function

6. Handle collision: Open addressing -- linear probing, quadratic probing, and double hashing.

Separate chaining.