10-哈希化

认识哈希化：

• 现在需要一种压缩方法，把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。
  
• 对于英语词典，多大的数组才合适：
  
  • 如果只有50000个单词，可能会定义一个长度为50000的数组。
    
  • 但是实际情况中，往往需要更大的空间来存储这些单词，因为我们不能保证单词会映射到每一个位置。
    
  • 比如两倍大小：100000.
    
• 压缩起来：
  
  • 现在，就找一种方法，把0到超过7000000000000的范围，压缩为从0到100000.
    
  • 有一种简单的方法就是使用取余操作符，它的作用是得到一个数被另外一个数整除后的余数。
    
• 取余操作的实现：
  
  • 为了看到这个方法如何工作，我们先来看一个小点的数字范围，压缩到一个小点的空间中。
    
  • 假设从0~199的数字，比如使用largeNumber代表，压缩为从0到9的数字，比如使用smallRange代表。
    
  • 下标值的结果：index = largeNumber % smallRange；
    
  • 当一个数被10整除时，余数一定在0~9之间；
    
  • 比如13%10=3，157%10=7。
    
  • 当然这中间还是会有重复，不过重复的数量明显变小了，因为我们的数组是100000，而只有50000个单词。
    
  • 就好比，你在0~199中间选取5个数字，放在这个长度为10的数组中，也会重复，但是重复的概率非常小，（后面我们会讲到真的发生了重复应该怎么解决）。
    

哈希表的一些概念：

• 哈希化：将大数字转化成数组范围内下标的过程，我们就称之为哈希化。
  
• 哈希函数：通常我们会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数我们成为哈希函数。
  
• 哈希表：最终将数据插入到这个数组，对整个结构的封装，我们就称之为是一个哈希表。
  
• 但是还有问题需要解决：
  
  • 虽然，我们在一个100000的数组中，放50000个单词已经足够。
    
  • 但是通过哈希化后的下标值依然可能会重复，如何解决这种重复的问题那。
    

冲突问题：
尽管50000个单词，我们使用了100000个位置来存储，并且通过一种相对比较好的哈希函数来完成，但是依然有可能会发生冲突。

• 比如melioration这个单词，通过哈希函数得到它数组的下标值后，发现那个位置上已经存在一个单词demystify。
  
• 因为它经过哈希化后和melioration得到的下标实现相同。
  
  • 这种情况我们成为冲突。
    
  • 虽然我们不希望这种情况发生，当然跟希望每个下标对应一个数据项，但是通常这是不可能的。
    
  • 冲突不可避免，我们只能解决冲突。
    

• 就像之前0~199的数字选取5个放在长度为10的单元格中。
  
  • 如果我们随机选出来的是33，82，11，45，90，那么最终它们的位置会是：3-2-1-5-0，没有发生冲突。
    
  • 但是如果其中有一个33，还有一个73呢？还是发生了冲突。
    
• 我们需要针对这种冲突提出解决方案。
  
  • 即使冲突的可能性比较小，你依然需要考虑到这种情况。
    
  • 以便发生的时候进行对应的处理代码。
    
• 常见的情况有两种方案：
  
  • 链地址法。
    
  • 开放地址法。
    

链地址法：
链地址法是一种比较常见的解决冲突的方案（也称之为拉链法）
示图：

• 图片解析：
  
  • 图中表示：链地址解决冲突的办法是每个数单元中存储的不再是单个数据，而是一个链条。
    
  • 这个链条常用的数据结构是数组或者链表。
    
  • 比如说是链表，每个数组单元中存储着一个链表，一旦发现重复，将重复的元素插入到链表的首端或末端。
    
  • 当查询时，先根据哈希化后的下标值找到对应的位置，在取出链表，依次查询寻找的数据。
    
• 数组还是链表：
  
  • 数组或链表在这里其实都可以，效率上也差不多。
    
  • 因为根据哈希化的indx找出这个数组或者链表时，通常就会使用线性查找，这个时候数组和链表的效率是差不多的。
    
  • 在某些实现中，会将新插入的数据放在数组或者链表的最前面，因为觉得新插入的数据用于取出的可能性更大。
    
  • 这种情况最好采用链表，因为数组在首位插入数据是需要所有其它项向后移的，链表就没有这样的问题。
    
  • 当然，实际是看业务需求的，不见得新的数据就会访问次数更多。
    

开发地址法：
开放地址的主要工作方式是寻找空白的单元格来添加重复的数据。
示意图片：

• 图片解析：
  
  • 从图片的文字中我们可以了解到。
    
  • 开放地址法其实就是要寻找空白的位置来放置冲突的数据项。
    
