大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
上期使用 红黑树 实现映射结构,这样的结构满足 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
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中哈希一般是希望自己写算法的。随便返回什么都可以。如果什么也不写的话就会返回地址。如果自己写,最简单的做法是把所有字段拼起一个长串做个hash值。
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
方法是怎么做到的。