---

一、哈希值简介

哈希值是一个十进制的整数，有系统随机给出（就是对象的地址值，是一个逻辑地址，是模拟出来的地址，不是数据实际存储的物理地址）
在Object类中有一个方法可以获取对象的哈希值。
代码如下（示例）：

    public native int hashCode();

public native int hashCode();
native：代表该方法调用的是本地操作系统的方法

二、实例

简单的object继承类

代码如下（示例）：

//创建实例
        Object a="aaaa";
        Object b="aaaa";
        //接收值为十进制数字
        int h1=a.hashCode();
        int h2=b.hashCode();
        System.out.println(h1);
        System.out.println(h1);

我们可以看到打印的数据：

这就是一个十进制的数字

我们熟悉的toString（）方法,我们查看源码可以看到
代码如下（示例）：

    public String toString() {
        return getClass().getName() + "@" + Integer.toHexString(hashCode());
    }

我们可以看到，这实际上就是返回一个hashcode的值。

在String类中有两个特殊的哈希值

        System.out.println("重地".hashCode());
        System.out.println("通话".hashCode());

通过打印我们可以看到：

虽然字符串不一样，但是哈希值是一样的，这是一个特殊的。

这就是我们所说的哈希值，其实就是一个十进制数字，没有重写系统随机给你一个，重写了你想要什么数字就是什么数字。

该处使用的url网络请求的数据。

---

总结

提示：这里对文章进行总结：
例如：以上就是今天要讲的内容，本文仅仅简单介绍了pandas的使用，而pandas提供了大量能使我们快速便捷地处理数据的函数和方法。

什么是哈希函数？

（哈希函数，又称散列算法，英语：Hash Function）是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。
在java的String类中有hashcode方法：

当然Integer，boolean，对象等都有自己的哈希函数。
那么哈希函数的有几种构造方法呢？

• 上图是String类的哈希函数，计算出来的哈希值与字符串的字符个数和ASCII码有关。由此计算出的哈希值必唯一。
• 除此之外还有随机乘数法、ASCII码加和法、移位法。
• 还有直接定址法、除留余数、平方取中。

哈希值

哈希值又称哈希码，是哈希函数计算出来，表示一个对象的值。

• `如果两个哈希值是不相同的（根据同一函数），那么这两个散列值的原始输入一定是不相同的。
• 相同的哈希函数计算出来的哈希值是不一定唯一`的，如果两个字符串的哈希值相同，那么字符串一定是相同的。但如果用除留余数法计算出来的哈希值，哈希值相同，输入值却不同。
• 如果两个哈希值相同，两个输入值很可能(极大概率)是相同的，但也可能不同，这种情况称为“哈希碰撞”。

哈希表

哈希表的由来

• 链表是一个能够快速插入删除的数据结构，但是查找需要遍历。
• 数组是一个找到比较快的数据结构，但是必须知道数组的下标，如果不知道数组的下标，依然需要遍历。但是插入和删除也是比较麻烦。

由上述的两个问题，能不能找到一个快速插入删除、不需要数组下标的数据结构-------哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

哈希表怎么创建的？

数组是知道下标后，直接找到下标对应的值。在校园中，我们如果知道一个学生的学号，那么可以很快找到他的名字。那么基于这种知道学号就可以找出对应学生的姓名怎么实现呢？
哈希函数计算哈希值
我们的学号是唯一的，并且是一个int型的数字。我们可以根据哈希函数（除留余数法）计算出哈希值，
并以哈希值为数组下标，存储名字。
由此我们可以根据关键码值（key-value）来进行访问。

• 所以哈希表，也是采用了数组的思想，将key映射到数组中的位置。如何映射的呢？通过哈希函数计算哈希值。

但是问题来了，通过除留余数法（除以13）计算出来的哈希值相同怎么办？比如学号是5，则哈希值为5。那么序号为18，哈希值也为5。这样就产生了哈希碰撞。

哈希碰撞

回到前面，我们创建哈希表的原因是数组和链表并不能很好的满足查找一个元素（知道学号，怎么知道名字（这个例子有点憨批））。计算机的资源是有限的，不可能去创建一个很大的数组供我们去查询。在缩短数组长度，并且进行存储。肯定会有碰撞的时候。当然这个问题可以解决，如下。
哈希碰撞是可以解决的，比如用开放地址法，链地址法。

