新闻资讯

新闻资讯 行业动态

Java的HashMap

编辑:006     时间:2020-02-14

HashMap

概述

  • HashMap是一个
  • jdk8源码

    构造器

    有4个构造器:
public HashMap() public HashMap(int initialCapacity) public HashMap(int initialCapacity, float loadFactor) public HashMap(Map<? extends K, ? extends V> m)
  • 除了显式设置loadFactor,其他情况都是设置为默认的0.75。
  • 传入另外一个Map需要满足泛型上下界的要求,比如只能由<String,String>转成<Object,Object>。

主要成员变量

  • Node<K,V>[] table;
    哈希表。
  • Set<Map.Entry<K,V>> entrySet;
    用来遍历的Entry集合。
  • int size;
    map中元素个数。
  • int modCount;
    源码上说的是结构化修改的次数,关系不大。
  • int threshold;
    阈值,当size大于这个阈值,就要resize
  • final float loadFactor;
    加载因子,表示哈希表中元素的密集程度,默认是0.75。

put

table

哈希表,就是一个Node数组,而Node是HashMap里一个静态内部类,实现了Map接口里的Entry接口,可以看出Node类其实是一个链表节点,所以HashMap就是使用了链地址法来解决冲突的。
Node类重写了hashCode方法,把key和value的哈希值异或起来。

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

putVal

put方法内部是调用了putVal方法,putVal(hash(key), key, value, false, true)。
多了三个参数,第一个是哈希值,后两个是onlyIfAbsent和evict。
onlyIfAbsent是put方法用来判断是否覆盖。
evict应该是LinkedHashMap用到的,默认都为true。

  • 第一步就是判断哈希表是否为空,若是进行resize(),保证哈希表的长度是2的k次方的形式。
  • 第二步就是通过哈希值计算下标,计算的方法是(n - 1) & hash,因为n=2^k,所以这个操作就是取哈希值的低k位,其实就是取模
  • 第三步判断是否冲突了,若否就直接放一个新节点上去,存有hash值,key和value。
  • 第四步就是解决冲突。

注意这里的相等比较用到了==和equals(),这是key覆盖的情况。

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

如果哈希表上不是链表节点,而是平衡树节点,调用putTreeVal方法。

else if (p instanceof TreeNode)
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

这是哈希位置相同而key不同的清空,也就是哈希冲突。
遍历对应位置的链表,加到表尾,如果链表中间有相等的key,也是覆盖。
当同一位置链表节点数大于等于8个时,调用treeifyBin方法进行树化,将链表转化为红黑树。

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

接下来是处理key覆盖的清空,会返回旧的value。
put方法的onlyIfAbsent是false,所以无论如何都会覆盖相同key的值。
putIfAbsent方法的onlyIfAbsent是true,所以只有当oldValue是null的时候,才会覆盖。

if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e); return oldValue;
}

Test code1

import java.util.HashMap; public class LearnHashMap { public static void main(String[] args) {
        HashMap<String,String> a=new HashMap<>();
        a.put("abc","FF");
        a.putIfAbsent("abc","FFF"); //不会覆盖,仍然是{"abc":"FF"} System.out.println(a.put("abc","kk"));
    }
}

最后是处理对应哈希表下标没有元素的清空,size要加1,如果大于threshold,就扩容。

++modCount; if (++size > threshold)
    resize();
afterNodeInsertion(evict); return null;

tableSizeFor

这个方法可以返回最近且大于cap的2的次幂,可以用来根据容量capacity来确定阈值threshold。
源码就不看了,神仙位运算看不懂。

resize

每次都是2倍的扩容,MAXIMUM_CAPACITY就是1<<30。

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
    newThr = oldThr << 1; // double threshold

如果容量为0,而阈值大于0,直接让容量为阈值。

else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr;

都为0,则用默认值,默认阈值等于默认容量默认加载因子,即160.75=12。

else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

然后就是new一个新的节点数组,大小是原数组的两倍,然后将原数组的链表和红黑树copy过去。
这一步可以把原本一个节点的链表分成两个。

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

treeifyBin

将链表转红黑树

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。

回复列表