散列
散列是一种以常数平均时间插入、删除和查找的技术。
1.1 一般想法
理想的散列表就是包含一些项的固定大小的数组，每个关键字被映射到0和tablesize-1这个范围的某个数。
当两个关键字映射到同一个值时称作冲突。
1.2 散列函数
一般想法是：散列函数：Key mod tablesize.但表过大而关键字过小时不能很好的散射。比如表有10000，关键字大小只有0-1000，则不能均匀散列。
另一种是取前n个字符，乘以一定基数，再求余得到散射。
public static int hash(String key,int tblesize){ return (key.charAt(0)+27*key.charAt(1)+729*key.charAt(2)) %tablesize; }
但是前3个字符的分布可能不是随机的。
第三种方式是使用所有字符：
public static int hash(String key,int tblesize){ int hashVal = 0; for(int i=0;i<key.length;i++){ hashVal = 37* hashVal +key.charAt(i); } hashVal %= tablesize; if(hashVal <0) hashVal += tablesize; return hashVal; }
这种方式可能溢出，因此需要处理负数。
处理hash冲突
2.1 分离链接法
将散列到同一个值的所有元素保存再一个表中。通常采用链表实现。Java中这样的对象应实现equals方法并有一个返回int的hashCode方法。
典型实现见HashMap。（）
散列表概念:
装填因子λ：散列表中的元素个数与散列表大小的比值。该值也是散列表中链表的平均长度。
再一次不成功的查找中，平均考察时间为λ，一次成功的查找中需要遍历1+λ/2个链。搜索的链表中包含一个成功匹配的节点和其余节点。N个元素的散列表中含M个链表，其他节点期望个数为（N-1）/M=λ-1/M，M较大，因此约为λ。因此平局代价为1+λ/2。因此装填因子对查找效率影响最大。
一般让元素个数与表大小大致相等。λ约为1
2.2不用链表的散列
分离链表中使用了其余的数据结构，可能导致速度变慢。
因此考虑在冲突时寻找别的位置，这种方式所需的表要比分离链接表的大，一般λ不建议超过0.5.这种方法叫探测散列表。
线性探测表：
线性探测表中，查找空单元的函数为i的线性函数。
假设将[89,18,49,58,69]插入表中。采用x%10的散列函数，表大小为10。当插入49时，与89冲突，放入下一个0的位置，58与18冲突，下一个位置与89冲突，在下一个与49冲突， 再进入下一个位置时才插入。
这样的方式容易造成元素再某一些地方聚集，后面的元素需要找很多次才能插入。
插入及不成功查找为0.5（1+1/（1-λ）^2）,对于成功查找为0.5(1+1/(1-λ))
。。。
平方探测法：
线性探测中存在一次聚集的问题，平方探测将冲突函数该为2次，f(i)=i^2.
在上面的例子中，49与89冲突，被放入下一个单元，58与18冲突，探测到下一个单元89，跳过，到第四个单元，空位置可以插入。
如果使用平方探测，当表有一半是空的，且表大小为素数，则总能插入元素。
探测散列表中元素不能直接删除，否则查找容易失败，一般采用懒惰删除。
平方探测解决了一次聚集，但会导致映射在同一位置的元素探测相同的备选名单，造成二次聚集。
双散列：
一种流行的选择是：f(i)=i*hash2(x)。hash2(x)应谨慎选择，不然容易没有作用。hash2(x)采用 R-(x mod R)比较好。R为素数。
采用上面的例子。采用Ｒ = 7，49与89冲突时，hash2(49）= 7 - 0 = 7.插入6的位置。
双散列可以解决二次聚集，但需要计算hash2函数。
2.3 再散列
当表中元素较多时，需要再建立一个约两倍大的表，并使用与之相关的hash函数重新散列插入。
建立新表时应尽量保证表大小为素数。
一般可以在表一半、插入失败、装填因子达到某一个值时再散列。一般采用第三种。
2.4 标准库中的散列
常见的HashSet与HashMap。HashSet使用HashMap实现。
String类会在第一次使用时记住HashCode吗，避免频繁计算。（String类是不可变的）
20200915
最坏情形下O（1）的散列
装填因子为1时，最坏情形下期望值为（log N/log logN).