Java之HashMap实现原理

2017-03-04 本文已影响0人 dotaer_shashen

目录
1.HashMap的数据储存方式
---- HashMap中的部分结构源码
2.HashMap put元素时的 hash 碰撞
---- 第一种情况
---- 第二种情况
---- 第三种情况
3.put函数的源码与扩容
4.HashMap的扩容阈值验证
---- 验证代码示例一
---- 验证代码示例二

Java之HashMap实现原理(jdk11)

1.HashMap的数据储存方式

HashMap采取数组+ 链表 + 红黑树的存储方式来实现，亦即数组（散列桶）中的每一个元素都是链表；

HashMap中的部分结构源码

// 储存链表结构的初始化数组
transient Node<K,V>[] table;
// 链表结构类 Node 
static class Node<K,V> implements Map.Entry<K,V> {
    // 链表元素通过 key 值计算出来的 hash值
    final int hash;
    final K key;
    V value;
    // 链表指针
    Node<K,V> next;
    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }
    //......
}

// 红黑树结构类TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    // 父节点
    TreeNode<K,V> parent;  // red-black tree links
    // 左子节点
    TreeNode<K,V> left;
    // 右子节点
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    // 红色还是黑色
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    // ......
}

2.HashMap put元素时的 hash 碰撞

第一种情况

通过 key 元素的 hashCode() 方法计算出 hash 值, 再通过 hash 值得到索引, 并且索引处没有元素则将新元素直接加入; 如下图:

第一种情况.png

第二种情况：

通过 key 元素的 hashCode() 方法计算出 hash 值, 再通过 hash 值得到索引, 索引处有元素, 则再调用 key 元素的 equals() 方法, 检测链表上有么有相等的 key 值, 如果有直接覆盖; 如下图:

第二种.png

第三种情况：

通过 key 元素的 hashCode() 方法计算出 hash 值, 再通过 hash 值得到索引, 索引处有元素, 则再调用 key 元素的 equals() 方法, 检测链表上有没有相等的 key 值; 如果没有, 则检测链表上已有元素的个数:

如果链表上已有元素的个数等于 7 个, 则会将新元素添加到链表尾之后会将此链表转为红黑树存储;

第三种1.png

如果链表上已有元素的个数小于 7 个, 则会将新元素添加到链表尾;

第三种2.png

3.put函数的源码与扩容

// 链表转为红黑树时的判断值
static final int TREEIFY_THRESHOLD = 8;

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 为局部数组变量 tab 赋值并检测是否为空 
    // n为tab数组长度
    // i是所存元素经过计算所得到的 tab 数组下标
    // p是tab[i]上的元素
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 第一种情况p为null,也就是tab[i]位置没有元素,可以直接存入数据
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            // 第二种情况p不为null,也就是tab[i]上已有元素,但是计算出来的key值相同,所以直接覆盖
            e = p;
        else if (p instanceof TreeNode)
            // 第三种情况
            // tab[i]上已经是红黑树结构类型了 所以添到红黑树上
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 将新元素添加到tab[i]的链表尾
                    p.next = newNode(hash, key, value, null);
                    // 判断 tab[i] 上的链表是否应该转为红黑树
                    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;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断是否超过了HashMap的扩容值
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

treeifyBin(tab, hash) 与 resize() 函数

在put函数中会在将链表转为红黑树时, 调用这个函数; 其部分源代码如下:

static final int MIN_TREEIFY_CAPACITY = 64;

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    // 当第一次发生元素链表转成红黑树操作时,如果数组长度小于 MIN_TREEIFY_CAPACITY
    // 会自动调用 resize() 扩容;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) {
       // ...... 省略红黑树操作
    }
}

final Node<K,V>[] resize() {
    // 扩容之后会 reHash 重新分配所存储的元素,这样旧的链表就会打散,链表上的元素个数就会减少;
    // 如果还是有红黑树结构, 此时直接找到 TreeNode 的类型判断位置
    // ......
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 重新分配之后的已经确定这里是链表转为红黑树
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // ......
                }
            }
        }
    }
    return newTab;
}

