图文并茂深入学习哈希表 (上)

 一、哈希表简介

哈希表也称为散列表

底层是由数组+单链表+红黑树实现

编辑

添加、搜索、删除的流程

（1）利用hash函数生成key对应的数组索引 index O（1）

（2）根据index操作定位数组元素 O（1）

哈希表采用 空间换时间的思路

1. 哈希冲突

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

解决方法：

(1) 开放定址法

按照一定规则向其他地址探测，直到遇到空

• 线性探测
  
• 平方探测
  

(2) 再哈希法

设计多个哈希函数

(3) 链地址法

比如通过链表将同一index的元素串接起来

(4) 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。数位叠加可以有移位叠加和间界叠加两种方法。移位叠加是将分割后的每一部分的最低位对齐，然后相加；间界叠加是从一端向另一端沿分割界来回折叠，然后对齐相加。

(5) 随机数法：选择一随机函数，取关键字的随机值作为散列地址，即 H(key)=random(key)其中 random 为随机函数,通常用于关键字长度不等的场合。

(6) 除留余数法：取关键字被某个不大于散列表表长 m 的数 p 除后所得的余数为散列地址。即 H(key) = key MOD p,p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对 p 的选择很重要，一般取素数或 m，若 p 选的不好，容易产生同义词。

2.jdk1.8的哈希冲突解决方案

• 默认使用单向链表将元素串起来
  
• 在添加元素时，可能会由单向链表转为红黑树来存储元素

• 比如当哈希表容量>=64且单向链表的节点数量大于8时
  

• 当红黑树节点数量少到一定程度时，又会转为单向链表
  
• JDK1.8中的哈希表是使用链表+红黑树解决哈希冲突
  

编辑

为什么使用单链表？

(1) 当通过哈希函数计算key对应的索引后，根据索引遍历所有key如果key是相同的则会覆盖key对应的value值，所以每次都要添加新元素都要从头遍历一遍链表并把新元素插入链表尾部，使用单向链表即可解决

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

二、哈希函数

1.哈希表中哈希函数的实现步骤：

（1）先生成key的哈希值(必须是整数)

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

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

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

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

进行&运算可以使得key的哈希值一定小于 table.length-1也就是数组下标长度，不会造成下标越界

良好的哈希函数

让哈希值更加均匀分布->减少哈希冲突的次数->提升哈希表的性能-

2.如何生成key的哈希值？

key的常见种类可能有：

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

不同种类的key，哈希值的生成方式不一样，但是目的相同

• 尽量让每个key的哈希值是唯一的
  
• 尽量让key的所有信息参与运算(可以使得key的哈希值更大概率不相同)
  

Java中哈希值必须是int类型

（1）整数 整数本身作为哈希值

（2）浮点数

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

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

（3）Long类型

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

（4）Double类型

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

>>>和 ^ 的作用

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

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

（5）字符串的哈希值

字符串由若干个字符组成

比如字符串hash，由h、a、s、h四个字符组成(字符串的本质就是一个整数)

因此hash的哈希值可以表示为h* n ^ 3 + a * n ^ 2 + s * n + h ，(会有重复计算 比如 n*n 计算后在计算n*n*n时又进行计算了) 等价于 ([h * n + a ] * a + s ) * n +h

在JDK中乘数n为31

31是一个奇素数，JAM会将31 * i 优化成(i << 5) - i

（6）自定义对象

新建一个Person类

class Person{
     //姓名
     private  String name;
     //身高
     private float height;
     //年龄
     private  int age;
     public Person() {
     }
     public Person(String name, float height, int age) {
         this.name = name;
         this.height = height;
         this.age = age;
     }
 }
 public class Demo01 {
  public static void main(String[] args) {
        Person p1 = new Person("张三",1.7f,20);
         Person p2 = new Person("张三",1.7f,20);
         System.out.println(p1.hashCode());
         System.out.println(p2.hashCode());
         Map<Object,Object> map = new HashMap<>();
         map.put(p1,1);
         map.put(p2,2);
         System.out.println(map.size());
     }
 }
 /**
  *运行结果: 2129789493
  *         668386784
  *         2
  */

我们p1和p2对象的属性值完全相同，这个时候我们如果规定属性值相同就是同一个key，但是我们发现直接调用hashCode()方法，输出的结果是不同的，map中有两个键值对

