算法笔记-散列表2

如何打造一个工业级别的散列表

在散列表中：散列函数，扩容机制，冲突解决等是决定散列表性能的重要因素，下面针对这三者分析它们是如何影响散列表的性能的。

散列函数

散列函数的设计不能太过复杂，否则计算散列值的时候势必会消耗更多的时间。
散列函数生成的值要尽可能随机且自由分布，否则势必会引起更多的散列冲突

散列函数的设计过程中，我们要综合考虑数据关键字的类型，长度，规模以及分布。上篇文章中，针对运动员的编号分析创建出散列函数，这种方法叫做“数据分析法”。当然还有其他直接寻址法，平方取中法，折叠法，随机数法等等。

散列表的扩容

在散列表中，装载因子的高低说明了散列表中元素的多少，空闲地址的多少，引发散列冲突概率的大小。同时，也体现了在散列表中插入删除以及查找数据的快慢。

对于静态数据集合，可以设计出稳定高效的散列函数，保证散列表的高性能。

对于动态数据集合，由于数据规模的变化，装载因子也跟着变化。当数据规模大的时候，散列冲突就愈发明显，整个散列表的性能机会急剧下降。这个时候，我们就需要对散列表扩容。扩容之后，我们对数据搬移的过程中，就要重新计算散列值，重新确定元素在散列表中的位置。

散列表的扩容，是因为装载因子值过大，散列冲突高频发生。如果，装载因子过小，说明散列表中空闲地址过多，造成了资源浪费，所以就需要缩蓉。所以，装载因子的设定，要充分考虑到散列表中散列冲突发生的概率以及散列表内存地址的高效使用。

低效散列表的扩容：当往散列表中插入数据的时候发现散列表需要扩容，这个时候直接申请内存空间，搬移散列表数据，最后在新的散列表中插入数据。这个插入过程不仅包含了插入操作，还包含了数据搬移的工作，插入时间相当长，这种一次性扩容的方法效率不高。

高效散列表的扩容：扩容的时候，先申请内存空间，然后不要一次性把所有的元素搬移到新的散列表中。每次插入新数据的时候，插入到新的散列表的中，并且从旧散列表中取出一个数据放入新的散列表中。每次查询数据的时候，先从旧的散列表中查询，若未查到，再到新的散列表中查询。经过多次重复这样的操作，旧散列表中的数据就会一点一点的转移到新的散列表中。

散列冲突的解决

开放寻址法：例如 Java 中 ThreadLocalMap
开发寻址法中，散列表中的数据都存储在数组中，可以有效利用CPU缓存加速查询。这种方法实现的散列表，序列化方便。缺点就是冲突代价更高，装载因子不能大于 1。试用场景就是：当数据规模较小，装载因子小的时候，适合采用这种方法。

链表法：例如 Java 中 LinkedHashMap
链表法的内存利用率高，不用像数组那样提前申请号内存空间，而是在需要的时候再申请内存节点。对于散列冲突的元素，该散列值位置对应的是一个链表，可以直接将数据插入的链表的尾部，所以用链表法实现的散列表，装载因子可以很大。即便装载因子过大，链表数据过多，我们可以将链表转化为跳表或者是红黑树，查找数据的时间复杂度就是 O(logn) 不会是 O(n)。当然，它的缺点就是内存访问不友好，占用的内存都是零散的内存地址，不想数组那般是一个连续的内存空间。所以，链表法实现的散列表适合大数据规模，优化策略是可以将链表转化为跳表或者红黑树这种结构。

工业散列表的分析

Java 中的 HashMap：
初始大小：16，也可以修改默认值设置初始大小。
装载因子和动态扩容：装载因子是 0.75，每次扩容都是扩大为原来的两倍。
散列冲突解决办法：底层采用链表法解决散列冲突，JDK1.8以后修改了链表的数据结构。当链表中的元素个数大于 8 的时候，链表转化为红黑树，当链表元素个数小于 6 的时候转化为链表。
散列函数：见代码

int hash(Object key) {
    int h = key.hashCode()；
    return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小
}

public int hashCode() {
  int var1 = this.hash;
  if(var1 == 0 && this.value.length > 0) {
    char[] var2 = this.value;
    for(int var3 = 0; var3 < this.value.length; ++var3) {
      var1 = 31 * var1 + var2[var3];
    }
    this.hash = var1;
  }
  return var1;
}

如何打造一个工业级别的散列表

一个工业级别的散列表应该具备以下特点：
性能稳定，极端情况下性能也不会退化到难以接受的地步(时间复杂度的考量)。
内存空间使用合理，不浪费过多的内存空间(空间复杂度的考量)。
支持高效的插入删除查找等操作(综合考量时间复杂度和空间复杂度)。

为了保证以上特点，我们就要考虑设计一个合适的散列函数，保证数据随机性以及均匀分布。定义合适的装载因子值，设计动态扩容缩容的策略，不浪费空间又保证散列冲突发生低频性。选择合适的散列冲突解决方式，综合考量数据的规模特点等等。

总结

本文创作灵感来源于 极客时间 王争老师的《数据结构与算法之美》课程，通过课后反思以及借鉴各位学友的发言总结，现整理出自己的知识架构，以便日后温故知新，查漏补缺。

初入算法学习，必是步履蹒跚，一路磕磕绊绊跌跌撞撞。看不懂别慌，也别忙着总结，先读五遍文章先，无他，唯手熟尔~
与诸君共勉