HashMap底层原理分析

技术本质

数据结构：

  • JDK7：数组＋链表

  • JDK8：数组＋链表+红黑树

算法：哈希算法

//数组：采用连续的存储单元来存储数据
//特点：查询快，插入慢

链表：创建一个简单的链表

public class Node {
    private Object data;
    public Node next;

    public  Node(Object date){
        this.data=date;
    }
    //链表：链表是一种物理存储单元上非连续、非顺序的存储结构
    //特点：插入、删除时间复杂度 o（1）查询遍历时间复杂度o（N）
    //总结：插入快、查询慢（查询时要通过遍历链表来查询）
    public static void main(String[] args) {
        Node head=new Node("sovzn");//头节点
        head.next=new Node("张三");
        head.next.next=new Node("李四");
      /*
       |sovzn|---->next---->|张三|---->----|李四|
       地址并非要连续，因为存在next引用
       */
        System.out.println(head.data);
        System.out.println(head.next.data);
        System.out.println(head.next.next.data);
    }
}

sovzn
张三
李四

Process finished with exit code 0

HashMap 源码中的链表Node（1.7中的是 Entry ）：

static class Node<K,V> implements Map.Entry<K,V> {
       final int hash; //hash值
       final K key;    //key值
       V value;        //value值
       Node<K,V> next; //next引用

       Node(int hash, K key, V value, Node<K,V> next) {
           this.hash = hash;
           this.key = key;
           this.value = value;
           this.next = next;
       }

ArrayList底层采用的就是数组：所以ArrayList具有查询快，插入慢的特点

LinkedList底层采用的是链表：而且是双向链表（next、prev），所以其特点为插入快、查询慢

//LinkedList中的Node源码
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

Hash算法

哈希算法（也叫散列），就是把任意长度值（key）通过散列算法变换成固定长度的key（地址），通过这个地址进行访问的数据结构。

它通过把关键码值映射到一个表中。位置来访问记录，以加快查询的速度。

img点击并拖拽以移动

Hashcode

Hashcode：通过字符串算出它的ASCII码，进行Mod（取模，节省空间），算出哈希表中的下标。

​ img点击并拖拽以移动

Hash碰撞

哈希冲突（碰撞） img点击并拖拽以移动 解决哈希冲突的方法：

可以通过链表，如果两个值的HashCode相等，取模后必然也相等，此时可以在产生冲突的数组位置形成链表，通过next指向新存储的值。

JDK8使用红黑树的原因

在JDK8中HashMap源码中有这一属性：

链表的阈值为8：

static final int TREEIFY_THRESHOLD = 8;

在put方法中有如下源码：

for (int binCount = 0; ; ++binCount) {
                   if ((e = p.next) == null) {
                       p.next = newNode(hash, key, value, null);
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                           treeifyBin(tab, hash);
                       break;
                   }

当链表的长度大于TREEIFY_THRESHOLD - 1（之所以是TREEIFY_THRESHOLD - 1，即7，因为链表的索引值binCount也是从0开始计算的）时。执行 treeifyBin(tab, hash);也就是让这个链表树化，将其结构转为红黑树。

将链表转为红黑树的目的：

以为在执行查询操作时，对于链表，是通过遍历的方法来进行查询的，如果链表过长的话，查询效率会非常低，而红黑树是一种树结构，查询效率要比链表高，但是对于链插入操作而言，红黑树的效率要比链表低。

总结：

常见问题

1.HashMap是如何定位下标的？

先获取Key，然后对Key进行hash，获取一个hash值，然后用hash值对HashMap的容量进行取余（实际上不是真的取余，而是使用按位与操作），最后得到下标。

2.HashMap由什么组成？

数组+单链表，jdk1.8以后又加了红黑树，当链表节点个数超过8个（m默认值）以后，开始使用红黑树，使用红黑树一个综合取优的选择，相对于其他数据结构，红黑树的查询和插入效率都比较高。而当红黑树的节点个数小于6个（默认值）以后，又开始使用链表。这两个阈值为什么不相同呢？主要是为了防止出现节点个数频繁在一个相同的数值来回切换，举个极端例子，现在单链表的节点个数是9，开始变成红黑树，然后红黑树节点个数又变成8，就又得变成单链表，然后节点个数又变成9，就又得变成红黑树，这样的情况消耗严重浪费，因此干脆错开两个阈值的大小，使得变成红黑树后“不那么容易”就需要变回单链表，同样，使得变成单链表后，“不那么容易”就需要变回红黑树。

3.HashMap往链表里插入节点的方式？

jdk1.7以前是头插法，jdk1.8以后是尾插法，因为引入红黑树之后，就需要判断单链表的节点个数（超过8个后要转换成红黑树），所以干脆使用尾插法，正好遍历单链表，读取节点个数。也正是因为尾插法，使得HashMap在插入节点时，可以判断是否有重复节点。

4.HashMap默认容量和负载因子的大小是多少？

jdk1.7以前默认容量是16，负载因子是0.75。

5.HashMap初始化时，如果指定容量大小为10，那么实际大小是多少？

16，因为HashMap的初始化函数中规定容量大小要是2的指数倍，即2，4，8，16，所以当指定容量为10时，实际容量为16。

6.哈希值相同，对象一定相同吗？对象相同，哈希值一定相同吗？

不一定。一定。 （联想hash冲突）

7.HashMap的扩容与插入元素的顺序关系？

jdk1.7以前是先扩容再插入，jdk1.8以后是先插入再扩容。

8.HashMap扩容的原因？

提升HashMap的get、put等方法的效率，因为如果不扩容，链表就会越来越长，导致插入和查询效率都会变低。

9.jdk1.8引入红黑树后，如果单链表节点个数超过8个，是否一定会树化？

不一定，它会先去判断是否需要扩容（即判断当前节点个数是否大于扩容的阈值），如果满足扩容条件，直接扩容，不会树化，因为扩容不仅能增加容量，还能缩短单链表的节点数，一举两得。

10.HashMap满足扩容条件的大小（即扩容阈值）怎么计算？

扩容阈值=容量*加载因子

假设，我们直接new hashmap，不指定任何的参数，那么默认这个hashmap的容量就为16，加载因子为0.75，当hashmap的大小大于或者等于扩容阈值即容量 * 加载因子0.75 ，也就是12时，就会把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作。

方法流程

jdk1.7

put：

  • 判断数组是否为空，如果为空进行初始化，初始化的是数组容量
  • 判断key是否为空,执行方法，key为null存在index为0的位置
  • 根据key得到hash，对key进行hashcode
  • 根据hash值和容量得到下标，indexFor方法
  • 覆盖逻辑，遍历链表，短路与先判断hash值是否相等，再判断key,value覆盖，返回oldvalue
  • addEntry(hash,key,value,i),先有（判断扩容），再根据四个值，头插法或尾插法插入

get：

  • 判断key是否为空 ，如果为空，直接取出index为0的位置的值
  • 根据key获得entry，计算hash值，得到下标，遍历链表，先比较hash再比较key，就得到了
  • 根据entry获得value

1.7和1.8流程差不多。只是在执行put和get时先判断是链表还是红黑树，并执行各自的插入和读取方法。