链地址法

• 我们将相同的哈希值的元素，放在一个链表上，这样不同哈希值也就有不同的链表，我们将这些链表拼成一个数组。
  
  这就是链表+数组创建的哈希表，解决了哈希碰撞的问题。

哈希查找的高效率也是有一定代价的，具体来说它是一种以空间换时间的查找算法，哈希表的构造需要合适的哈希函数，在构造哈希表时要分配跟多的空间来给记录，在记录发生冲突的时候，我们就需要一些冲突的处理方法。哈希表的构造过程也会因此更加复杂。

哈希表完整代码

哈希表完整代码

引出哈希表

设计一个写字楼通讯录，存放所有公司的通讯信息

• 座机号码作为 key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为 value
• 添加、删除、搜索的时间复杂度要求是 O(1)

我们用这种思路，将座机号码作为索引值（数组索引），公司详情作为数据元素值（数组的值）。

由于数组添加、删除、搜索元素的时间复杂度都是$o(1)$，可以达到要求。

但是这种做法有缺点。

• 空间复杂度非常大
  要保证存储所有元素，所以需要开辟一个非常大的空间。

• 空间使用率极其低，非常浪费内存空间
  就拿电话号码来说，开辟了100000000大小的空间，但是1~99999999之间有很多数字是索引值是用不到的。

其实 数组companies 就是一个哈希表，典型的 【空间换时间】。

哈希表（Hash Table）

哈希表也叫做散列表（hash有“剁碎”的意思）

哈希表是如何实现高效处理数据的？

put("Jack",666);
put("Rose",777);
put("Kate",888);

1.利用哈希函数生成 key 对应的 index【$O(1)$】

2.根据 index 操作定位数组元素【$O(1)$】

• 哈希表添加、搜索、删除的流程都是类似的

• 哈希表是【空间换时间】的典型应用

• 哈希函数，也叫做 散列函数

• 哈希表内部的数组元素，很多地方也叫 Bucket（桶），整个数组叫 Buckets 或者 Bucket Array

哈希冲突（Hash Collision）

哈希冲突 也叫做 哈希碰撞

• 2 个不同的 key，经过哈希函数计算出相同的结果

• key1 ≠ key2，hash(key1) = hash(key2)

如下图，“Rose” 不等于 “Kate”，但是经过哈希函数算出来的索引确实相同的，此时就产生了冲突。

解决哈希冲突的常见方法

• 开放定址法（Open Addressing） ✓ 按照一定规则向其他地址探测，直到遇到空桶
    线性探测：往下 一个一个顺序查找，直到遇到空桶
    平方探测：往下按照平方数顺序查找，直到遇到空桶

• 再哈希法（Re-Hashing） ✓ 设计多个哈希函数

• 链地址法（Separate Chaining） ✓ 比如通过链表将同一index的元素串起来

JDK1.8的哈希冲突解决方案

• 默认使用单向链表将元素串起来

• 在添加元素时，可能会由单向链表转为红黑树来存储元素
   比如当哈希表容量 ≥ 64 且 单向链表的节点数量大于 8 时

• 当红黑树节点数量少到一定程度时，又会转为单向链表

• JDK1.8 中的哈希表是使用 链表+红黑树 解决哈希冲突
  

思考：这里为什么使用单链表而不是双向链表？

• 每次都是从头节点开始遍历（依次比较每个元素，若有相同key则替换原本的值，若无相同key，则将新元素添加在链表尾部）

• 单向链表比双向链表少一个指针，可以节省内存空间

哈希函数

◼ 哈希表中哈希函数的实现步骤大概如下

1. 先生成 key 的哈希值（必须是整数）
2. 再让 key 的哈希值 跟 数组的大小 进行相关运算，生成一个索引值
   

◼ 为了提高效率，可以使用 & 位运算取代 % 运算【前提：将数组的长度设计为 2 的幂（$2^n$）】

将数组的长度设计为 2 的幂（$2^n$）是因为 $2^{n-1}$ 的二进制必然为全 1

10 - 1 		= 1			2^1 - 1 = 1
100 - 1 	= 11		2^2 - 1 = 3
1000 - 1 	= 111		2^3 - 1 = 7
10000 - 1 	= 1111		2^4 - 1 = 15
100000 - 1 	= 11111		2^5 - 1 = 31	

