时间戳

首页 > 技术文章 > HashMap集合详解

HashMap集合详解

jiahaodaicoder 2021-04-15 14:12 原文

HashMap集合详解

参考文章
https://blog.csdn.net/qq_40574571/article/details/97612100
https://blog.csdn.net/woshimaxiao1/article/details/83661464
https://zhuanlan.zhihu.com/p/42806127

1. 继承关系

avatar

2. HashMap 的底层数据结构

avatar

  1. HashMap的源码
	
	// 默认初始容量
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    
    // 负载因子，主要是和容量一起来计算resize()的阈值。 capacity * load = threshold 
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
    // 扩展成红黑树时候，节点的阈值
    static final int TREEIFY_THRESHOLD = 8;

    // HashMap的Node数组。数组中的每个元素都是头结点，然后通过链表连接hash冲突的值。
    // 如果超过了 扩展成树的阈值，就变成红黑树
    transient Node<K,V>[] table;

    // Node的结构
    static class Node<K,V> implements Map.Entry<K,V> {
        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;
        }

        // 还很多、省略
    }

3. HashMap的put方法

avatar
从这张图可以看出来JDK1.8之后HashMap中put()方法存储key-value的过程。

  1. 首先判断table是否为空或者长度是0.如果是的话扩容。
  2. 然后计算hash值，计算其索引的位置。如果当前索引table[index] = null,直接插入
  3. 如果不是null。则查看该key是否存在，如果存在就覆盖之前的value值。 如果不存在 就判断是链表还是树节点进而进行插入
  4. 插入完成之后，要判断size 和 容量的大小，看是否需要扩容

源码分析

	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;
        // 判断table 是否为null 或者长度为0
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 计算hash值，并且判断当前table[index]是否有值
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            // 如果key存在的话，直接覆盖
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 判断是否是TreeNode 红黑树节点，如果是红黑树按照红黑树的方法插入
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
            	// 链表节点的方式
                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;
                    }
                    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;
            }
        }
        // 这个成员表示的是对于hashmap的修改次数
        ++modCount;
        // 是否需要扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

4. HashMap中计算索引的方法

  1. 计算hash
	// 计算hash
	static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

分为两步
h = key.hashCode()
h ^ (h >>> 16)
为什么要进行无符号右移16位？
这是为了将key.hashcode的高位和低位都用上.
主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

  1. 计算在table中的位置
	// 这段代码截取putVal()方法
	Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 判断table 是否为null 或者长度为0
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 计算hash值，并且判断当前table[index]是否有值
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

其中可以看出 (n - 1) & hash作为了索引。其中n = table.length 也就是当前HashMap的容量
为什么要利用这个方法来计算idnex值呢?
1. 首先要知道HashMap中的容量都是2的幂次方。
2. 2^n - 1的二进制数 低位全部是1。 就比如 16 - 1 = 15---------> 0000 1111
3. 每次扩容都是在原有的容量上* 2
avatar

通过上图可以看出来，在扩容之后，扩容前的节点的位置和扩容后节点的索引位置只有两种关系。一种是不变，一种是 old_index + 旧容量 = new_index
这样做的好处是  简化了对于 index的计算

第二个好处就是：通过  hash & (length - 1) 这个实质上在 length 是2^n的时候就是  hash % length
而位运算的效率高于%
第三个好处就是  (h ^ (h >>> 1) ) & (length - 1) 这样会使得hash分布的更均匀，避免hash冲突。因为不会是的一个链表或者树的高度太大从而降低了查找效率

3. 线程安全问题

HashMap是线程不安全的。

avatar
HashTable是线程安全的，因为它的方法上加上了synchronize关键字。 因为加锁，所以效率低于hashmap

avatar
ConcurrentHashMap是线程安全的。jdk1.8以前使用的是segment分段，每一个segment[i]就是一个hashmap结构。它给每一段加上了锁，所以可以实现并发。

jdk 1.8 之后，给每个节点加上了锁
avatar

推荐阅读