static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
    // ......
    
    // 下面函数是对红黑树再分配的操作,当元素个数大于 UNTREEIFY_THRESHOLD 时
    // 就会将链表转为红黑树存储这个值是 6;
    if (loHead != null) {
        if (lc <= UNTREEIFY_THRESHOLD)
            tab[index] = loHead.untreeify(map);
        else {
            tab[index] = loHead;
            if (hiHead != null) // (else is already treeified)
                loHead.treeify(tab);
        }
    }
    if (hiHead != null) {
        if (hc <= UNTREEIFY_THRESHOLD)
            tab[index + bit] = hiHead.untreeify(map);
        else {
            tab[index + bit] = hiHead;
            if (loHead != null)
                hiHead.treeify(tab);
        }
    }
}

其实搞不懂为啥设计的这么复杂, 红黑树就算了, 又是8 又是6的, 先吐槽一下;
大体是这个样子的:

当 HashMap 中的数组大小小于 64 时, 索引处上的链表元素个数添加到 8 个就会转为红黑树存储, 如果超过8个就会扩容; 这样一来旧的链表就会被打散;
而当 HashMap 中的数组大小扩容到大于 64 时, 索引处上的链表元素个数等于 6 个就会转为红黑树存储, 如果超过 6 个就会继续扩容
像上面这样的情况一般非常少见, 因为通过 key 计算出来 hash 值相等的概率低, 然后就算获取到相同的索引, 而当元素个数达到阈值就会扩容, 所以在HashMap的一个链表上挂着8个元素的概率是非常低的;

据说这么设计是为了提高 HashMap 的搜索效率;
```
if (++size > threshold)
   resize();
```

4.HashMap的扩容阈值验证

HashMap的扩容阈值是由变量 loadFactor 与 threshold 决定的; 前者是负载因子, 后者等于负载因子 x 数组容量; loadFactor 的默认值是 0.75 , 这个值也可以在 new HashMap对象时手动传入 (与 HashMap 性能有关);

4.1 验证代码示例一

HashMap 并没有对外提供获取 HashMap 对象数组容量的函数, 可以用反射的方式获取capacity()函数来拿到初始数组 table[]的大小;

示例代码如下:

public class HashMapTest {
    public static void main(String[] args){
        // 指定初始容量16 来创建一个HashMap
        HashMap hashMap = new HashMap(16);
        // 获取HashMap整个类
        Class<?> mapType = hashMap.getClass();
        // 获取指定方法，因为HashMap没有容量这个属性，但是capacity方法会返回容量值
        Method capacity = mapType.getDeclaredMethod("capacity");
        // 设置目标方法为可访问
        capacity.setAccessible(true);
        
        for (int i = 0; i < 14; i++) {
            hashMap.put(i, i);
            // 动态监测HashMap的容量与元素数量
            System.out.println("容量：" + capacity.invoke(hashMap) + ","
                               + "元素数量：" + hashMap.size());
        }
    }
}

打印结果

容量：16,元素数量：1
容量：16,元素数量：2
容量：16,元素数量：3
容量：16,元素数量：4
容量：16,元素数量：5
容量：16,元素数量：6
容量：16,元素数量：7
容量：16,元素数量：8
容量：16,元素数量：9
容量：16,元素数量：10
容量：16,元素数量：11
容量：16,元素数量：12
容量：32,元素数量：13
容量：32,元素数量：14

4.1 验证代码示例二

将 threshold 主动设置为0.5;

public class HashMapTest {
    public static void main(String[] args){
        // 指定初始容量16 来创建一个HashMap
        HashMap hashMap = new HashMap(16,0.5f);
        // 获取HashMap整个类
        Class<?> mapType = hashMap.getClass();
        // 获取指定方法，因为HashMap没有容量这个属性，但是capacity方法会返回容量值
        Method capacity = mapType.getDeclaredMethod("capacity");
        // 设置目标方法为可访问
        capacity.setAccessible(true);
        
        for (int i = 0; i < 14; i++) {
            hashMap.put(i, i);
            // 动态监测HashMap的容量与元素数量
            System.out.println("容量：" + capacity.invoke(hashMap) + ","
                               + "元素数量：" + hashMap.size());
        }
    }
}