工业级的散列表应该具有哪些特性？
- 支持快速的查询、插入、删除操作；
- 内存占用合理，不能浪费过多的内存空间；
- 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。
如何实现这样一个散列表呢？我会从这三个方面来考虑设计思路：
- 设计一个合适的散列函数；
- 定义装载因子阈值，并且设计动态扩容策略；
- 选择合适的散列冲突解决方法。
1. 如何设计散列函数
首先，散列函数的设计不能太复杂。否则会消耗很多计算时间，影响散列表的性能。其次，散列函数生成的值要尽可能随机并且均匀分布，这样才能避免或者最小化散列冲突。
常见的散列函数设计方法：直接寻址法、平方取中法、折叠法、随机数法等。
2. 如何根据装载因子动态扩容
1. 设置装载因子阈值
针对散列表，当装载因子过大时，我们可以进行动态扩容，重新申请一个更大的散列表，将数据搬移到这个新散列表中，还需要通过散列函数重新计算每个数据的存储位置。对于支持动态扩容的散列表，插入数据的时间复杂度使用摊还分析法是 O(1)。
装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。
2. 避免低效扩容
分批扩容
为了解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成。
分批扩容的插入操作：当有新数据要插入时，将数据插入新散列表，并且从老散列表中取出一个数据放入新散列表。每次插入都重复上面的过程。
分批扩容的查询操作：先查找新散列表，如果没有找到，再查找老散列表。
通过均摊的方式，任何情况下，插入一个数据的时间复杂度都是O(1)。
3. 如何选择冲突解决方法
开放寻址法和链表法在实际的软件开发中都非常常用。比如，Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。
开放寻址法
优点：
- 散列表中的数据都存储在数组中，可以有效地利用 CPU 缓存加快查询速度。
- 没有指针，序列化起来比较简单。
缺点：
- 删除数据的时候比较麻烦，需要特殊标记已经删除的数据。
- 数据存储在一个数组中，比起链表法，冲突的代价更高。
- 装载因子的上限不能太大，比链表法更浪费内存空间。
结论：
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是 Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突的原因。
链表法
优点：
- 链表法对内存的利用率比开放寻址法要高。
- 链表法比起开放寻址法，对大装载因子的容忍度更高。
缺点：
- 对于比较小的对象的存储，是比较消耗内存的。
- 对 CPU 缓存是不友好的，对执行效率有一定的影响。
结论：
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
4. 工业级散列表举例分析
Java 中的 HashMap。
默认初始大小 16
默认最大装载因子 0.75，扩容到原来的两倍
链表法解决冲突，JDK1.8 后引入红黑树
散列函数 (h ^ (h >>> 16)) & (capitity -1);
自己是从事了七年开发的Android工程师，不少人私下问我，2019年Android进阶该怎么学，方法有没有？
没错，年初我花了一个多月的时间整理出来的学习资料，希望能帮助那些想进阶提升Android开发，却又不知道怎么进阶学习的朋友。【包括高级UI、性能优化、架构师课程、NDK、Kotlin、混合式开发（ReactNative+Weex）、Flutter等架构技术资料】，希望能帮助到您面试前的复习且找到一个好的工作，也节省大家在网上搜索资料的时间来学习。
资料获取方式：加入Android架构交流QQ群聊：513088520 ，进群即领取资料！！！
点击链接加入群聊【Android移动架构总群】：加入群聊
资料大全
网友评论