Day16
学习内容 :掌握散列表的设计方法和应用场景，我们就可以在保证散列表性能的前提下，设计出工业级水平的散列表。
什么是散列表？
散列表的英文叫“Hash Table”，我们平时也叫它“哈希表”或者“Hash 表”。
散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。
1.如何设计散列函数？
首先，散列函数的设计不能太复杂。
其次，散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突，而且即便出现冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况。
2.装载因子过大了怎么办？
装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。
针对散列表，当装载因子过大时，我们也可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新散列表中。
3.如何避免低效地扩容？
为了解决一次性扩容耗时过多的情况，我们可以将扩容操作穿插在插入操作的过程中，分批完成。当装载因子触达阈值之后，我们只申请新空间，但并不将老的数据搬移到新散列表中。
当有新数据要插入时，我们将新数据插入新散列表中，并且从老的散列表中拿出一个数据放入到新散列表。每次插入一个数据到散列表，我们都重复上面的过程。经过多次插入操作之后，老的散列表中的数据就一点一点全部搬移到新散列表中了。这样没有了集中的一次性数据搬移，插入操作就都变得很快了。
4.如何选择冲突解决方法？
- 开放寻址法
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的ThreadLocalMap使用开放寻址法解决散列冲突的原因 - 链表法
首先，链表法对内存的利用率比开放寻址法要高。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
5.工业级散列表怎么应用？
- 初始大小
HashMap默认的初始大小是16
可以通过修改默认初始大小，减少动态扩容的次数，这样会大大提高 HashMap 的性能。 - 装载因子和动态扩容
最大装载因子默认是 0.75，当 HashMap 中元素个数超过 0.75*capacity（capacity 表示散列表的容量）的时候，就会启动扩容，每次扩容都会扩容为原来的两倍大小。 - 散列冲突解决方法
HashMap 底层采用链表法来解决冲突 - 散列函数
int hash(Object key) {
int h = key.hashCode()；
return (h ^ (h >>> 16)) & (capicity -1); //capicity表示散列表的大小
}
本文参考【极客时间】专栏《数据结构与算法之美》。
网友评论