3.4散列表

3.4.1软缓存

如果散列的值计算时间很耗时,我们可以将每个键值的散列值缓存起来,即在每一个键中用一个hash变量来保存他们的hashcode()返回值.总的来说要实现优秀的hashCode方法需要满足3个条件:
1.一致性---等价的键产生的散列值必须相等
2.高效性--方便计算
3.均匀性—均匀的散列所有的键
在java中有性能要求时应该谨慎使用散列,因为糟糕的散列函数往往是程序的罪魁祸首.
假设J:(均匀散列的假设)
我们使用的散列能够均匀的并独立的将所有的键值分布在(0~M-1)之间
尽管这个假设很难实现,但是仍然使我们考察散列的最重要的方式.原因有两点:1 设计的散列函数尽量减少随意制定参数以防止大量的数据碰撞. 这是最重要的目标. 2.虽然我们无法精确的验证本身,但是我们可以尽量采用数学分析预测散列的性能,并在试验中验证.

3.4.2 基于拉链法的散列表

• 散列表的大小
  对于基于拉链法散列表,选择的目标是选择适当的数组大小M,既不会因为空链表而浪费内存,又不会因为链表太大而在查找上浪费太多时间.

3.4.3 基于线性探测法的散列表

用Ｍ个数组保存Ｎ个键值，其中Ｍ＞Ｎ，如果遇到碰撞需要用数组的空位来解决，这样的方法叫开放地址法．

开放地址法最简单的叫线性探测法．思路是，如果发生碰撞，则继续在散列表中查找下一个(索引＋１)．
这样会出现３中情况：
１．命中
２．没命中，键为空，该位置没有键
３．没命中，继续查找，该位置的键和被查找的键不同．(如果到了末尾，则折返)

3.4.3.2键族

线性探测的平均成本取决于元素在插入数组后聚集成的一条连续的条目数,叫链族.显然越短的链族对插入命中率越高.

3.4.3.3 线性探测法分析

Knuth在1962年做出的推导算法是算法史上的一个里程碑.

调整大小:

需要考虑在插入数据,和删除数据时都要动态的调整大小,一般而言 put ,N>M/2 ,resize(Mx2),而在delete 时N<M/8 ,resize(M/2);

3.4应用

考察以下3个典型应用场景:

1. 能够快速并灵活的从文件中提取由逗号分割的信息的一个字典和索引程序.逗号分隔的格式(及类似格式)常用于存储网络信息.
2. 为一组文件构建逆向索引的程序
3. 一个表示稀疏矩阵的数据类型.他用符号表处理的问题的规模远远大于这种数据类型的标准实现.

应该使用符号表的哪种实现?

• 1.散列表的优点在于代码简单,且查找时间最优(常数级别,只要键的数据类型是标准或简单到可以为他写出满足均匀性假设的高效散列函数即可)
• 2.二叉查找树相对于散列表数据抽象更简单,不需要为其编写散列函数.
• 3.红黑树可以保证最坏情况下性能,且他支持更多的操作(如排名,选择,排序,和范围查找)

大多时候时候会选择散列表,在其他更重要因素下才是红黑树

2018-04-07 21-56-48 的屏幕截图.png