• 但是搜索这个位置的方式不同，有三种方法：
  
  • 线性探测
    
    • 线性探测非常好理解：线性的查找空白的单元。
      
    • 如何插入依据重复的？比如是32取余2：
      
      • 经过哈希化得到的index=2，但是在插入的时候，发现该位置已经有了82。
        
      • 线性探测就是从index位置+1开始一点点查找合适的位置来放置32，什么是合适的位置呢？
        
      • 空的位置就是合适的位置，在我们上面的例子中就是index=3的位置，这个时候就会放在该位置。
        
    • 怎么查询这个因为依据重复而+1向后排的数据？假设说还是32。
      
      • 查询32和插入32比较相似。
        
      • 首先经过哈希化得到index = 2，比如2的位置结果和查询的数值是否相同，相同那么就直接返回。
        
      • 不相同呢？线性查找，从index的位置+1开始查找和32一样的。
        
      • 这里有一个特别需要注意的地方：如果32的位置我们压根没有插入，是否将整个哈希表查询一遍来确定32存不存在？
        
      • 当然不是，查询过程有一个约定，就是查询到空位置，就会停止。
        
      • 因为查询到这里有空位置，32之前不可能跳过空位置去其它的位置。
        
    • 那么删除数据（32为例）？
      
      • 删除操作和插入查询比较类似，但是也有一个特别注意点。
        
      • 注意：删除操作一个数据项时，不可以将这个位置下标的内容设置为null，为啥？
        
      • 因为将它设置为null可能会影响我们之后查询其它数据的操作，比如个线性结构有了2，后又插入了32，82，取余依据后续排序，我们操作了删除32，32的占据的位置置为了null，我们在查找82时，依据线性查找的话肯定会被原先32位置置为的null给拦住误判的，所以我们要将删除位置进行特殊处理（比如置为-1）。
        
      • 当我们之后看到 -1 数据时，就知道查询时要继续查询，但是插入时这个位置可以放置数据。
        
      • 线性探测的问题：
        
        • 线性探测有一个比较严重的问题，就是聚集，什么是 聚集？
          
        • 比如我们在没有任何数据的时候，插入的是22-23-24-25-26，那么意味着下标值：2-3-4-5-6的位置都有元素。
          
        • 这种一连串填充单元就叫做聚集。
          
        • 聚集会会影响哈希表的性能，无论是插入/查询/删除都会有影响。
          
        • 比如我们插入一个32，会发现连续但单元都不允许我们放置数据，并且在这个过程中我们需要探索多次。
          
        • 然而二次探索可以解决一部分这个问题。
          
  • 二次探测
    
    • 线性探测存在的问题：
      
      • 如果之前的数据是连续插入的，那么新插入的一个数据可能需要探测很长的距离。
        
    • 二次探测在线性探测的基础上进行了优化：
      
      • 二次探测主要优化的是探测时的步长，啥意思那？
        
      • 线性探测，我们可以看成是步长为1的探测，比如下标值x开始，那么线性测试就是x+1, x+2, x + 3 依次探测。
        
      • 二次探测，对步长做了优化，比如从下标值x开始，x+1的2次方，x+2的2次方，x+3的2次方。
        
      • 这样就可以一次性探测比较长的距离，避免那些聚集带来的影响。
        
    • 二次探测的问题：
      
      • 但是二次探测依然存在问题，比如我们连续插入的时 32-112-82-2-192 这样的，那么它们依次累加的时候步长是相同的。
        
      • 也就是这种情况下会造成步长不一的一种聚集，还是会影响效率，（当然这种可能性相对于连续的数字会小一些）。
        
      • 怎么根本解决这个问题？让每个项的步长不一样，那么就是再哈希法。
        
  • 再哈希法
    
    • 为了消除线性探测和二次探测中无论步长+1，还是步长+平法中存在的问题，还有一种最常用的解决方案：再哈希法。
      
    • 再哈希法：
      
      • 二次探测的算法产生的探测序列步长是固定的：1的2次方=1，2的2次方=4，3的2次方=9，4的2次方=16，依次类推。
        
      • 现在需要一种方法：产生一种依赖关键字的探测序列，而不是每个关键字都是一样的。
        
      • 那么，不同的关键字即使映射到相同的数组下标，也可以使用不同的探测序列。
        
      • 再哈希发的做法就是：把关键字用另外一个哈希函数，再做一次哈希化，用这次哈希化的结果作为步长。
        
      • 对于指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长。
        
    • 二次哈希化需要具备如下特点：
      
      • 和第一个哈希函数不同，（不要使用上一次的哈希函数了，不然结果还是会在原来的位置）。
        
      • 不能输出为0（否则，将没有步长，每次探测都是原地踏步，算法就进入了死循环）。
        
    • 其实，我们不用费脑细胞来设计，计算机专家已经设计出一种工作很好的哈希函数：
      
      • stepSize = constant - （key % constant）。
        
      • 其中constant是质数，且小于数组的容量。
        
      • 列如：stepSize = 5 - （key % 5 ），满足需求，并且结果不可能为0。
        

