day58
第九章 词典
9.词典
9.b 散列原理
Hashing-散列
数据来源于一个相当大的空间，但是实际要存储和组织的数据是其中很小的子集，空间效率极低
压缩空间
鸽巢问题，将x从比较大的定义域，映射到更小的值域，可以采取一定的手段减少冲突（设计更好的散列函数或者增大散列表长M），但是无法避免（如何解决？）
9.c 散列函数
gcd:最大公因子为1
取中间的若干位，可以使原关键码的各数位对地址的影响彼此更为接近，如下图，平方运算可以分解成加法运算
散列函数越是随机，越是没有规律，越好。
key可能不是整数，需要先将其转换为hashcode,再做处理，如下图
有必要，如果使用简单的计算方法，很容易出现哈希冲突
9.d 冲突
9.d1 散列排解冲突1
查找时跳过，插入时直接插入。
9.d2 散列排解冲突2
封闭定址 vs 开放定址
上面介绍的线性试探，试探位置间距太近，会造成很多不必要的冲突。可以适当的拉开间距
假设一次缓存的大小是1KB，桶中只存储指针（4字节），那么除非发生16次散列冲突，才会使得缓存失效，需要额外的I/O。
b+a≥2，是M的非平凡因子，这与M为素数相矛盾。
对于有些素数（例如7，11）的表长，双向查找链行之有效，有些素数（例如5，13）的表长效果不好.
9.e 桶/计数排序
其中n为元素个数，[0,M)为元素范围
其中红线是蓝线的积分
线性扫描一遍得到count[],再扫描一遍count[]得到accum[],就可以在线性时间完成排序。