发布网友
发布时间：2022-11-18 15:57
共1个回答
热心网友
时间：2024-10-13 11:09
上期使用 红黑树 实现映射结构，这样的结构满足 Key 必须具备可比性，元素有顺序地分布 这两个特点。在实际的应用场景中，存在结构中的 元素是不需要有序的，并且 Key 也不具备可比较性 ，哈希表完全满足这样的应用场景。
比如设计一个公司的通讯录，存放所有员工的通讯信息，就可以拿手机号作为 index，员工的名称、职位等作为 value。用哈希表的方式可以将添加、删除和搜索的时间复杂度控制在 O(1)。
这时创建一个数组，手机号作为 index，然后存放 value。这样能将复杂度控制在 O(1)，但是这种 空间换时间 的方式也造成了一些其他问题，比如空间复杂度大（需要更多的空间），空间使用率极其低，非常浪费内存空间。
哈希表 就是空间换时间的处理方式，但是做了优化，在空间和时间两个纬度中达到适当的平衡。
哈希表也叫做散列表，整体结构就是一个数组 ，哈希表会将 key 用哈希函数处理之后返回 hash（哈希值），hash 就是哈希表中的 index这样的处理方式就可以满足搜索时间是 O(1)，这样的处理方式就可以满足搜索时间是 O(1)。因为哈希表中的 key 可能不具备可比较性，所以要做哈希处理。
在执行哈希函数之后返回的 hash，可能会出现相同的情况 ，这样的情况就是 哈希冲突 。解决哈希冲突常见的方法有这三种：
JDK1.8 解决哈希冲突的方式就是使用链地址法，其中的链表就是通过链表+红黑树的组合来实现 。比如当哈希表中的容量大于等于 64，并且单向链表的节点数大于 8 时，转换为红黑树，不满足这个条件时就使用单向链表。
哈希函数 是生成哈希值的实现方法，哈希函数的实现步骤大致分为两步：
hash_code 是生成哈希值的函数，也可以直接用 JAVA 中的标准函数 hashCode() 。
这里可以用 & 位运算替换 % 运算，来提高效率。因为 & 位运算是二进制运算，所以在设计数组的时候，需要将数组的长度设计为 2 的幂次方。
一个良好的哈希函数，可以让生成的哈希值分布更加均匀，减少哈希冲突的次数，最终可以提升哈希表的性能。
Key 的常见类型可能有证书、浮点数、字符串或者自定义对象，不同的类型生成哈希值的方式也会不一样，但是目标是一致的，就是 尽量让每个 Key 的哈希值唯一，尽量让 Key 中的所有信息参与运算 。
比如在 Java 中， Long 的哈希值实现如下代码：
这里的 >>>和 ^ 就是将高 32 bit 和低 32 bit 混合计算出 32 bit 的哈希值。
在计算字符串的哈希值时，可以将字符串拆解成若干个字符，比如 jack，将它拆解成 j、a、c、k（字符的本质就是一个整数，所以 jack 的哈希值可以表示为 j * n3 + a * n2 + c * n1 + k * n0，表达式也可以写成 [(j * n + a) * n + c] * n + k，代码实现如下：
看上面代码时，可以发现，表达式中的 n 使用的是 31 这个数字，那么为什么用 31 呢？
因为 31 不仅符合 22 - 1 , 而且它还是个奇素数（既是技术，又是素数，还是质数），素数和其他数相乘的结果比其他方式更容易产生唯一性，减少哈希冲突。
JDK 中，乘数 n 也是用 31，31 也是经过观测分布结果后的选择，关于 31 的变体可以有以下几种：
31 * i = (25 - 1) * i = i * 25 - i = (i << 5) - i
Copyright © 2019-2022 51dongshi.com 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