哈希化的效率：

• 哈希表中执行插入和搜索操作效率是非常高的
  
  • 如果没有产生冲突，那么效率就会更高。
    
  • 如果发生冲突，存取时间就依赖后来的探测长度。
    
  • 平均探测长度以及平均存取时间，取决于装填因子，随着装填因子变大，探测长度也越来越长。
    
  • 随着填装因子变大，效率下降的情况，在不同开放地址法方案中比链地址更严重，所以我们来对比一下它们的效率，再决定我们选取的方案。
    
• 在分析效率之前，我们先了解：填装因子概念。
  
  • 装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值。
    
  • 填装因子 = 总数据项 / 哈希表长度。
    
  • 开放地址法的装填因子最大是1，因为它必须寻找到空白的单元才能将元素放入。
    
  • 链地址法的装填因子可以大于1，因为链地址可以无限的延伸下去，只要你愿意，（当然后面效率会变低）。
    

线性探测效率

• 下面的等式显示了线性探测时，探测序列（P）和填装因子（L）的关系。
  
  • 对成功的查找： P=(1+1/(1-L)^2)/2
    
  • 对不成功的查找：P=(1+1/(1-L))/2
    
• 公式来自于Knuth（算法分析领域的专家，现代计算机的先驱人物），这些公式的推导过程有兴趣可以自己去查，这里推导过程，只是说明它的效率。
  
• 
  
• 图片解析：
  
  • 当填装因子是1/2时，成功的搜索需要1.5次比较，不成功的搜索需要2.5次。
    
  • 当填装因子更大，比较次数会非常大。
    
  • 应该使填装因子保存在2/3（3分之2）以下，最好在1/2（2分之1）以下，另一方面，填装因子越低，对于给定数量的数据项，就需要越多的空间。
    
  • 实际情况中，最好的填装因子取决于存储效率和速度之间的平衡，随着填装因子变小，存储效率下降，而速度上升。
    

二次探测和再哈希化的性能

• 二次探测和在哈希法的性能相当，它们的性能比线性探测略好。
  
• 对成功的搜索，公式是：-log2（1-loadFactor）/ loadFactor 。
  
• 对于不成功的搜索，公式是：1/（1-loadFactor）
  
• 
  
• 图片解析：
  
  • 当填装因子是0.5时，成功和不成的查找平均需要2次比较。
    
  • 当填装因子为2/3时，分布需要2.37和3.0次比较。
    
  • 当填装因子为0.8时，分布需要2.9和5.0次。
    
  • 因此对于比较高的填装因子，对比线性探测，二次探测和再哈希还凑合着用。
    

链地址法的性能

• 连地址法的效率分析有些不同，一般来说比开放地址法简单，我们来分析以下这个公式应该是怎样的。
  
  • 加入哈希表包含arraySize个数据项，每个数据项有一个链表，在表中一共包含N个数据项。
    
  • 那么，平均起来每个链表有 N/arraySize 个数据项。
    
  • 这个公式实际上就是装填因子。
    
• OK，那么我们现在就可以求出查找成功和不成功的次数了。
  
  • 成功可能只需要查找链表的一半即可：1+loadFactor/2。
    
  • 不成功呢？可能需要将整个链表查询完才知道：1+loadFactor。
    
• 经过上面的比较我们可以发现，链地址法相对来说效率是好于开放地址法的。
  
• 所以在真实开发中，使用链地址法的情况较多。
  
  • 因为它不会因为添加了某元素后性能急剧下降。
    
  • 比如Java的HashMap中使用的就是链地址法。
    

优秀的哈希函数

• 哈希表理论知识，一个非常重要的东西：哈希函数。
  
• 好的哈希函数应该尽可能让计算的过程变得简单，提高计算的效率。
  
  • 哈希表的主要优点是它的速度，所以在速度上不满足，那么就达不到设计的目的了。
    
  • 提高速度的一个办法就是让哈希函数中尽量少用乘法和除法（计算机在运算乘除的时候效率不会特别高），因为它们的性能比较低。
    