哈希值的二进制与一个全为1的二进制 &(与)，结果必然小于等于哈希值，如下图。

◼ 良好的哈希函数，让哈希值更加均匀分布 → 减少哈希冲突次数 → 提升哈希表的性能

如何生成 key 的哈希值

key 的常见种类可能有

• 整数、浮点数、字符串、自定义对象

• 不同种类的 key ，哈希值的生成方式不一样，但目标是一致的
    尽量让每个 key 的哈希值是唯一的

    尽量让 key 的所有信息参与运算（即让key的所有数字、内容参与运算）

在Java中，HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为 null

Integer 的哈希值计算

整数值当做哈希值

比如 10 的哈希值就是 10

Java 中 Integer.hashCode() 源码：

Float 的哈希值计算

将存储的二进制格式转为整数值

Java 中 Float.hashCode() 源码：

Long 的哈希值计算

Long.HashCode() ，Java源码如下：

那么， ^ 和 >>> 的作用是什么呢？

• 高32bit 和 低32bit 混合计算出 32bit 的哈希值

• 充分利用所有信息计算出哈希值

>>> 即 无符号右移，代码中的 value >>> 32 即将 value 的值无符号右移 32 位。

^ 即位运算中的异或，它的作用是：两数异或，不同为1，相同为0。

为什么用 ^ 而不用 &、| 呢？

• & 与：结果就是低32位，那高32位相当于没参数运算
• | 或：如果高32位都是1，那么结果全是1，很容易造成哈希冲突
• ^ 异：最合适的，把高32位 和 低32位，全部参与运算

>>> 无符号右移：无论正负数高位全部补0
>> 有符号右移：正数高位全部补0，负数高位全部补1

由上图可知，将 64bit 的二进制数字，无符号右移 32bit 后，左边32位必然全为 0（第二行）， 右边则为左32位的数字，(value ^ (value >>> 32)) 相当于用自己的右32位 异或 自己的左32位，最后(int)强转回了 32bit ，相当于把左边的32位全部去掉。这样可以充分利用了自身所有信息来计算哈希值。

Double 的哈希值计算

Double.HashCode() 的计算和 Long 差不多

String 的哈希值计算

思考一下：整数 5489 是如何计算出来的？

$5\ast 10^3+4\ast 10^2+8\ast 10^1+9\ast 10^0$

字符串是由若干个字符组成的

• 比如字符串 jack，由 j、a、c、k 四个字符组成（字符的本质就是一个整数）

• 因此，jack 的哈希值可以表示为 $j\ast n^3+a\ast n^2+c\ast n^2+k\ast n^0$
  等价于$[(j\ast n+a)\ast n+c]\ast n+k$（这样写效率比上面更高）

new String().hashCode() 源码如下：

由上图可知，在JDK中，乘数n为31，为什么使用31？

• JVM 会将 31 * i 优化成 (i << 5) - i

• $31\ast i=(2^5-1)\ast i=i\ast 2^5-i$

• 31 不仅仅是符合 $2^n-1$ ，它是个奇素数（既是奇数，又是素数，也就是质数）

• 素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突

• 最终选择 31 是经过观测分布结果后的选择

因此在Java中，下面两种写法完全等价。

自定义对象 的哈希值

自定义对象作为key

重写hashCode方法和equals方法

自定义对象作为 key，最好同时重写 hashCode 、equals 方法，什么时候调用？

• hashCode：计算索引的时候调用，让索引分布均匀，避免哈希冲突，即插入到数组中的哪个位置的时候；

• equals：当发生哈希冲突，比较两个对象是否相同的时候调用，即在计算完hashCode的之后

equals 用以判断 2 个key 是否为同一个key。

• 自反性
  对于任何非 null 的 x
  x.equals(x) 必须返回 true

• 对称性
  对于任何非 null 的 x、y
  如果y.equals(x)返回 true
  x.equals(y)必须返回 true

• 传递性
  对于任何非 null 的 x、y、z
  如果x.equals(y)、y.equals(z)返回 true
  那么x.equals(z)必须返回 true

• 一致性
  对于任何非 null 的 x、y
  只要 equals 的比较操作在对象中所用的信息没有被修改
  x.equals(y)的结果就不会变

