哈希表基本概念
维基百科比较清楚，可以参考。我觉得可能最好跟着打字一遍，比读一遍能理解更多，往往太多字，很容易放弃阅读，或者晕头了，而打字的过程中会字字阅读从而思考更多内容：https://zh.wikipedia.org/wiki/%E5%93%88%E5%B8%8C%E8%A1%A8
哈希表也叫散列表，是根据关键码值（key value）而直接访问在内存储存位置的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（Hash Function），存放记录的数组叫做哈希表（或散列表）。
- 若关键字为 k，则其值存放在 f(k) 的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系 f 为散列函数，这个思想建立的表为散列表。
- 对不同的关键字可能得到同一散列地址，即 k1 ≠ k2，而 f(k1) = f(k2)，这种现象称为冲突（Collsion）。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数 f(k) 和处理冲突的方法讲一组关键字映射到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种便称为散列表，这一映射过程称为散列造表或散列，所得的存储位置称为散列地址。
- 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此散列函数为均匀散列函数（Uniform Hash function），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。
工程实践
- 电话号码簿
- 用户信息表
- 缓存（LRU Cache）
- 键值对存储（Redis）
哈希函数 Hash Function
用来映射 key 存放到哈希表（数组）的位置，这个映射的函数叫做哈希函数。
- 直接定址法
- 取关键字或关键字的某个线性函数为散列地址。
- 即 hash(k) = k 或 hash(k) = a * k + b, 其中 a，b为常数
- 这种散列函数叫做自身函数
- 数字分析法
- 假设关键字是以 r 为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
- 平方取中法
- 取关键字平方后的中间几位为哈希地址。
- 通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此随机分布的关键字得到的哈希地址也是随机的。取的位处由表长决定。
- 折叠法
- 讲关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
- 随机数法
- 除留余数法
- 取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。
- hash(k) = k mod p, p <= m.
- 不仅可以关键字直接取模，也可在折叠法、平方取中法等运算之后取模。
- 对 p 的选择很重要，一般取素数或 m，若 p 选择不好，容易产生冲突。
哈希冲突 Hash Collisions
当两个不同的 key，通过哈希函数计算得出的存放位置相同，这个时候就产生了哈希冲突。
通常哈希函数会设计的很少碰到哈希碰撞，一旦发生碰撞，需要解决冲突。
解决冲突方法
- 开放定址法
- 单独链表法
- 双散列
- 再散列
- 建立一个公共溢出区
Java 中解决冲突方法
- Hashtable 通过「链表」去存储这些冲突的 key 的 value，叫做「拉链式解决冲突法」（应该是对应上方 单独链表法）。
- HashMap 通过链表或者红黑树去解决冲突。（通过哪种方法取决于扩容时由链表向红黑树转化，参考 resize 方法）
产生冲突的三个因素
- 散列函数是否均匀
- 处理冲突的方法
- 散列表的荷载因子（load factor）
- 荷载因子：a = 填入表中的元素个数 / 散列表的长度
- A 越大，表明填入表中的元素元多，产生冲突的可能行越大
- 对于开放定址法，荷载因子特别重要，应严格限制在 0.7-0.8 以下。超过 0.8，查表时 CPU 缓存不命中按照指数曲线上升。Java 系统库限制为 0.75，超过此值将 resize 散列表。
哈希表复杂度分析
- 增删查时间复杂度皆为 O(1)，最差 O(n) （产生哈希冲突最后成了链表了）
- 空间复杂度 O(n)
Java code
- Map: key-value 对，key 不重复
- new HashMap() / new TreeMap()
- map.put(key, value)
- map.get(key)
- map.containsKey(key)
- map.size()
- map.clear()
- Set: 不重复元素的集合
- new HashSet() / new TreeSet()
- set.add(value)
- set.remove(value)
- set.contains(value)
Map, Set: interfaces
- Java set classes
- Java map classes
- HashMap, Hashtable, ConcurrentHashMap
- https://docs.oracle.com/en/java/javase/12/docs/api/java.base/java/util/Map.html
小技巧分享
复杂度分析
image.png
