HashMap的层是数组和链表实现的,有两个重要参数:容量和负载因子。其中容量默认为16,负载因子为0.75,当HashMap的size>容量*负载因子就会发生扩容。

//默认容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//默认加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap内部依靠一个一个Nody<k,v>结点实现,其中数组结构也叫做桶结构

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;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    public final V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }
}

HashMap添加元素操作put:

  1. 首先会将传入的 Key 做hash运算计算出 hashcode,然后根据数组长度取模计算出在数组中的 index 下标
  2. 如果没有碰撞则直接插入到数组(桶)中
  3. 如果碰撞了

    1. 节点存在就替换旧值
    2. 链表长度大于阈值(TREEIFY_THRESHOLD=8)则链表转红黑树
    3. 头插法插入该桶的链表
  4. 如果桶满了(size大于容量16*加载因子0.75)就需要2倍扩容
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
/**
* @param hash  由key计算出来的 hash值
* @param key   要存储的key
* @param value  要存储的value
* @param onlyIfAbsent  如果当前位置已存在一个值,是否替换,false是替换,true是不替换
* @param evict  表是否在创建模式,如果为false,则表是在创建模式。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K, V>[] tab;Node<K, V> p;int n, i;
    //1、检查table是否为空,如果为空就初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        //  初始化,也是扩容
        n = (tab = resize()).length;
    //2.检查table中位置为(n -1 ) & hash 是否为空,如果为空,直接放入(这是放在数组里)
    if ((p = tab[i = (n - 1) & hash]) == null)
        //放入
        tab[i] = newNode(hash, key, value, null);
    //桶中已经存在元素了,也就是说 table中( n -1) & hash这个位置不为空(发生碰撞了)
    else {
        Node<K, V> e;K k;
        //3.如果桶中存在的元素的key和hash都相等,直接覆盖旧value
        if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        //4.判断存放该元素的链表是否转为红黑树,如果为红黑树,直接插入,此时上面3是不成立,hash值不相等,也就是key值不等(hash值是由key算出来的)
        else if (p instanceof TreeNode)
            //存放在红黑树里
            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
        //5.第3和第4都不成立,将插入元素存放在链表中
        else {
            //循环链表,找到链表末尾插入元素
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    //判断当前链表的元素是否超过要转换为红黑树的阈值 (节点数超过8就要转换为红黑树)
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                           //转换为红黑树存储
                        treeifyBin(tab, hash);
                    break;
                }
                //遍历链表,看链表中是否存在hash和key与要插入进来的元素相同,如果相同,跳出循环。
                if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            //跳出循环
                    break;
                // 跟 e = p.next 组成用来遍历链表,即循环条件。
                p = e;
            }
        }
       //6.存在key值和hash值相等的,直接覆盖旧value
           if (e != null) { // existing mapping for key
            //取出e的value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                //覆盖
                e.value = value;
            //访问后回调
            afterNodeAccess(e);
            return oldValue;
        }
    }
    //7.将记录修改次数加1,判断是否需要扩容,如果需要就扩容
    ++modCount;
    if (++size > threshold)
        resize();
    //插入后回调
    afterNodeInsertion(evict);
    return null;
}
//hash算法
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

红黑树问题

  1. HashMap并不是在链表元素个数大于8就一定会转换为红黑树,而是先考虑扩容,扩容达到默认限制后才转换
  2. HashMap的红黑树不一定小于6的时候才会转换为链表,而是只有在resize的时候才会根据 UNTREEIFY_THRESHOLD 进行转换。

二者转换的原因

  1. 如果元素小于8个,查询成本高,新增成本低
  2. 如果元素大于8个,查询成本低,新增成本高
//链表转红黑树临界条件
static final int TREEIFY_THRESHOLD = 8;
static final int MIN_TREEIFY_CAPACITY = 64;
//红黑树转链表临界条件
static final int UNTREEIFY_THRESHOLD = 6;
Last modification:October 17th, 2020 at 05:36 pm