• 设计好的哈希函数应该具备那些优点：
  
  • 快速的计算
    
    • 哈希表的优势就在于效率，所以快速获取到对应的hashCode非常重要。
      
    • 我们需要通过快速的计算来获取到元素对应的hashCode。
      
  • 均匀分布
    
    • 哈希表中，无论是链地址法还是开发地址法，当多个元素映射到同一个位置的时候，都会影响效率。
      
    • 所以优秀的哈希函数应该尽可能将元素映射到不同的位置，让元素在哈希表中均匀的分布。
      

快速计算：霍纳法则

• 在前面，我们计算哈希值的时候使用的方式。
  
  • cats = 3273 + 1272 + 20*27 + 17 = 60337
    
• 这种方式是直观计算的结果，那么这种计算方式会进行几次乘法几次加法？
  
  • 当然我们可能不止4项，可能有更多项
    
  • 我们抽象一下，这个表达式其实是一个多项式：a(n)x^n+a(n-1)x^(n-1)+…+a(1)x+a(0) 。
    
• 现在问题就变成了多项式有多少次乘法和加法：
  
  • 乘法次数：n+（n-1）+…+1 = n(n+1)/2 。
    
  • 加法次数：n次 。
    
• 多项式的优化：霍纳法则
  
  • 解决这类求值问题的高效算法—霍纳法则。在中国，霍纳法则也被称位秦九韶算法。
    
• 通过如下变换我们可以得出一种快得多的算法：
  
  • 
    
• 变化前，我们需要多少次乘法，多少次加法？
  
  • 乘法次数：n（n+1）/2次；
    
  • 加法次数：n次；
    
• 变化后，我们需要多少次乘法，多少次加法？
  
  • 乘法次数：N次；
    
  • 加法次数：N次；
    
• 如果使用大O表示时间复杂度的话，我们直接从O(N^2)降到了O(N) 。
  

均匀分布

• 均匀的分布
  
  • 在设计哈希表时，我们已经有办法处理映射到相同下标值得情况:链地址法或者开放地址法。
    
  • 但是无论那种方案，为了提供效率，最好得情况还是让数据在哈希表中均匀分布。
    
  • 因此，我们需要在使用常量得地方，尽量使用质数。
    
  • 哪些地方我们会使用到常量？
    
• 质数的使用：
  
  • 哈希表的长度。
    
  • N次幂的底数（我们之前使用的是27）。
    
• 为什么使用质数，会让哈希表分布更加均匀？
  
  • 我们这里简单来讨论一下。
    

哈希表的长度

• 哈希表的长度最好使用质数
  
• 再哈希法中质数的重要性：
  
  • 假设表的容量不是质数，列如：表长度为15（下标值0~14）
    
  • 有一个特定关键字映射到0，步长为5，探测序列是多少呢？
    
  • 0 - 5 - 10 - 0 - 5 - 10，一次类推循环下去。
    
  • 算法只尝试着三个单元，如果这三个单元已经有了数据，那么会一直循环下去，直到程序崩溃。
    
  • 如果容量是一个质数，比如13，步长还是5探测序列是多少？
    
  • 0 - 5 - 10 - 2 - 7 - 12 - 4 - 9 - 1 - 6 - 11 - 3 - 8，一直这样下去。
    
  • 不仅不会产生循环，而且可以让数据在哈希表中更加均匀的分布。
    
• 链地址法中质数没有那么重要，甚至在Java中故意是2的N次幂。
  

Java中的HashMap

• Java中的哈希表采用地是链地址法。
  
• HashMap的初始长度是16，每次自动扩展（我们还没有聊到扩展的话题），长度必须是2的次幂。
  
• 这是为了服务于从Key映射到index的算法。
  
• HashMap中为了提高效率，采用了位运算的方式。
  
  • HashMap中index的计算公式：index = HashCode（key）&（Lrngth - 1）
    
  • 比如计算book的hashcode，结果为十进制的3029737，二进制的1011100011101011101001 。
    
  • 假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111 。
    
  • 把以上两个结果做与运算，1011100011101011101001 & 1111 = 1001，十进制为9，所以index=9 。
    
  • 这样的方式相对于取模来说性能会高，因为计算机更运算计算二进制的数据。
    
• 但是JavaScript中进行较大数据的位运算时，可能会出现问题，所以以js实现的代码还是使用了取模。
  
  • 在这里为了方便代码之后向开发地址法中迁移，容量还是选择使用质数。