概念
用一个自定义的hash函数算法，将key经过计算得出一个索引值，然后用它去定位对应的值。
一般key不同的话，索引不同，可以O(1)速度查找、插入。 但算出来的索引如果相同，就需要额外处理这个碰撞情况，在一个索引上保存两个值。
Hash表是空间和时间上做出权衡的经典例子 既不能无限扩充索引，虽然更快，但太费空间。 又不能所有人都只用一个索引，那等于就是普通数组了，节省空间但浪费时间要依次遍历循环。所以通畅是任意key通过一个算法，换算成固定数量的一组索引。
Hash函数
对于基础数据类型，比如整数 最简单的方法是除留余数法，比如有10亿比数据，我希望保存在1000个索引上（散列值M=1000），则直接用不同数据的key%1000得出的余数就是索引值，这个索引一定是在0~999之间的。且较为平均的分布。
那么对于char很简单，转成int，继续按整数的套路。 但是String怎么办？如果对象的键是多个部分组成的怎么办？ 可以把多个键相乘相加
1
2
3
int hash = 0;
for (int i = 0; i < s.length(); i++)
hash = (R * hash + s.charAt(i)) % M;
只要R足够小就不会溢出，且为了保证所有字符都能发挥作用，所以用一个比较小的素数，如31。
看java代码里，都没有 %M，如int是直接返回当前值，long是(int)(value ^ (value »> 32))转成int，其他的也都是转成32bit整数的hash函数。相当于M=2^32离散值。
那么字符串如果特别长的时候，不停*31再累加不就int溢出了吗？？？ 溢出没有关系，不会报错，保存成int类型还是在int范围中
那为什么取尽量小的素数31防止溢出呢？且为啥不用13？更小
优秀Hash函数需要满足的三个条件
- 一致性 — 等价的键必然产生相等的hash值
- 高效性 — 计算简便
- 均匀性 — 均匀地散列所有的键
Hash碰撞处理
因为终究还是散落在一个离散值内的，且可能有一样的键，所以肯定会落在同一个索引上的情况，此时就要碰撞处理了。
最简单的是拉链法 直接把同一个索引下的值链式的连起来保存
此外还有线性探测法？
应用
Java中有封装基于Hash的实现 java.util.HashMap
