哈希表、映射、集合

2020-03-28 本文已影响0人云莉6

哈希表基本概念

维基百科比较清楚，可以参考。我觉得可能最好跟着打字一遍，比读一遍能理解更多，往往太多字，很容易放弃阅读，或者晕头了，而打字的过程中会字字阅读从而思考更多内容：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），这就使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

用来映射 key 存放到哈希表（数组）的位置，这个映射的函数叫做哈希函数。

直接定址法
- 取关键字或关键字的某个线性函数为散列地址。
- 即 hash(k) = k 或 hash(k) = a * k + b, 其中 a，b为常数
- 这种散列函数叫做自身函数
数字分析法
- 假设关键字是以 r 为基的数，并且哈希表中可能出现的关键字都是事先知道的，则可取关键字的若干数位组成哈希地址。
平方取中法
- 取关键字平方后的中间几位为哈希地址。
- 通常在选定哈希函数时不一定能知道关键字的全部情况，取其中的哪几位也不一定合适，而一个数平方后的中间几位数和数的每一位都相关，因此随机分布的关键字得到的哈希地址也是随机的。取的位处由表长决定。
折叠法
- 讲关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为哈希地址。
随机数法
除留余数法
- 取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。
- hash(k) = k mod p, p <= m.
- 不仅可以关键字直接取模，也可在折叠法、平方取中法等运算之后取模。
- 对 p 的选择很重要，一般取素数或 m，若 p 选择不好，容易产生冲突。

当两个不同的 key，通过哈希函数计算得出的存放位置相同，这个时候就产生了哈希冲突。

通常哈希函数会设计的很少碰到哈希碰撞，一旦发生碰撞，需要解决冲突。

散列函数是否均匀
处理冲突的方法
散列表的荷载因子（load factor）
- 荷载因子：a = 填入表中的元素个数 / 散列表的长度
- A 越大，表明填入表中的元素元多，产生冲突的可能行越大
- 对于开放定址法，荷载因子特别重要，应严格限制在 0.7-0.8 以下。超过 0.8，查表时 CPU 缓存不命中按照指数曲线上升。Java 系统库限制为 0.75，超过此值将 resize 散列表。

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)

image.png