hashCode

• 必须保证 equals 为 true 的 2 个 key 的哈希值一样

• 反过来 hashCode 相等的 key，不一定 equals 为 true

◼ 不重写 hashCode 方法只重写 equals 会有什么后果?

✓ 可能会导致 2 个 equals 为 true 的 key 同时存在哈希表中

不同类型的数据有可能计算出相同的哈希值，例如 String类型的数据与Double类型的数据的哈希值可能相同，此时会产生冲突，Java中解决冲突的方法为单链表与红黑树。

当两个 key 不相等，但是哈希值相等时，我们需要用 equals 方法来判断两个 key 是否为同一个key，此时就需要重写 equals。

public class Person {
	private int age;
	private float height;
	private String name;
	
	public Person(int age, float height, String name) {
		super();
		this.age = age;
		this.height = height;
		this.name = name;
	}
	
	@Override
	/**
	 * 比较两个对象是否相等
	 */
	public boolean equals(Object obj) {
		if(this == obj) return true;
		if(obj == null || obj.getClass() != getClass()) return false;
		
		Person person = (Person)obj;
		return person.age == age 
				&& person.height == height
				&& person.name==null ? name==null : person.name.equals(name);
				// 传入name若为空，则当前对象name也必须为空才为 true
				// 传入name若不为空，则调用equals方法比较即可
	}
	
	@Override
	public int hashCode() {
		int hashCode = Integer.hashCode(age);
		hashCode = hashCode * 31 + Float.hashCode(height);
		hashCode = hashCode * 31 + (name!=null ? name.hashCode() : 0);
		return hashCode;
	}

}

验证一下重写了equals和hashCode的作用：

• 由于重写 hashCode，p1、p2 哈希值必然相等，则放入 map 会去比较 key

• 由于重写 equals，p1、p2 为同一 key，则 p1 会覆盖 p2

public static void main(String[] args) {
	Person p1 = new Person(18, 1.75f, "jerry");
	Person p2 = new Person(18, 1.75f, "jerry");
	// 由于重写 hashCode(),p1、p2哈希值必然相等
	
	Map<Object, Object> map = new HashMap<>();
	map.put(p1, "abc");
	map.put("test", "bcd");
	// 由于 p1 与 p2 哈希值相等
	// 会比较 p1 与 p2 是否为同一key
	// 由于重写 equals(), p1、p1为同一key
	map.put(p2, "ccc"); // 同一 key 则覆盖,map里的元素数量不增加

	System.out.println(map.size()); // 2
}

• 若只重写 hashCode
  由于重写 hashCode，p1、p2 哈希值必然相等，则放入 map 会去比较 key
  但是 equals 默认比较地址，p1、p2地址不同，不为同一 key，因此 map.size() 为3

• 若只重写 equals
  由于没有重写 hashCode，p1、p2 哈希值大概率不相等(有极小可能相等)
  一般情况下，p1、p2哈希值不相等，map.size()值应当为3
  若是真遇到了哈希值相等的情况，由于重写了 equals，map.size()值为2

结论就是，重写 hashCode 与 equals 是最稳妥的做法。

关于使用%来计算索引

◼ 如果使用%来计算索引

• 建议把哈希表的长度设计为素数（质数）

• 可以大大减小哈希冲突

10%8 = 2     10%7 = 3
20%8 = 4     20%7 = 6
30%8 = 6     30%7 = 2
40%8 = 0     40%7 = 5
50%8 = 2     50%7 = 1
60%8 = 4     60%7 = 4
70%8 = 6     70%7 = 0

◼ 下表格列出了不同数据规模对应的最佳素数，特点如下

• 每个素数 略小于 前一个素数的 2倍
• 每个素数尽可能接近2的幂（$2^n$）
  

易错点总结

• 哈希值相等，根据哈希函数求的索引必然相等

• 哈希值不相等，根据哈希函数求的索引有可能相等
  原因是hash_code(key) & (table.length - 1)取模运算可能会遇到相等的情况
  可以理解为 2 % 3 = 2，5 % 3 = 2，2 和 3 不相等，%3 的结果却相等

• HashMap 的 key 必须实现 hashCode、equals 方法，也允许 key 为null