数据结构之 HashMap 系列

写在前面：

小伙伴儿们，大家好！今天来分享一波个人对HashMap相关的个人见解！

一、HashMap 概述

HashMap是基于哈希表的Map接口实现，是以key-value存储形式存在，主要用来存放键值对。
哈希表的基本结构就是数组+链表
1：数组：占用空间连续，寻址容易，查询速度快，但是，增加和删除效率非常低
2：链表：占用空间不连续，寻址困难，查询速度慢，但是，增加和删除效率非常高。

HashMap的关键特点：

无序、key唯一、value允许重复、key和value允许为null

二、HashMap的数据结构

【在jdk1.7的结构】

在JDK 1.7之前的HashMap的数据结构由数组+单向链表组成的，数组是HashMap的主体，链表则是主要为了节解决哈希碰撞(两个对象调用的hashCode方法计算的哈希码值一致导致计算的数组索引值相同)而存在的问题。

在向单向链表中插入元素时，采用**【头插法】**将元素插入链表

【在jdk1.8的结构】

JDK1.8之后的HashMap的数据结构由数组+单向链表+红黑树组成的，当链表长度大于阈值（或者红黑树的边界值，默认为8）并且当前数组的长度大于64时，此时此索引位置上的所有数据改为使用红黑树存储。从而一定程度避免了哈希碰撞的问题。

在向单向链表中插入元素时，采用**【尾插法】**将元素插入链表

解决哈希冲突的常见方法：

1. 链地址法：哈希表中的每个Node节点都有一个next指针，构成一个单向链表。被分配到同一个下标位置上的多个Node节点（发生哈希冲突），可以通过存入同一个单向 链表来解决这个问题。
2. 开放定址法：一旦发生哈希冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
3. 建立公共溢出区：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。
4. 再哈希法：再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。

三、HashMap数据结构定义

Node 类型的数组

public class HashMap{
    // 每个Node既保存一个KV键值对，同时也是链表中的一个节点
    Node<K,V>[] table; 
}

链表节点类 Node

public class HashMap{
    
    // 静态内部类Node
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; // 哈希值
        final K key; // 键
        V value; // 值
        Node<K,V> next; // 下一个节点(由于只拥有next，所以该链表为单向链表)
    }
}

四、储存数据过程 put(key,value)

保存【K，V】键值对的数组，每个【K，V】Z键值对都会被封装一个Node对象

数组容量决定了HashMap对内存的占用大小

当添加一个元素的时候，首先计算key的hash值，以此确定数组中的位置，但是可能存在同一个hash值得元素已经被放在数组同一位置，这时就添加到同一hash值元素的 后面，他们在数组同一个位置，就形成了链表，同一个链表上的hash值是相同的，所以数组存放的列表，JDK8中，当链表长度大于8时，链表就转换成红黑树，这样大大提高查询效率。

HashMap的hash函数

HashMap通过新添加元素key的hashCode()方法，计算一个hash值，然后通过这个hash值计算位置下标。

static final int hash(Object key) {
    int h;
    // 通过key的hashCode()方法返回的哈希值与它的高16位进行异或运算
    // 作用：计算出的hash值，在计算下标位置时，会更“散列”，减少哈希冲突
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

下标计算：

• JDK1.7 ：hash % 数组长度
• JDK1.8 ：(数组长度 - 1) & hash

HashMap的数组容量
首先HashMap在第一次添加KV键值对时，如果数组为空，则将数组容量按照默认初始化容量16进行扩容。默认初始化容量DEFAULT_INITIAL_CAPACITY通过位运算1<<4计算得出。

public class HashMap{
    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    // 添加键值对
    final V putVal(int hash, K key, V value) {
        Node<K,V>[] tab; // 数组
        Node<K,V> p; int n, i;
        
        if ((tab = table) == null || (n = tab.length) == 0)
            // 如果数组为空，则该数组扩容为16
            n = (tab = resize()).length;
    }
}

每次添加KV键值对时，都会通过hash()函数，按照key的hashCode()计算出来的hash值，按照**(n-1)&hash的方式计算出一个下标，该下标代表当前【KV键值对】在数组中的保存位置。这种计算下标的方式，作用等同于hash值 与 数组长度进行取模**运算。

public class HashMap{
    
      // 添加键值对
      final V putVal(int hash, K key, V value) {
        Node<K,V>[] tab; // 数组
        Node<K,V> p; // 临时节点
        int n, i; // n代表数组长度，i代表元素下标位置
        
        // 根据当前元素的key的hash值，计算该元素在数组tab中的下标位置i
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
      }
}

五、链表和红黑树用途和转换

1.链表转换为红黑树

//此处遍历链表
for (int binCount = 0; ; ++binCount) {
    //遍历到链表最后一个节点
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        //如果链表元素个数大于等于TREEIFY_THRESHOLD
        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            //红黑树转换逻辑
            treeifyBin(tab, hash);
        break;
    }
    if (e.hash == hash &&
        ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

	static final int MIN_TREEIFY_CAPACITY = 64;
    static final int UNTREEIFY_THRESHOLD = 6;
    /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */

// 链表转换为红黑树
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        
          // 数组为空或者数组的长度n小于64
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

可以看到在treeifyBin方法中并不是简单地将链表转换为红黑树，而是先判断table的长度是否大于64，如果小于64，就通过扩容的方式来解决，避免红黑树结构化.

链表长度大于8有两种情况：

• table长度足够，hash冲突过多
• table长度太小,但是在计算table下标的时候,导致很多hash不一致的key计算的下标一致

所以扩容后链表长度变短，读写效率自然提高。另外，扩容相对于转换为红黑树的好处在于可以保证数据结构更简单。并不是链表长度超过8就一定会转换成红黑树，而是先尝试扩容。

2.红黑树转换为链表

基本思想：当红黑树中的元素减少并小于一定数量时，会切换回链表。

而元素减少有两种情况：

• 调用map的remove方法删除元素
• resize的时候，对红黑树进行了拆分

总结：

1、hashMap并不是在链表元素个数大于8就一定会转换为红黑树，而是先考虑扩容，扩容达到默认限制后才转换

2、hashMap的红黑树不一定小于6的时候才会转换为链表，而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。

写在最后~~

麻烦各位看官，动动小手给个免费的点赞，小小的一个小红心…