一、前言哈希表的历史哈希思想在不同的地方独立出现。1953年1月，HansPeterLuhn使用散列和链接编写了一份IBM内部备忘录。开放寻址是后来ADLinh在Luhn的论文中提出的。大约在同一时间，IBMResearch的GeneAmdahl、ElaineM.McGraw、NathanielRochester和ArthurSamuel为IBM701汇编程序实现了散列。线性探测的开放寻址是由于Amdahl，尽管Ershov独立地有相同的想法。“开放寻址”一词是由W.WesleyPeterson在他讨论大文件搜索问题的文章中创造的。2.哈希数据结构哈希表的存在就是为了解决通过O(1)时间复杂度直接索引到指定元素的问题。这是什么意思？通过使用数组来存储元素，它们都是按顺序存储的。当需要获取一个元素时，需要遍历数组获取指定的值。如图所示；而通过循环遍历比较获取指定元素的操作，时间复杂度为O(n)，也就是说如果你的业务逻辑实现中有这样的代码，那会很hip。那我们该怎么办呢？这就介绍了哈希表的设计。在计算机科学中，哈希表（hashtable、hashmap）是一种实现关联数组的抽象数据结构，通过哈希计算将键映射到值。也就是说，我们计算一个Key值的hash，将长度为2的n次方的数组减一，计算slot对应的index，将数据存入index下。那么这样就解决了在获取指定数据时，只需要按照存储时计算索引ID的方法重新计算一遍，就可以获取到slot上对应的数据并进行处理，从而实现了这种情况时间复杂度为O(1)。.如图所示；虽然哈希解决了获取元素的时间复杂度问题，但是大多数时候这只是一种理想情况。因为随着元素个数的增加，很可能会发生hash冲突，或者hash值波动不大，导致计算同一个索引，即多个元素出现在一个索引位置。如图所示；当李二狗和李飘虫的下标索引为03的胯猫发生冲突时，情况变得更糟，因为它不能满足O(1)时间复杂度的获取。要素提出上诉。那么这时候就出现了一系列的解决方案，包括：HashMap+红黑树中的拉链寻址、扰动函数、负载因子、ThreadLocal的开放寻址、mergehash、cuckoohash、hopscotchhash、RobinHoodGreek等多种数据结构设计。当发生哈希冲突时，让元素存储到新的槽中，并尽量保证索引的时间复杂度小于O(n)，不管是我们用的HashMap，ThreaLocal还是你刷题提高索引效率，都会用到hash散列。只要通过加载因子合理控制哈希桶的长度，每次元素查找的平均时间复杂度与桶中存储的元素数量无关。此外，许多哈希表设计还允许任意插入和删除键值对，每个操作的摊销固定平均成本。好了，介绍了这么多，付哥就带大家做几个关于散列的数据结构，通过实践会更容易理解。源码地址：https://github.com/fuzhengwei/java-algorithms(opensnewwindow)-Java算法与数据结构本章源码：https://github.com/fuzhengwei/java-algorithms/blob/main/data-structures/src/main/java/cn/bugstack/algorithms/data/queue/DelayQueue.java(opensnewwindow)1.Hash碰撞说明：通过模拟一个简单的HashMap实现，去除拉链寻址等设计，在索引位置验证元素Collision的新颖性。publicclassHashMap01implementsMap{privatefinalObject[]tab=newObject[8];@Overridepublicvoidput(Kkey,Vvalue){intidx=key.hashCode()&(tab.length-1);tab[idx]=值；}@OverridepublicVget(Kkey){intidx=key.hashCode()&(tab.length-1);返回（V）标签[idx]；}}HashMap01的实现只是hash计算下标，hash存储在一个固定的数组中。那么当元素下标发生冲突时，原元素将被新元素替换。测试@Testpublicvoidtest_hashMap01(){Mapmap=newHashMap01<>();map.put("01","花花");map.put("02","豆豆");logger.info("keybeforecollision:{}value:{}","01",map.get("01"));//下标碰撞map.put("09","Dandan");map.put("12","喵喵");logger.info("Keybeforecollision:{}value:{}","01",map.get("01"));}06:58:41.691[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-碰撞前key:01value:Huahua06:58:41.696[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-碰撞前key:01value:MiaoMiaoProcessfinishedwithexitcode0通过测试结果，我们可以看到碰撞前map.get("01")的值为花花，两次下标索引碰撞后存储的值为喵喵。这是使用哈希哈希必须解决的一个问题，无论是在已知元素个数的情况下通过扩充数组长度来解决，还是通过链表存储碰撞的元素，都是可以解决的。2.zipperaddressing说明：既然我们不能控制元素碰撞，那么我们可以管理碰撞后的元素。比如像HashMap中的zipper方法，将碰撞的元素存储在链表上。这里我们简化实现。公共类HashMap02BySeparateChaining实现Map{privatefinalLinkedList>[]tab=newLinkedList[8];@Overridepublicvoidput(Kkey,Vvalue){intidx=key.hashCode()&(tab.length-1);if(tab[idx]==null){tab[idx]=newLinkedList<>();tab[idx].add(新节点<>(key,value));}else{tab[idx].add(新节点<>(key,value));}}@OverridepublicVget(Kkey){intidx=key.hashCode()&(tab.length-1);for(NodekvNode:tab[idx]){if(key.equals(kvNode.getKey())){返回kvNode.value;}}返回空值；}staticclassNode{finalKkey;V值；公共节点（K键，V值）{this.key=key;this.value=值；}公共KgetKey(){返回键；}publicVgetValue(){返回值；}}}因为在哈希桶中存储元素时可能会发生下标索引扩展，所以这里我们将每个元素设置为一个Node节点，这些Node通过LinkedList链表进行关联。当然你也可以通过Node节点构建链表的下一个元素。这时候，当元素发生碰撞时，相同位置的元素就会被存储到链表中。获取时，需要存储多个元素。遍历链表得到。测试@Testpublicvoidtest_hashMap02(){Mapmap=newHashMap02BySeparateChaining<>();map.put("01","花花");map.put("05","豆豆");logger.info("keybeforecollision:{}value:{}","01",map.get("01"));//下标碰撞map.put("09","Dandan");map.put("12","喵喵");logger.info("Keybeforecollision:{}value:{}","01",map.get("01"));}07:21:16.654[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-碰撞前键：01值：Huahua07:22:44.651[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-碰撞前键：01值：HuahuaProcessfinishedwithexitcode0此时，位置处的元素第一次和第二次得到的01都是花，元素没有被替换。因为此时的元素是存储在链表上的。3、开放寻址说明：除了将碰撞索引元素zip存储在hashbucket上之外，还有一种方法是将碰撞元素存储在hashbucket上，而不引入新的额外数据结构。称为开放寻址，是ThreaLocal中使用Fibonacci哈希+开放寻址的处理方式。公共类HashMap03ByOpenAddressing实现Map{privatefinalNode[]tab=newNode[8];@Overridepublicvoidput(Kkey,Vvalue){intidx=key.hashCode()&(tab.length-1);if(tab[idx]==null){tab[idx]=newNode<>(key,value);}else{for(inti=idx;i(key,value);休息;}}}}@OverridepublicVget(Kkey){intidx=key.hashCode()&(tab.length-1);对于(inti=idx;i{finalKkey;V值；公共节点（K键，V值){this.key=key;this.value=值；}}}开放寻址的设计会为碰撞的元素在哈希桶上寻找新的位置。这个位置会从当前的碰撞位置开始向后搜索，直到找到空的位置存储在ThreadLocal实现中，它使用斐波那契哈希、索引计算累加、启发式清洗、检测清洗等操作来保证尽可能少的碰撞。测试@Testpublicvoidtest_hashMap03(){Mapmap=newHashMap03ByOpenAddressing<>();map.put("01","花花");map.put("05","豆豆");logger.info("keybeforecollision:{}value:{}","01",map.get("01"));//下标碰撞map.put("09","Dandan");map.put("12","喵喵");logger.info("Keybeforecollision:{}value:{}","01",map.get("01"));}07:20:22.382[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-碰撞前键：01值：Huahua07:20:22.387[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-碰撞前键：01值：Huahua07:20:22.387[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-数据结构：HashMap{tab=[null,{"key":"01","value":"Huahua"},{"key":"09","value":"Egg"},{"key":"12","value":"MiaoMiao"},null,{"key":"05","value":"Doudou"},null,null]}进程结束，退出码0通过测试结果可以看出，对于冲突元素的寻址和存储，也可以使用开放寻址来解决哈希索引冲突的问题。4.Mergehash描述：Mergehash是开放寻址和个体链接的混合体，其中冲突的节点链接在一个哈希表中。该算法适用于内存分配固定的哈希桶，在存储元素时通过识别哈希桶上最大的空槽来解决合并哈希的冲突。公共类HashMap04ByCoalescedHashing实现Map{privatefinalNode[]tab=newNode[8];@Overridepublicvoidput(Kkey,Vvalue){intidx=key.hashCode()&(tab.length-1);if(tab[idx]==null){tab[idx]=newNode<>(key,value);返回;}intcursor=tab.length-1;while(tab[cursor]!=null&&tab[cursor].key!=key){--cursor;}tab[cursor]=newNode<>(key,value);//将撞击节点指向这个新节点while(tab[idx].idxOfNext!=0){idx=tab[idx].idxOfNext;}tab[idx].idxOfNext=cursor;}@OverridepublicVget(Kkey){intidx=key.hashCode()&(tab.length-1);while(tab[idx].key!=key){idx=tab[idx].idxOfNext;}返回标签[idx].value;}staticclassNode{finalKkey;V值；intidxOfNext;公共节点（K键，V值）{this.key=key;this.value=值；}}}组合hash最大的目的就是把碰撞的元素联系起来，避免了需要寻找碰撞元素出现的循环遍历意味着A和B元素在存储的时候发生了碰撞，所以当找到A元素时，可以快速索引B元素的位置。Test07:18:43.613[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-pre-collisionkey:01value:Huahua07:18:43.618[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-预碰撞collisionkey:01value:Miaomiao07:18:43.619[main]INFOcn.bugstack.algorithms.test.AlgorithmsTest-数据结构：HashMap{tab=[null,{"idxOfNext":7,"key":"01","value":"花花"},null,null,null,{"idxOfNext":0,"key":"05","value":"豆豆"},{"idxOfNext":0,"key":"12","value":"Miaomiao"},{"idxOfNext":6,"key":"09","value":"Egg"}]}进程结束，退出码0相对直接使用openaddressing，这种挂在链接点上的方式，可以提高索引的性能。因为在实际的数据存储中，元素的下一个位置不一定是空元素，有可能已经被其他元素占用，增加了索引的数量。因此，使用直接指向地址的方式会更好的提高索引性能。5.Rhododendronhash说明：这个名字比较有意思，也代表了它的数据结构。杜鹃鸟孵化
