Hash Table

1. 定义

• m为size, n为数组坑位。坑位为链表时, 时间复杂度是O(log(m)),坑位为平衡树时时间复杂度O(log(m/n))。如果所有元素在同一个坑位里面，时间复杂度为O(n)
• 设计hash时要考虑一致性(key和value)，高效性和均匀性
• 容量为质数(P)，用于减少hash冲突的概率，增加坑位

2. 目标

• 空间换时间
• 失去了数据的顺序性

3. 基本操作

get, put, remove

4.扩展

rehashing, open addressing, seperate chaining

code

https://github.com/nyannko/leetcode-java/blob/master/src/ds/hashtable/MyHashMap.java