Java--HashMap底层实现详解-2

·存储数据过程put(key,value)
  明白了HashMap的基本结构后，我们继续深入学习Hasap如何存储数据。此处的核心是如何产生hash值，该值用来对应数组的存储位置。

HashMap存储数据过程示意图.png

  我们的目的是将”key-value两个对象”成对存放到HashMap的Entry[]数组中。参见以下步骤：
  (1)获得key对象的hashcode
    首先调用key对象的hashcode()方法，获得hashcode。

  (2)根据hashcode计算出hash值(要求在[0, 数组长度-1]区间)
    hashcode是一个整数，我们需要将它转化成[0, 数组长度-1]的范围。我们要求转化后的hash值尽量均匀地分布在[0, 数组长度-1]这个区间，减少“hash冲突”
    i. 一种极端简单和低下的算法是：
    hash值 = hashcode/hashcode;
    也就是说，hash值总是1。意味着，键值对对象都会存储到数组索引1位置，这样就形成一个非常长的链表。相当于每存储一个对象都会发生“hash冲突”，HashMap也退化成了一个“链表”。

    ii. 一种简单和常用的算法是(相除取余算法)：
    hash值 = hashcode%数组长度
    这种算法可以让hash值均匀的分布在[0, 数组长度-1]的区间。早期的HashTable就是采用这种算法。但是，这种算法由于使用了“除法”，效率低下。JDK后来改进了算法。首先约定数组长度必须为2的整数幂，这样采用位运算即可实现取余的效果：hash值 = hashcode&(数组长度 - 1)。

iii. 如下为我们自己测试简单的hash算法：
【示例9】测试hash算法

public class Test {
    public static void main(String[] args) {
        int h = 25860399;
        int length = 16;//length为2的整数次幂，则h&(1ength-1)相当于对length取模
        myHash(h, length);
    }
    /**
      * ＠param h 任意整数
      * ＠param length 长度必须为2的整数幂
      * @return
      */
    public static int myHash(int h, int length) {
        System.out.println(h&(length-1));
        //length为2的整数幂情况下，和取余的值一样
        System.out.println(h%(length-1);//取余数
        return h&(length-1);
    }
}

  运行如上程序，我们就能发现直接取余(h%length)和位运算(h&(length-1))结果是一致的。事实上，为了获得更好的散列效果，JDK对hashcode进行了两次散列处理(核心目标就是为了分布更散更均匀)，源码如下：

hash算法源码.png

  (3)生成Entry对象
    如上所述，一个Entry对象包含4部分：key对象、value对象、hash值、指向下一个Entry对象的引用。我们现在算出了hash值。下一个Entry对象的引用为null。

  (4) 将Entry对象放到table数组中
    如果本Entry对象对应的数组索引位置还没有放Entry对象，则直接将Entry对象存储进数组；如果对应索引位置已经有Entry对象，则将已有Entry对象的next指向本Entry对象，形成链表。

总结如上过程：
  当添加一个元素(key-value)时，首先计算key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同－hash值的元素的后面，他们在数组的同一位置，就形成了链表，同一个链表上的Hash值是相同的，所以说数组存放的是链表。JDK8中，当链表长度大于8时，链表就转换为红黑树，这样又大大提高了查找的效率。

·取数据过程get(key)
Java--HashMap底层实现详解-3