[数据结构与算法]【数据结构与算法】第九篇：哈希表原理

一. HashMap的引入背景

上节集合，映射我们实现了用红黑树实现了映射（TreeMap）;虽然红黑树能够很好的实现映射的各项功能，但是红黑树自身有很多局限性，比如：
1.TreeMap中的key必须是具备可比较性的
2.元素的分布是有顺序的。
但是在现实很多需求中，是不要求 Map的key必须有顺序的,并且不要求key必须具备可比较性。
哈希表就能很好的解决这两个问题，并且能使平均时间复杂度达到O(1).

二. HashMap原理

其实哈希表就是用一个数组进行实现的，具体的场景可以看以下是实例：
? 设计一个写字楼通讯录，存放所有公司的通讯信息
座机号码作为 key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为 value
添加、删除、搜索的时间复杂度要求是 O(1)
其实用数组解决这个问题十分简单，只要设计一个足够大的数组使它能够容纳所有的8位数，然后以座机号码作为数组下标依次存入就可以了。

private Company[] companies = new Company[100000000];
public void add(int phone, Company company){
	companies[phone] = company;
}
public void remove(int phone){
	companies[phone] = null;
}
public Company get(int phone){
	return companies[phone];
}

这里的Company[]数组就是一个哈希表。
但是不足之处是，虽然时间复杂度变成了O(1),但是空间复杂度却十分的高。这也是哈希表的一个典型特征：时间换空间

哈希表的具体实现机制还得看以下这张图

比如说加入以下元素：
put(“Jack”, 666);
put(“Rose”, 777);
put(“Kate”, 888);

在转换机制中，哈希函数（一种转换函数），会接收Key,然后通过的一定转换规则将key生成相应的索引，然后将key,value放入对应索引的数组空间。

1. 添加、搜索、删除的流程都是类似的
   2.利用哈希函数生成 key 对应的 index【O(1)】
   3.根据 index 操作定位数组元素【O(1)】

哈希表是【空间换时间】的典型应用
哈希函数，也叫做散列函数
哈希表内部的数组元素，很多地方也叫 Bucket（桶），整个数组叫 Buckets 或者 Bucket Array

三.哈希冲突（Hash Collision）

1.Hash Collision的造成原因

哈希冲突其实即使不同的值在经过哈希函数转换后产生的索引相同，就造成的哈希冲突的现象。

1. 哈希冲突也叫做哈希碰撞
2. 2 个不同的 key，经过哈希函数计算出相同的结果
3. key1 ≠ key2 ，hash(key1) = hash(key2)

2Hash Collision解决方法

主要的解决办法大体分为两种：
1. 开放定址法（Open Addressing）
? 按照一定规则向其他地址探测，直到遇到空桶
2. 再哈希法（Re-Hashing）
? 设计多个哈希函数
3. 链地址法（Separate Chaining）
? 比如通过链表将同一index的元素串起来

我们经常使用就是第二种方法，链地址法。
在有不同元素的索引相同时，我们用来链表或者红黑树将重复元素串起来。
由于红黑树和链表的复杂度相差很多，所以我们可以设置限定个数，在哈希冲突不是很多的时候用链表进行连接，当数目大于某个值的时候，我们将结构转化为红黑树。

三.哈希函数原理

1.哈希函数的转换机制

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

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

对数组长度取余得到的索引肯定是0-table.length~1

public int hash(Object key) {
	return hash_code(key) % table.length;
}

为了提高效率还可以将%换成&运算符

public int hash(Object key) {
	return hash_code(key) & (table.length - 1);
}

2.Integer 的哈希值计算

整数的哈希值就是整数本身

  @Override
    public int hashCode() {
        return Integer.hashCode(value);
    }

3.Float 的哈希值计算

对于浮点数的哈希值的计算，底层是调用java自己带有的方法floatToIntBits（），进行转换。这个方法的原理是将浮点数在内存中对应的二进制数，进行运算，转化成它对应的整数作为哈希值。

public static void main(String[] args）{
        float f=12.5f;
        Float.hashCode(f)
    }

源码

 public static int hashCode(float value) {
        return floatToIntBits(value);
    }

4.Long 的哈希值计算

计算哈希值有一个基本的原则：尽量使所有位数都参与运算
Long类型的变量占8个字节，64个比特位，我们可以使这个变量右移32位，然后与自身取异或。这样可以保证Long类型的变量前32位和后32位都混合参与了运算。这样产生的哈希值不容易产生哈希冲突。

源码

 public static int hashCode(long value) {
        return (int)(value ^ (value >>> 32));
    }

1.>>> 和 ^ 的作用是:
(1)高32bit 和 低32bit 混合计算出 32bit 的哈希值
(2)充分利用所有信息计算出哈希值

5.Double 的哈希值计算

Double类型的哈希值的计算，就是利用doubleToLongBits()方法将double类型的数据对应的内存中的二进制数转化成它对应的长整型数。然后再计算长整型数据的哈希值。

  public static int hashCode(double value) {
        long bits = doubleToLongBits(value);
        return (int)(bits ^ (bits >>> 32));
    }

6.String 的哈希值计算

引例
整数 5489 是如何计算出来的？
5 ? 10³ + 4 ? 10² + 8 ? 10¹ + 9 ? 10⁰
字符串的哈希值也是这个原理：
由于字符本质上也是一个数，所以字符串的哈希值的计算也可类似于引例中的计算方式。
? 字符串是由若干个字符组成的
比如字符串 jack，由 j、a、c、k 四个字符组成（字符的本质就是一个整数）
因此，jack 的哈希值可以表示为 j ? n³ + a ? n² + c ? n¹ + k ? n⁰ ，等价于 [ ( j ? n + a ) ? n + c ] ? n + k.(这里这样等价，是可以避免重复计算n*n造成的时间浪费)
这里的n一般取31（java官方）因为：

1. 31不仅仅是符合2^n – 1，它是个奇素数（既是奇数，又是素数，也就是质数）
2. 素数和其他数相乘的结果比其他方式更容易产成唯一性，减少哈希冲突
3. 最终选择31是经过观测分布结果后的选择

四.自定义对象的哈希值

我们先自定义一个Person类，重写equals()和hashcode()方法

public class Person implements Comparable<Person> {
	private int age;   // 10  20
	private float height; // 1.55 1.67
	private String name; // "jack" "rose"
	
	public Person(int age, float height, String name) {
		this.age = age;
		this.height = height;
		this.name = name;
	}
	
	@Override
	/**
	 * 用来比较2个对象是否相等
	 */
	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));
	}
	
	@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;
	}

	@Override
	public int compareTo(Person o) {
		return age - o.age;
	}
}

我们定义Person对象，传入age ,height, name。对于自定义类hashcode()计算方法是我们将各个成员变量的哈希值计算出来，然后加在一起作为成员变量的哈希值。

特别注意：这里一定要重写equals(）方法，因为对于两个相同的对象Person p1=new Person(10,1.55,“jack”);
Person p2=new Person(10,1.55,“jack”);如果不重写equals()方法，就会判定这两个对象不相等，因为p1,p2的内存地址不相等。
重写equals()方法是他只要个成员变量分别相等就判定这两个对象相等，更加贴合实际。