这该如何解决？

一般我们会在类中重写hashCode()方法

@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;
 }

这样p1和p2对象哈希值就相同了，实际上我们在重写hashCode()方法时，jdk会自动帮我们重写

@Override
 public int hashCode() {
     return Objects.hash(name, height, age);
 }

点进hash()方法->hashCode()方法我们发现 jdk源码也是这样处理的

//将传入的值都放在object类型的数组a中
 public static int hashCode(Object a[]) {
     if (a == null)
         return 0;
     int result = 1;
 //循环遍历数组元素,计算每个元素的hashCode值 再计算整个数组a的哈希值
     for (Object element : a)
         result = 31 * result + (element == null ? 0 : element.hashCode());
     return result;
 }

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

为什么需要实现equals方法？

我们之前通过重写hashCode()方法使得自定义的Person对象再属性完全相同时，其哈希值是相同的，但是这个时候map集合添加p1和p2，能否实现p2覆盖p1也就是所谓的去重呢？

System.out.println(p1.hashCode());
 System.out.println(p2.hashCode());
 Map<Object,Object> map = new HashMap<>();
 map.put(p1,1);
 map.put(p2,2);
 System.out.println(map.size());
 //运行结果:-407057726
 //        -407057726
 //         2

运行结果发现map集合的大小为2，表明没有去重p1和p2都加入了

这是为什么呢？

实际上许多人刚学哈希表时都有一个误区，那就是哈希值相同就代表是相同的元素，这是不对的，因为我们前文刚说了哈希冲突，在key不同的情况下通过hash方法计算的哈希值可能相同，那么相同的key哈希值必定相同了，也就是说我们重写hashCode()方法只能计算key的哈希值并保证相同的key哈希值是相同的，其所对应的数组索引也必定相同。那么发生哈希冲突，使用单链表解决时，我们时从头到尾进行比较来判断key是否相同。简单来说通过比较哈希值来判断是否是相同的key，这是不靠谱的。

如何进行key的比较呢？

很容易想到 == 或 equals

如果是==则是比较内存地址，在比较对象时我们肯定不会选择==进行比较，因为两个新new的对象地址不相同，但是属性完全相同，因此我们选用equals方法进行比较

//在Person类中重写equals方法
 @Override
 public boolean equals(Object obj) {
     //如果内存地址相等则两个元素相等就是自己本身
     if (this == obj) return true;
      //如果obj为空 或者obj与本类Person不是同一个类，那么也必定不同
     if (obj == null || getClass() != obj.getClass()) return false;
       //传来的obj对象是Person类的实例
     Person person = (Person) obj;
     //比较height
     if (Float.compare(person.height, height) != 0) return false;
     //比较年龄
     if (age != person.age) return false;
     // 比较name
     return name != null ? name.equals(person.name) : person.name == null;
 }

此时我们再进行map集合添加p1和p2，就能够实现去重辣！！！

三、总结：

hashCode()方法是计算哈希值，保证相同元素的哈希值相同然后找数组索引

equals()方法是当发生哈希冲突时，判断两个key是否相等

注意点：计算哈希值时为了找数组索引，哈希值相同索引必相同，哈希值不同索引也可能相同，

（因为我们计算出哈希值后还需要与数组大小进行 & 运算）

图解重写hashCode与equals方法后map添加p1、一个与p1有相同哈希值的key1、p2 三对键值对

的过程

（1）map集合添加键值对(p1,123), 哈希函数计算出p1的哈希值再通过与数组长度进行&运算，假设求出索引为1，并发现此索引数据为空，然后添加数据

编辑

（2）map集合继续添加键值对（"key1",456），哈希函数计算哈希值并进行&运算发现"key1"对应的数组索引也是1,然后通过索引知道此时该索引存在数据，从头到尾进行遍历并比较，发现"key1"与p1不相同，添加键值对（"key1",456）

编辑

（3）map集合继续添加键值对（p2,789），哈希函数计算哈希值并进行&运算发现p2对应的数组索引是1,然后通过索引知道此时该索引存在数据，从头到尾进行遍历并比较，发p2与p1相同，进行覆盖

编辑

以上就是重写hashCode和equals方法后哈希表解决哈希冲突及相同key的过程