数据结构与算法-基础（十八）哈希表

上期使用 红黑树 实现映射结构，这样的结构满足 Key 必须具备可比性，元素有顺序地分布 这两个特点。在实际的应用场景中，存在结构中的 元素是不需要有序的，并且 Key 也不具备可比较性 ，哈希表完全满足这样的应用场景。

成都创新互联专注为客户提供全方位的互联网综合服务，包含不限于成都做网站、网站建设、象山网络推广、小程序开发、象山网络营销、象山企业策划、象山品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们最大的嘉奖；成都创新互联为所有大学生创业者提供象山建站搭建服务，24小时服务热线：13518219792，官方网址：www.cdcxhl.com

比如设计一个公司的通讯录，存放所有员工的通讯信息，就可以拿手机号作为 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

关于Java的地址值和哈希值？

1、hashCode的存在主要是用于查找的快捷性，如Hashtable，HashMap等，hashCode是用来在散列存储结构中确定对象的存储地址的；

2、如果两个对象相同，就是适用于equals(java.lang.Object) 方法，那么这两个对象的hashCode一定要相同；

3、如果对象的equals方法被重写，那么对象的hashCode也尽量重写，并且产生hashCode使用的对象，一定要和equals方法中使用的一致，否则就会违反上面提到的第2点；

4、两个对象的hashCode相同，并不一定表示两个对象就相同，也就是不一定适用于equals(java.lang.Object) 方法，只能够说明这两个对象在散列存储结构中，如Hashtable，他们“存放在同一个篮子里”

JAVA中哈希码具体是什么？

哈希其实只是一个概念，没有什么真实的指向。它的目的是保证数据均匀的分布到一定的范围内。所以不同数据产生相同的哈希码是完全可以的。

java中哈希一般是希望自己写算法的。随便返回什么都可以。如果什么也不写的话就会返回地址。如果自己写，最简单的做法是把所有字段拼起一个长串做个hash值。

关于java的哈希值

HASH

是散列表的基础计算方法，Java

内置了

hash

的支持，java.lang.Object

默认是通过对象在内存的地址计算出来的，所以每个对方都是唯一的

hash，但是当我们创建我们自己的对象类时，我们根据需要和业务逻辑来决定是否提供自己的

hashcode

和

equals

方法。

多个对象的

hash

可能重复，这是正常的，重复的对象在

hash

table

中是分配在同一个槽

(一个可以通过计算直接跳过那个位置的数组)中，会再通过

equals

对比

(在这个槽中的

hash

code

都相同的一个链表中逐一

equals

比较

key)

找到那个对象。

所以逻辑上是否相同是通过

equals

来计算的，而且

equals

相同的两个对象，它们的

hash

也应该相同，如果你不能保证这点，那就说明你的

hashcode

和

equals

方法不是使用相同的算法。

一个对象是否存在不是通过

hash

code

来判断的，而是

equals。

a

==

b

的话，a.equals

(b)

肯定成立，但反过来就不一定。因为

a

==

b

比较的是对象的地址，只有同一个对象才能成立，equals

比较的是逻辑角度上的相等性。

看

String

或其它一个

JRE

自带的类的

hashcode

和

equals

方法是怎么做到的。

当前文章：java计算哈希值代码 java的哈希值
标题URL：http://scyanting.com/article/ddosijp.html