Java道经第1卷 - 第5阶 - 数据结构二传送门JB1-5-数据结构一传送门JB1-5-数据结构二文章目录S04. 哈希数据结构E01. 哈希代码函数E02. 哈希函数重写E03. 哈希数据结构1. 调用hashCode()2. 右移动运算3. 异或运算4. 取余操作5. 仿写Hash函数E04. 哈希数组扩容E05. 哈希数组重构E06. 哈希碰撞冲突1. 再哈希法2. 公共溢出表3. 开放定址法4. 拉链法S04. 哈希数据结构心法: 哈希算法 Hash Algorithm 被称为散列或哈希是一种算法MD5SHA 等都属于 Hash 算法的实现。Hash Table哈希表也叫散列表是一种以数组为基础的数据结构以键值对映射的方式存取值。E01. 哈希代码函数心法: 哈希码函数hashCode()哈希码函数 hashCode()函数来自于 Object 类即任何实例都可以调用该方法以获取其 Hash 码public native int hashCode()返回指定实例的 Hash 码即对象的唯一标识。哈希码生成策略共有 6 种生成策略可以在 JVM 运行参数中使用-XX:hashCode来设置JVM运行参数描述-XX:hashCode0返回一个随机的 Hash 值该生成策略在高并发的时候会出现自旋等待-XX:hashCode1使用某种算法对实例的内存地址进行计算后返回-XX:hashCode2固定返回 1该策略一般用于测试-XX:hashCode3对一个公共变量进行自增后返回全部实例的哈希码都使用相同的自增变量-XX:hashCode4直接返回实例的内存地址-XX:hashCode其他值利用 xor-shift 算法产生伪随机数默认值 5武技: 测试哈希码生成策略开发测试方法HashCodeTest - testHashCodeGeneratePolicy():packagehash;/** author 周航宇 */publicclassHashCodeTest{/** HashCode生成策略: -XX:hashCode2 */TestpublicvoidtestHashCodeGeneratePolicy(){System.out.println(newObject().hashCode());}}E02. 哈希函数重写心法: 判断两个实例是否相等的流程调用两个实例的hashCode()获取各自的 Hash 值若 Hash 值不等则直接返回 false以此提升比较过程的效率。若 Hash 值相等则返回两个实例的equals()比较结果。所以任何情况下重写equals()时必须同时重写hashCode()以保证 Hash 值相等这一前提条件。武技: 利用 HashMap 测试重写equals()时未重写hashCode()出现的 BUG开发实体类HashCodeTest - User:packagehash;/** author 周航宇 */publicclassHashCodeTest{DataAllArgsConstructorprivatestaticclassUser{privateIntegerid;privateStringname;}}重写方法User - equals():publicclassHashCodeTest{DataprivatestaticclassUser{Overridepublicbooleanequals(Objectobj){// 若参与比较的obj参数就是this自己则直接返回trueif(thisobj){returntrue;}// 若参与比较的obj参数不属于User类型则直接返回falseif(!(objinstanceofUser)){returnfalse;}// 若参与比较的obj参数属于User类型则强转为User类型Useruser(User)obj;// 使用 Objects.equals() 工具分别比较两个实例的id和name值// 全相等则返回true否则返回falsereturnObjects.equals(id,user.id)Objects.equals(name,user.name);}}}开发测试方法HashCodeTest - testEquals():publicclassHashCodeTest{/** 测试重写的equals()方法 */TestpublicvoidtestEquals(){Userjack01newUser(1,杰克);Userjack02newUser(1,杰克);System.out.println(jack01.equals(jack02));}}开发测试方法HashCodeTest - testHashCode():publicclassHashCodeTest{/** 测试HashMap的取值原理 */TestpublicvoidtestHashCode(){Userjack01newUser(1,杰克);Userjack02newUser(1,杰克);HashMapUser,IntegerhashMapnewHashMap();hashMap.put(jack01,100);// HashMap中的get()方法底层是根据key的hash值来获取对应value的// 若User类没重写hashCode()方法则HashMap认为jack02和jack01不是同个key值返回null// 若User类重写了hashCode()方法则hashMap认为jack02和jack01是同个key值返回100System.out.println(hashMap.get(jack02));}}重写方法User - hashCode():publicclassHashCodeTest{DataAllArgsConstructorprivatestaticclassUser{OverridepublicinthashCode(){// 使用 Objects.hash() 工具对id和name的值计算hash总和并返回returnObjects.hash(id,name);}}}重新运行测试方法HashCodeTest - testHashCode()测试HashMap的取值原理。E03. 哈希数据结构心法: 哈希结构的核心就是 Node 数组Node 用于存储一个字符串类型的键一个 Object 类型的值和一个 Node 类型的后继指针和哈希函数决定 Hash 效率的最重要函数。无论使用哈希结构进行存值还是取值都需要先使用哈希函数对元素的键进行计算定位计算的结果就是该元素在 Node 数组中的位置在最优情况下仅需一次便可找到目标元素。Node组成部分中文类型存储内容key键String存储数据的键固定为字符串结构value值E存储数据的值next后继指针NodeE存储下一个节点的内存地址尾节点的next指向null值武技HashMap 的 put() 源码解析先通过hash(key)对 key 值进行计算然后传入putVal()方法。再通过(n - 1) hash计算出 value 最终在数组中的落点索引。1. 调用hashCode()心法解析key.hashCode()调用 Object 的哈希函数计算对象的初始哈希码int 型 Hash 值为 32 位约有 40 亿种可能直接在内存中创建 40 亿长度的数组是不明智的所以不推荐直接使用这个 Hash 值需要使用扰动函数对 h 结果进行二次处理操作。2. 右移动运算心法解析(h 16)将 Hash 值右移动 16 位此时原 Hash 的高 16 位被移动到低 16 位原 Hash 的低 16 位被移出原 Hash 的高 16 位全部补充 0。3. 异或运算心法解析h ^ (h 16)将右移动结果和原 Hash 值进行异或混合原 Hash 的高 16 位信息和低 16 位信息在结果的低 16 位进行混合提升 Hash 值低 16 位的随机性以减少 Hash 冲突而结果的高 16 位信息可忽略。这样做是为了让哈希值的高位信息也能参与到桶位置的计算中从而减少哈希冲突同时简化了计算逻辑。4. 取余操作心法解析(n - 1) hash对比直接取余使用位运算取余方式来决定最终存放的位置其效率比直接取余(hash % length)要高但前提是 bitmap 的长度会被尽量保证为 2 的 N 次方。位运算取余操作从二进制的角度来看对一个数右移 N 位就相当于对这个数除以 2 的 N 次方右移 N 位后剩余的二进制数字所表示的就是商被移出的 N 个数字就是余数所以想要通过位运算获取一个数对 2 的 N 次方取余的结果直接提取该数的后 N 位数即可。减 1 操作一个 2 的 N 次方值减去 1 后位图末尾就会变为 N 个 1如 2 的 2 次方 - 1 03(0000 0011)末尾 2 个 1。如 2 的 3 次方 - 1 07(0000 0111)末尾 3 个 1。如 2 的 4 次方 - 1 15(0000 1111)末尾 4 个 1。取余操作任何数和此时结果的操作会提取 Hash 值中后 N 位如 Hash 值为 21(0001 0101)数组长度为 16减 1 后为 15(0000 1111)那么 (0001 0101) (0000 1111) (0000 0101)相当于提取了 21 的后 4 位而这后 4 位就是 21 对 16 取余的结果 5。5. 仿写Hash函数武技: 开发自定义哈希结构开发哈希类MyHashTest - MyHash:packagehash;/** author 周航宇 */SuppressWarnings(all)publicclassMyHashTest{/** 哈希类 */DatapublicclassMyHash{DataAllArgsConstructorprivateclassNode{privateStringkey;privateObjectvalue;privateMyHash.Nodenext;}/** 底层数组 */privateMyHash.Node[]nodesnewMyHash.Node[4];/** 底层数组中非null元素的个数 */privateIntegerelementLength0;/** 加载因子: 当数组当前容量超过 capacity * factor 时进行扩容 */privatefloatfactor0.75f;}}开发方法MyHashTest - MyHash - hash():publicclassMyHashTest{publicclassMyHash{/** * 计算指定元素的hash值并返回 * * param obj 待计算的元素 * return 指定元素的hash值 */publicinthash(Objectobj){// 对 obj 参数进行空值保护if(objnull){return0;}// 获取Hash值inthobj.hashCode();// 使用扰动函数和取余处理优化Hash值并返回return(h^(h16))(nodes.length-1);}}TestpublicvoidtestHash(){MyHashmyHashnewMyHash();System.out.println(myHash.hash(周));System.out.println(myHash.hash(航));System.out.println(myHash.hash(宇));}}开发方法MyHashTest - MyHash - put():publicclassMyHashTest{publicclassMyHash{/** 在数组中存储数据 */publicvoidput(Stringkey,Objectvalue){// 在数组的 hash(key) 位置上存储一个Node数据nodes[hash(key)]newMyHash.Node(key,value,nextNode);// 数组中的非null元素计数器自增elementLength;}}TestpublicvoidtestPut(){MyHashmyHashnewMyHash();myHash.put(周,zhou);myHash.put(航,hang);myHash.put(宇,yu);System.out.println(myHash);}}开发方法MyHashTest - MyHash - get():publicclassMyHashTest{publicclassMyHash{/** 从数组中获取数据 */publicMyHash.Nodeget(Stringkey){returnnodes[hash(key)];}}TestpublicvoidtestGet(){MyHashmyHashnewMyHash();myHash.put(周,zhou);System.out.println(myHash.get(周));}}E04. 哈希数组扩容心法: 当底层数组到达一定阈值时需要对数组进行扩容这个阈值就是加载因子是一个浮点数。数组扩容时乘以 2 的 N 次方可以使 Hash 分布更均匀假设初始容量为16减1后15的二进制后四位为1111位与运算的结果会更均匀。武技: 开发数组扩容方法开发方法MyHashTest - MyHash - expansion():publicclassMyHashTest{publicclassMyHash{/** 数组扩容 */privatevoidexpansion(){// 创建新数组长度为当前数组长度的两倍MyHash.Node[]newNodesnewMyHash.Node[nodes.length*2];// 拷贝数据到新数组System.arraycopy(nodes,0,newNodes,0,nodes.length);// 交换引用nodesnewNodes;}}}修改方法MyHashTest - MyHash - put()每次添加新数据时判断是否需要进行扩容。publicclassMyHashTest{publicclassMyHash{/** 在数组中存储数据 */publicvoidput(Stringkey,Objectvalue){// 每次添加新数据时判断是否需要进行扩容if(elementLengthnodes.length*factor){// 数组扩容this.expansion();}// ..}}TestpublicvoidtestExpansion(){MyHashmyHashnewMyHash();myHash.put(高渐离,gao-jian-li);myHash.put(钟无艳,zhong-wu-yan);myHash.put(李元芳,li-yuan-fang);myHash.put(狄仁杰,di-ren-jie);myHash.put(老夫子,lao-fu-zi);myHash.put(安琪拉,an-qi-la);System.out.println(myHash);}}E05. 哈希数组重构心法: 哈希数组重构rehash当数组扩容后因为数组长度改变Hash 规则也改变为避免数据倾斜需要将原数组的每个元素重新 Hash 到新数组。武技: 开发哈希数组重构方法开发方法MyHashTest - MyHash - rehash()publicclassMyHashTest{publicclassMyHash{/** Hash重构操作 */privatevoidrehash(){// 创建临时数组MyHash.Node[]newNodesnewMyHash.Node[nodes.length];// 遍历原数组中的全部Node数据并进行空值保护for(MyHash.Nodenode:nodes){if(node!null){// rehash操作newNodes[hash(node.getKey())]newMyHash.Node(node.getKey(),node.getValue(),null);}}// 将临时数组的引用递交给原数组变量nodesnewNodes;}}}修改方法MyHashTest - MyHash - expansion()每次扩容结束后执行一次重构操作。publicclassMyHashTest{publicclassMyHash{/** 数组扩容 */privatevoidexpansion(){// ..this.rehash();}}}E06. 哈希碰撞冲突心法: 哈希碰撞冲突简称哈希冲突或哈希碰撞冲突类型描述键冲突两个 key 相同此时会发生值覆盖哈希冲突两个 key 不相同但它们的hash(key)值相同的情况此时视为哈希冲突1. 再哈希法心法哈希冲突解决方案之 再哈希法Rehashing原理准备多个哈希函数当使用第一个哈希函数发生冲突时就依次使用其他哈希函数直到找到一个不冲突的位置。优点不易产生聚集现象因为每次冲突后都换用不同的哈希函数来计算新的地址。缺点需要预先准备多个哈希函数增加了计算的复杂度和时间开销。适用场景对数据分布均匀性要求较高且对时间复杂度不是特别敏感的场景。2. 公共溢出表心法哈希冲突解决方案之 公共溢出表原理把哈希表分为基本表和溢出表两部分当发生哈希冲突时将冲突的元素都存入溢出表中在查找时先在基本表中查找如果未找到再到溢出表中查找。优点实现简单基本表中的数据不会受到冲突元素的影响查找基本表中的元素速度较快。缺点当冲突元素较多时溢出表的查找效率会降低。适用场景冲突元素相对较少的场景。3. 开放定址法心法哈希冲突解决方案之 开放定址法Open Addressing原理当发生哈希冲突时在哈希表中按照某种探测规则寻找下一个空闲位置来存放冲突元素删除元素时会在目标位置上添加 isDelete 标记表示该位置上的元素已经被删除了。添加元素时若发生哈希冲突则利用规则向后探测一个新的空闲位置来存储新元素。查找元素时若目标位置上不是目标元素则开始线性探测遇 isDelete 继续探测遇空闲位置停止若探测次数超过数组长度则表示该数组已无空闲位置应该扩容了。探测公式(Hash值 i) % 数组长度其中取余操作是为了避免数组越界。探测规则如下探测规则描述示例线性探测依次探测下一个位置直到找到空闲位置i 1, 2, 3, 4, 5, 6, ..二次探测以二次方的步长来探测空闲位置i 1², -1², 2², -2², ..随机探测随机一个位置i 随机数双重哈希使用另一个哈希函数来确定探测的步长优点不需要额外的存储空间来存储链表或溢出表空间利用率较高。缺点容易产生聚集现象即冲突元素会集中在某一片区域导致查找和插入的效率下降。适用场景对空间利用率要求较高且数据量相对较小、冲突不是特别频繁的场景。4. 拉链法心法哈希冲突解决方案之 拉链法Chaining也叫链地址法原理哈希表的每个位置不再只存储一个元素而是存储一个链表或其他数据结构如红黑树当发生哈希冲突时将冲突的元素插入到对应位置的链表中添加元素时若发生哈希冲突则在冲突的位置上建立一个链表并将所有冲突的元素追加到链表。查找元素时若目标位置上不是目标元素则进入链表查找或者红黑树查找。优点处理冲突简单不会产生聚集现象平均查找长度较短查找、插入和删除操作的时间复杂度相对稳定。缺点需要额外的指针域来存储链表节点的指针增加了空间开销。适用场景数据量较大、冲突较为频繁的场景如 Java8 中的 HashMap 就采用了拉链法HashMap 底层结构:Entry[] 单链表 红黑树HashMap 容量规则: 初始 16扩容时乘以 2 的 N 次方HashMap 树化阈值: 数组某位置上的链表长度超过 8HashMap 退化阈值: 数组某位置上的链表长度小于 6武技: 使用链地址法解决哈希冲突修改方法MyHashTest - MyHash - put()每次存值前若发生哈希冲突则将新元素前插到链表中。publicclassMyHashTest{publicclassMyHash{/** 在数组中存储数据 */publicvoidput(Stringkey,Objectvalue){// ..// 若发生哈希冲突// 提取当前位置上的元素即链表头元素MyHash.NodeheadNodenodes[hash(key)];// 定义当前位置上元素的next后继元素初始为nullMyHash.NodenextNodenull;if(headNode!null){// 将非空链表头备份到新链表头的后继元素变量中nextNodeheadNode;}// 设置新元素为链表头nodes[hash(key)]newMyHash.Node(key,value,nextNode);// 数组中的非null元素计数器自增elementLength;}}}修改方法MyHashTest - MyHash - get()每次取值时若发生哈希冲突则顺着链表向下寻找。publicclassMyHashTest{publicclassMyHash{/** 从数组中获取数据 */publicMyHash.Nodeget(Stringkey){// 提取当前位置上的元素即链表头元素MyHash.NodeheadNodenodes[hash(key)];if(headNode!null){// 获取到的结果不是目标key则开始链表查询while(!key.equals(headNode.getKey())){// 循环向下寻找代码headNodeheadNode.next;}}// 返回最终目标元素returnheadNode;}}/** hash冲突 */TestpublicvoidtestHashConflict(){MyHashmyHashnewMyHash();// 钟无艳的hash值分别为 (3, 0, 3)myHash.put(钟,zhong);myHash.put(无,wu);myHash.put(艳,yan);System.out.println(myHash);System.out.println(myHash.get(钟));System.out.println(myHash.get(艳));}}Java道经第1卷 - 第5阶 - 数据结构二传送门JB1-5-数据结构一传送门JB1-5-数据结构二
JB1-5-数据结构（二）
Java道经第1卷 - 第5阶 - 数据结构二传送门JB1-5-数据结构一传送门JB1-5-数据结构二文章目录S04. 哈希数据结构E01. 哈希代码函数E02. 哈希函数重写E03. 哈希数据结构1. 调用hashCode()2. 右移动运算3. 异或运算4. 取余操作5. 仿写Hash函数E04. 哈希数组扩容E05. 哈希数组重构E06. 哈希碰撞冲突1. 再哈希法2. 公共溢出表3. 开放定址法4. 拉链法S04. 哈希数据结构心法: 哈希算法 Hash Algorithm 被称为散列或哈希是一种算法MD5SHA 等都属于 Hash 算法的实现。Hash Table哈希表也叫散列表是一种以数组为基础的数据结构以键值对映射的方式存取值。E01. 哈希代码函数心法: 哈希码函数hashCode()哈希码函数 hashCode()函数来自于 Object 类即任何实例都可以调用该方法以获取其 Hash 码public native int hashCode()返回指定实例的 Hash 码即对象的唯一标识。哈希码生成策略共有 6 种生成策略可以在 JVM 运行参数中使用-XX:hashCode来设置JVM运行参数描述-XX:hashCode0返回一个随机的 Hash 值该生成策略在高并发的时候会出现自旋等待-XX:hashCode1使用某种算法对实例的内存地址进行计算后返回-XX:hashCode2固定返回 1该策略一般用于测试-XX:hashCode3对一个公共变量进行自增后返回全部实例的哈希码都使用相同的自增变量-XX:hashCode4直接返回实例的内存地址-XX:hashCode其他值利用 xor-shift 算法产生伪随机数默认值 5武技: 测试哈希码生成策略开发测试方法HashCodeTest - testHashCodeGeneratePolicy():packagehash;/** author 周航宇 */publicclassHashCodeTest{/** HashCode生成策略: -XX:hashCode2 */TestpublicvoidtestHashCodeGeneratePolicy(){System.out.println(newObject().hashCode());}}E02. 哈希函数重写心法: 判断两个实例是否相等的流程调用两个实例的hashCode()获取各自的 Hash 值若 Hash 值不等则直接返回 false以此提升比较过程的效率。若 Hash 值相等则返回两个实例的equals()比较结果。所以任何情况下重写equals()时必须同时重写hashCode()以保证 Hash 值相等这一前提条件。武技: 利用 HashMap 测试重写equals()时未重写hashCode()出现的 BUG开发实体类HashCodeTest - User:packagehash;/** author 周航宇 */publicclassHashCodeTest{DataAllArgsConstructorprivatestaticclassUser{privateIntegerid;privateStringname;}}重写方法User - equals():publicclassHashCodeTest{DataprivatestaticclassUser{Overridepublicbooleanequals(Objectobj){// 若参与比较的obj参数就是this自己则直接返回trueif(thisobj){returntrue;}// 若参与比较的obj参数不属于User类型则直接返回falseif(!(objinstanceofUser)){returnfalse;}// 若参与比较的obj参数属于User类型则强转为User类型Useruser(User)obj;// 使用 Objects.equals() 工具分别比较两个实例的id和name值// 全相等则返回true否则返回falsereturnObjects.equals(id,user.id)Objects.equals(name,user.name);}}}开发测试方法HashCodeTest - testEquals():publicclassHashCodeTest{/** 测试重写的equals()方法 */TestpublicvoidtestEquals(){Userjack01newUser(1,杰克);Userjack02newUser(1,杰克);System.out.println(jack01.equals(jack02));}}开发测试方法HashCodeTest - testHashCode():publicclassHashCodeTest{/** 测试HashMap的取值原理 */TestpublicvoidtestHashCode(){Userjack01newUser(1,杰克);Userjack02newUser(1,杰克);HashMapUser,IntegerhashMapnewHashMap();hashMap.put(jack01,100);// HashMap中的get()方法底层是根据key的hash值来获取对应value的// 若User类没重写hashCode()方法则HashMap认为jack02和jack01不是同个key值返回null// 若User类重写了hashCode()方法则hashMap认为jack02和jack01是同个key值返回100System.out.println(hashMap.get(jack02));}}重写方法User - hashCode():publicclassHashCodeTest{DataAllArgsConstructorprivatestaticclassUser{OverridepublicinthashCode(){// 使用 Objects.hash() 工具对id和name的值计算hash总和并返回returnObjects.hash(id,name);}}}重新运行测试方法HashCodeTest - testHashCode()测试HashMap的取值原理。E03. 哈希数据结构心法: 哈希结构的核心就是 Node 数组Node 用于存储一个字符串类型的键一个 Object 类型的值和一个 Node 类型的后继指针和哈希函数决定 Hash 效率的最重要函数。无论使用哈希结构进行存值还是取值都需要先使用哈希函数对元素的键进行计算定位计算的结果就是该元素在 Node 数组中的位置在最优情况下仅需一次便可找到目标元素。Node组成部分中文类型存储内容key键String存储数据的键固定为字符串结构value值E存储数据的值next后继指针NodeE存储下一个节点的内存地址尾节点的next指向null值武技HashMap 的 put() 源码解析先通过hash(key)对 key 值进行计算然后传入putVal()方法。再通过(n - 1) hash计算出 value 最终在数组中的落点索引。1. 调用hashCode()心法解析key.hashCode()调用 Object 的哈希函数计算对象的初始哈希码int 型 Hash 值为 32 位约有 40 亿种可能直接在内存中创建 40 亿长度的数组是不明智的所以不推荐直接使用这个 Hash 值需要使用扰动函数对 h 结果进行二次处理操作。2. 右移动运算心法解析(h 16)将 Hash 值右移动 16 位此时原 Hash 的高 16 位被移动到低 16 位原 Hash 的低 16 位被移出原 Hash 的高 16 位全部补充 0。3. 异或运算心法解析h ^ (h 16)将右移动结果和原 Hash 值进行异或混合原 Hash 的高 16 位信息和低 16 位信息在结果的低 16 位进行混合提升 Hash 值低 16 位的随机性以减少 Hash 冲突而结果的高 16 位信息可忽略。这样做是为了让哈希值的高位信息也能参与到桶位置的计算中从而减少哈希冲突同时简化了计算逻辑。4. 取余操作心法解析(n - 1) hash对比直接取余使用位运算取余方式来决定最终存放的位置其效率比直接取余(hash % length)要高但前提是 bitmap 的长度会被尽量保证为 2 的 N 次方。位运算取余操作从二进制的角度来看对一个数右移 N 位就相当于对这个数除以 2 的 N 次方右移 N 位后剩余的二进制数字所表示的就是商被移出的 N 个数字就是余数所以想要通过位运算获取一个数对 2 的 N 次方取余的结果直接提取该数的后 N 位数即可。减 1 操作一个 2 的 N 次方值减去 1 后位图末尾就会变为 N 个 1如 2 的 2 次方 - 1 03(0000 0011)末尾 2 个 1。如 2 的 3 次方 - 1 07(0000 0111)末尾 3 个 1。如 2 的 4 次方 - 1 15(0000 1111)末尾 4 个 1。取余操作任何数和此时结果的操作会提取 Hash 值中后 N 位如 Hash 值为 21(0001 0101)数组长度为 16减 1 后为 15(0000 1111)那么 (0001 0101) (0000 1111) (0000 0101)相当于提取了 21 的后 4 位而这后 4 位就是 21 对 16 取余的结果 5。5. 仿写Hash函数武技: 开发自定义哈希结构开发哈希类MyHashTest - MyHash:packagehash;/** author 周航宇 */SuppressWarnings(all)publicclassMyHashTest{/** 哈希类 */DatapublicclassMyHash{DataAllArgsConstructorprivateclassNode{privateStringkey;privateObjectvalue;privateMyHash.Nodenext;}/** 底层数组 */privateMyHash.Node[]nodesnewMyHash.Node[4];/** 底层数组中非null元素的个数 */privateIntegerelementLength0;/** 加载因子: 当数组当前容量超过 capacity * factor 时进行扩容 */privatefloatfactor0.75f;}}开发方法MyHashTest - MyHash - hash():publicclassMyHashTest{publicclassMyHash{/** * 计算指定元素的hash值并返回 * * param obj 待计算的元素 * return 指定元素的hash值 */publicinthash(Objectobj){// 对 obj 参数进行空值保护if(objnull){return0;}// 获取Hash值inthobj.hashCode();// 使用扰动函数和取余处理优化Hash值并返回return(h^(h16))(nodes.length-1);}}TestpublicvoidtestHash(){MyHashmyHashnewMyHash();System.out.println(myHash.hash(周));System.out.println(myHash.hash(航));System.out.println(myHash.hash(宇));}}开发方法MyHashTest - MyHash - put():publicclassMyHashTest{publicclassMyHash{/** 在数组中存储数据 */publicvoidput(Stringkey,Objectvalue){// 在数组的 hash(key) 位置上存储一个Node数据nodes[hash(key)]newMyHash.Node(key,value,nextNode);// 数组中的非null元素计数器自增elementLength;}}TestpublicvoidtestPut(){MyHashmyHashnewMyHash();myHash.put(周,zhou);myHash.put(航,hang);myHash.put(宇,yu);System.out.println(myHash);}}开发方法MyHashTest - MyHash - get():publicclassMyHashTest{publicclassMyHash{/** 从数组中获取数据 */publicMyHash.Nodeget(Stringkey){returnnodes[hash(key)];}}TestpublicvoidtestGet(){MyHashmyHashnewMyHash();myHash.put(周,zhou);System.out.println(myHash.get(周));}}E04. 哈希数组扩容心法: 当底层数组到达一定阈值时需要对数组进行扩容这个阈值就是加载因子是一个浮点数。数组扩容时乘以 2 的 N 次方可以使 Hash 分布更均匀假设初始容量为16减1后15的二进制后四位为1111位与运算的结果会更均匀。武技: 开发数组扩容方法开发方法MyHashTest - MyHash - expansion():publicclassMyHashTest{publicclassMyHash{/** 数组扩容 */privatevoidexpansion(){// 创建新数组长度为当前数组长度的两倍MyHash.Node[]newNodesnewMyHash.Node[nodes.length*2];// 拷贝数据到新数组System.arraycopy(nodes,0,newNodes,0,nodes.length);// 交换引用nodesnewNodes;}}}修改方法MyHashTest - MyHash - put()每次添加新数据时判断是否需要进行扩容。publicclassMyHashTest{publicclassMyHash{/** 在数组中存储数据 */publicvoidput(Stringkey,Objectvalue){// 每次添加新数据时判断是否需要进行扩容if(elementLengthnodes.length*factor){// 数组扩容this.expansion();}// ..}}TestpublicvoidtestExpansion(){MyHashmyHashnewMyHash();myHash.put(高渐离,gao-jian-li);myHash.put(钟无艳,zhong-wu-yan);myHash.put(李元芳,li-yuan-fang);myHash.put(狄仁杰,di-ren-jie);myHash.put(老夫子,lao-fu-zi);myHash.put(安琪拉,an-qi-la);System.out.println(myHash);}}E05. 哈希数组重构心法: 哈希数组重构rehash当数组扩容后因为数组长度改变Hash 规则也改变为避免数据倾斜需要将原数组的每个元素重新 Hash 到新数组。武技: 开发哈希数组重构方法开发方法MyHashTest - MyHash - rehash()publicclassMyHashTest{publicclassMyHash{/** Hash重构操作 */privatevoidrehash(){// 创建临时数组MyHash.Node[]newNodesnewMyHash.Node[nodes.length];// 遍历原数组中的全部Node数据并进行空值保护for(MyHash.Nodenode:nodes){if(node!null){// rehash操作newNodes[hash(node.getKey())]newMyHash.Node(node.getKey(),node.getValue(),null);}}// 将临时数组的引用递交给原数组变量nodesnewNodes;}}}修改方法MyHashTest - MyHash - expansion()每次扩容结束后执行一次重构操作。publicclassMyHashTest{publicclassMyHash{/** 数组扩容 */privatevoidexpansion(){// ..this.rehash();}}}E06. 哈希碰撞冲突心法: 哈希碰撞冲突简称哈希冲突或哈希碰撞冲突类型描述键冲突两个 key 相同此时会发生值覆盖哈希冲突两个 key 不相同但它们的hash(key)值相同的情况此时视为哈希冲突1. 再哈希法心法哈希冲突解决方案之 再哈希法Rehashing原理准备多个哈希函数当使用第一个哈希函数发生冲突时就依次使用其他哈希函数直到找到一个不冲突的位置。优点不易产生聚集现象因为每次冲突后都换用不同的哈希函数来计算新的地址。缺点需要预先准备多个哈希函数增加了计算的复杂度和时间开销。适用场景对数据分布均匀性要求较高且对时间复杂度不是特别敏感的场景。2. 公共溢出表心法哈希冲突解决方案之 公共溢出表原理把哈希表分为基本表和溢出表两部分当发生哈希冲突时将冲突的元素都存入溢出表中在查找时先在基本表中查找如果未找到再到溢出表中查找。优点实现简单基本表中的数据不会受到冲突元素的影响查找基本表中的元素速度较快。缺点当冲突元素较多时溢出表的查找效率会降低。适用场景冲突元素相对较少的场景。3. 开放定址法心法哈希冲突解决方案之 开放定址法Open Addressing原理当发生哈希冲突时在哈希表中按照某种探测规则寻找下一个空闲位置来存放冲突元素删除元素时会在目标位置上添加 isDelete 标记表示该位置上的元素已经被删除了。添加元素时若发生哈希冲突则利用规则向后探测一个新的空闲位置来存储新元素。查找元素时若目标位置上不是目标元素则开始线性探测遇 isDelete 继续探测遇空闲位置停止若探测次数超过数组长度则表示该数组已无空闲位置应该扩容了。探测公式(Hash值 i) % 数组长度其中取余操作是为了避免数组越界。探测规则如下探测规则描述示例线性探测依次探测下一个位置直到找到空闲位置i 1, 2, 3, 4, 5, 6, ..二次探测以二次方的步长来探测空闲位置i 1², -1², 2², -2², ..随机探测随机一个位置i 随机数双重哈希使用另一个哈希函数来确定探测的步长优点不需要额外的存储空间来存储链表或溢出表空间利用率较高。缺点容易产生聚集现象即冲突元素会集中在某一片区域导致查找和插入的效率下降。适用场景对空间利用率要求较高且数据量相对较小、冲突不是特别频繁的场景。4. 拉链法心法哈希冲突解决方案之 拉链法Chaining也叫链地址法原理哈希表的每个位置不再只存储一个元素而是存储一个链表或其他数据结构如红黑树当发生哈希冲突时将冲突的元素插入到对应位置的链表中添加元素时若发生哈希冲突则在冲突的位置上建立一个链表并将所有冲突的元素追加到链表。查找元素时若目标位置上不是目标元素则进入链表查找或者红黑树查找。优点处理冲突简单不会产生聚集现象平均查找长度较短查找、插入和删除操作的时间复杂度相对稳定。缺点需要额外的指针域来存储链表节点的指针增加了空间开销。适用场景数据量较大、冲突较为频繁的场景如 Java8 中的 HashMap 就采用了拉链法HashMap 底层结构:Entry[] 单链表 红黑树HashMap 容量规则: 初始 16扩容时乘以 2 的 N 次方HashMap 树化阈值: 数组某位置上的链表长度超过 8HashMap 退化阈值: 数组某位置上的链表长度小于 6武技: 使用链地址法解决哈希冲突修改方法MyHashTest - MyHash - put()每次存值前若发生哈希冲突则将新元素前插到链表中。publicclassMyHashTest{publicclassMyHash{/** 在数组中存储数据 */publicvoidput(Stringkey,Objectvalue){// ..// 若发生哈希冲突// 提取当前位置上的元素即链表头元素MyHash.NodeheadNodenodes[hash(key)];// 定义当前位置上元素的next后继元素初始为nullMyHash.NodenextNodenull;if(headNode!null){// 将非空链表头备份到新链表头的后继元素变量中nextNodeheadNode;}// 设置新元素为链表头nodes[hash(key)]newMyHash.Node(key,value,nextNode);// 数组中的非null元素计数器自增elementLength;}}}修改方法MyHashTest - MyHash - get()每次取值时若发生哈希冲突则顺着链表向下寻找。publicclassMyHashTest{publicclassMyHash{/** 从数组中获取数据 */publicMyHash.Nodeget(Stringkey){// 提取当前位置上的元素即链表头元素MyHash.NodeheadNodenodes[hash(key)];if(headNode!null){// 获取到的结果不是目标key则开始链表查询while(!key.equals(headNode.getKey())){// 循环向下寻找代码headNodeheadNode.next;}}// 返回最终目标元素returnheadNode;}}/** hash冲突 */TestpublicvoidtestHashConflict(){MyHashmyHashnewMyHash();// 钟无艳的hash值分别为 (3, 0, 3)myHash.put(钟,zhong);myHash.put(无,wu);myHash.put(艳,yan);System.out.println(myHash);System.out.println(myHash.get(钟));System.out.println(myHash.get(艳));}}Java道经第1卷 - 第5阶 - 数据结构二传送门JB1-5-数据结构一传送门JB1-5-数据结构二
