HashMap

HashMap

底层刨析

  1. 允许为NULL

  2. 无序

  3. 不同步

  4. 装载因子设置的太低，初始化容量设置的太高，对遍历的性能影响比较高(不好)

    • 为了减少在散列的机会

  5. 装载因子默认0.75

  6. 如果有足够大的数据量存储到HashMap，最好设置初始化容量（比自动散列好很多）Spring 绝对设置了初始化容量

  7. 继承关系

    image-20210731091048824

  8. 属性

    1. 初始化容量 ： 16 不是直接写16 而是 1<<4 <=> 2^4 <=> 16

       /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    2. 最大容量： 2^30

      static final int MAXIMUM_CAPACITY = 1 << 30;

    3. 默认装载因子： 0.75f

       static final float DEFAULT_LOAD_FACTOR = 0.75f;

    4. 判断何时链表->树的一个链表的元素个数阈值： 8

      static final int TREEIFY_THRESHOLD = 8;

      散列表的某一个桶中(数组某一位的链表内)元素个数最少是这个值，那么才允许把这个桶转换为树结构存储

    5. 判断何时树->链表阈值： 6

      static final int UNTREEIFY_THRESHOLD = 6;

      桶中的树结构的节点数目小于了这个值，那么该桶的数据结构就转换为链表存储

    6. **哈希表 ** 底层的散列表

      transient Node<K,V>[] table;

    7. 实体集合 用于做缓存

      transient Set<Map.Entry<K,V>> entrySet;

    8. 大小

      transient int size;

    9. 并发控制字段

      transient int modCount;

    10. 在散列阈值

      int threshold; // 容量 * 装载因子

    11. 装载因子

      final float loadFactor;

  9. Node类

    1. 属性

      1. final int hash; // hash值

      2. final K key; // 键

      3. V value; // 值

      4. Node<K,V> next; // next节点

HashMap构造方法

四个构造方法

  1. HashMap(int initialCapacity, float loadFactor)

    1. 判断初始化容量是否合理：<0? >2^30?

      1. <0? ：抛出异常

      2. 大于 2^30 ：直接让初始化容量 = 2^30

      3. if (initialCapacity < 0)
    throw new IllegalArgumentException("Illegal initial capacity: " +
                                       initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
    initialCapacity = MAXIMUM_CAPACITY;

    2. 初始化装载因子

      1. this.loadFactor // 装在因子	

      2. int threshold; 
// 是否需要在散列的一个阈值 ：(capacity * loadFactor)
// 在后期创建散列表的时候会重新赋值

put方法

  1. 调用了 putVal() 方法

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

    2. 在之前调用了 hash() 方法来计算哈希值

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

      2. 让key的hashCode与key的hashCode的高16位做异或

        1. (h = key.hashCode()) ^ (h >>> 16)

        2. 为啥？

          1. 转到putVal()方法分析

          2. 因为默认的初始容量是16，放到散列表中的位置应该是0~15

          3. tab[i = (n - 1) & hash]

            1. (n-1)&hash -> 存储的位置

            2. 与hash进行&运算时，仅仅后四位有效

            3. 如果Key的hashCode高位变化很大，低位变化小，导致Hash值相同的许多

            4. 那么做完高16位异或之后 -> 低位 -> 高位与原低位的结合,减少了碰撞的可能性

    3. putVal()方法分析

      1. Node<K,V>[] tab; // 散列表 -> 用于对比底层的散列表

      2. Node<K,V> p; // 新的元素

      3. if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

        如果散列表为空时，调用resize方法初始化，散列表

      4. if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

        如果没有碰撞 -> 直接添加到这个位置上

        • 如果没有碰撞 ： 计算出的这个Key的hash,先通过下标获取一个元素，位NULL -> 这个位置没有东西

      5. 发生了Hash碰撞

        1. 源码

          else {
    Node<K,V> e; K k;
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;
    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;
        }
    }

        2. 逻辑处理

          1. Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

            特殊：hash相同并且key也相同的情况 桶上时

            若p的hash等于key的hash,等等，目的就是确认key存在了, 记录一下 e = p 判断是不是put了同一个Key

            • P：就是判断是否hash冲突时，赋值的那个
            • p = tab[i = (n - 1) & hash]
          2. else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            判断是否是红黑树结构，是调用树的的方法

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

            判断这个桶满足转换树的条件

            • binCount：记录链表的长度的，如果达到转为树的阈值条件了 -> 转换为树

              binCount >= TREEIFY_THRESHOLD - 1 // 8 - 1 = 7

          4. if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    break;

            是不是put了相同的Key , 也就是条件：特殊：hash相同并且key也相同的情况 在链表循环时

          5. p = e; // 继续遍历
// 之后等待遍历 直到 最后一个节点了 break了，走的是

          6. 注意点

            1. 没有发送hash碰撞直接存储到对应的位置上

          7. hash碰撞了(key是不同的)，链接到链表的尾部
            3. 确定何时转换为红黑树的时机

          8. hash碰撞了，key也相同，新值替换旧值

      6. resize()方法

        1. 源码

          final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    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 { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

        2. 就是再散列的一个过程，包含了判断桶是不是红黑树、是不是链表

get方法

  1. 源码

    public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

  2. 是AbstractMap抽象类里的方法

  3. 核心方法：getNode

  4. getNode()

    1. 参数

      1. getNode(hash(key), key)

      2. hash(key), key

      3. hash(key) 与高16位做异或 -> put方法的hash

    2. 逻辑步骤

      1. 判断计算出来的哈希值是在哈希表上的

        if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n - 1) & hash]) != null)

      2. 若是在桶的首位上就直接按下标返回Node

        if (first.hash == hash && // always check first node
    ((k = first.key) == key || (key != null && key.equals(k))))
    return first;

      3. 否则就在红黑树、链表里面查找元素

        if ((e = first.next) != null) {
    if (first instanceof TreeNode)
        return ((TreeNode<K,V>)first).getTreeNode(hash, key);
    do {
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
            return e;
    } while ((e = e.next) != null);
}

remove方法

  1. 源码

    public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

  2. 是抽象类、Map接口的方法

  3. 调用removeNode(hash(key), key, null, false, true)核心方法

  4. removeNode(hash(key), key, null, false, true)

    1. 规则检查-桶不为空、映射的哈希值也存在

      if ((tab = table) != null && (n = tab.length) > 0 &&
    (p = tab[index = (n - 1) & hash]) != null)

    2. 若在桶的首位找到了元素，先记录下来

      if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    node = p;

    3. 否则，就去红黑树、链表里面查找

      else if ((e = p.next) != null) {
    if (p instanceof TreeNode)
        node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
    else {
        do {
            if (e.hash == hash &&
                ((k = e.key) == key ||
                 (key != null && key.equals(k)))) {
                node = e;
                break;
            }
            p = e;
        } while ((e = e.next) != null);
    }
}

    4. 找到了节点，都对上了，就进行删除

      1. 链表删除
      2. 红黑树删除
      3. 桶的首位删除
      if (node != null && (!matchValue || (v = node.value) == value ||
                     (value != null && value.equals(v)))) {
    if (node instanceof TreeNode)
        ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
    else if (node == p)
        tab[index] = node.next;
    else
        p.next = node.next;
    ++modCount;
    --size;
    afterNodeRemoval(node);
    return node;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/JQ04/p/15092917.html