HashMap-02

Jingxc大约 6 分钟java后端HashMapjava后端

HashMap-02

1. 构造器

HashMap在创建对象时，可的调用构造器有三种，无参构造器(常用)，初始化容量大小，初始化容量和加载因子

初始化的时候，

  • 默认容量为16，static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
  • 默认最大容量为1<<30(高位符号位)， static final int MAXIMUM_CAPACITY = 1 << 30;
  • 加载因子，static final float DEFAULT_LOAD_FACTOR = 0.75f;
//初始化容量和加载因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                            initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                            loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

//初始化容量
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//无参构造器
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

2. put方法

HashMap的put方法实际上调用的是putVal方法

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

2.1 hash算法

HashMap的hash返回值：

**问题：**HashMap⾥⾯的hash()返回值为什么不是的返key.hsahCode()的返回值，⽽是key.hsahCode()^(key.hsahCode()>>>16)的返回值呢？

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

提示

这样做的目的是减少hash的冲突概率

HashMap在put的时候，hash冲突时不可避免的，所以如何尽量避免hash冲突，或者在hash冲突时如何快速高效定位到数据的真实存储位置，就是HashMap中最核心的部分key.hsahCode()^(key.hsahCode()>>>16)的逻辑就是先获得key的hashCode值h，然后h和h右移16位做异或运算，这样高16为也参与到hash的逻辑运算中了，减少冲突。

例

比如有两个key的hashCode返回值如下：

key1.hashCode()

1111 1111 1111 1111 0101 0101 0111 0101

key2.hashCode()

1111 1111 1110 1111 0101 0101 0111 0101

如果没有^(key.hsahCode()>>>16)那么，15&hash就分别是

key1在底层的数组索引值是：5

1111 1111 1111 1111 0101 0101 0111 0101

0000 0000 0000 0000 0000 0000 0000 1111

key2在底层的数组索引值是：5

1111 1111 1110 1111 0101 0101 0111 0101

0000 0000 0000 0000 0000 0000 0000 1111

这是因为key1.hashCode()和key2.hashCode()的低16位完全相同，然后15&hash的时候，15的二进制00000000000000000000000000001111的高位全是0，这就造成了15&hash的时候，只有hash的低16为起了作用，而key1.hashCode()和key2.hashCode()的低16位完全相同，所以底层索引值也相同了，这样很容易造成hash冲突。但如果有^(h >>>16)

相关信息

比如有两个key的hashCode返回值如下：

就比如key.hsahCode()也就是h的变量值如下：

1111 1111 1110 1111 0101 0101 0111 0101

然后(h = key.hashCode())^(h >>>16)就变成

1111 1111 1110 1111 0101 0101 0111 0101^

0000 0000 0000 0000 1111 1111 1110 1111

计算结果是：1111 1111 1110 1111 1010 1010 1001 1010

这里可以看出，最终的结果值具备了高16位与低16位共同的特征，这样减少了hash冲突的概率。

2.2 第一次添加键值对

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    ...
}

第一次调用添加元素时会初始化Node<K,V>属性

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    ...
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    ...
    return newTab;
}

初始化属性Node<K,V>后添加元素，通过&操作确定元素位置,i = (n - 1) & hash

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    ...
}

2.3 第二次添加键值对

第二次添加元素，不会初始化数组属性Node<K,V>,也不会进行扩容，直接添加元素即可

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    ...
    if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
    ...
}

2.4 多次添加键值对(键已存在)

在添加重复的键值对时，判断hash(key)相同并且值也相同，认为重复键，只修改存储的值为新值

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    ...
    else {
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        ...
    }
    if (e != null) { // existing mapping for key
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e);
        return oldValue;
    }
    ...
}

2.5 多次添加键值对(链表)

多次添加键值对，

  1. 首先判断链表是否存在下一节点，存在则判断key是否相同，相同则更新value值，不同则继续判断
  2. 如果判断链表不存在下一节点了，则把最新的键值对添加到链表尾部

注意

这里存在扩容或者链表转红黑树的可能性，如果链表的长度等于8了，则进行扩容或树的转换

 final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    ...
    else {
        ...
        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);// TREEIFY_THRESHOLD = 8
                    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;
        }
    }
    ...
}

2.6 多次添加键值对(树)

多次添加键值对，如果在数组中索引位置为树结构，则通过左右旋添加到树结构中

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    ...
    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);
        ...
    }
    ...
}

2.7 扩容或者树的转换

当链表的元素个数等于8时会进行扩容或树的转换 treeifyBin(tab, hash);

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //将Node节点变为TreeNode节点，将单向链表变成双向链表
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            //这个方法里就开始做各种比较，左旋右旋，然后把双向链表搞成一个红黑树
            hd.treeify(tab);
    }
}

数组扩容：

final Node<K,V>[] resize() {
    ...
    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
    }
    ...
    @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) {
                ...
                else { // preserve order
                   ...
                    do {
                        ...
                        if ((e.hash & oldCap) == 0) {
                            ...
                        }
                    } while ((e = next) != null);
                    ...
                }
            }
        }
    }
    return newTab;
}

这里主要介绍一下 if ((e.hash & oldCap) == 0) 链表扩容时的操作

提示

扩容前在数组中索引位置为：i = (n - 1) & hash即(2^n - 1) & hash

扩容后在数组中索引位置为：(2*2^n - 1) & hash

两个位置的对比关键在于hash ^ oldCap即hash ^ 2^n

扩容
扩容

说明

树结构在扩容时也是类似于链表一样存放索引位置

3. 线程不安全

  1. jdk1.8 在多线程put(尾插法)的时候可能会出现元素丢失的情况，在多线程put/get的时候，也有可能造成get为null
  2. jdk1.7 在多线程put(头插法)的时候可能会出现死循环
上次编辑于:
贡献者: Jingxc
联系我 | Copyright © 2018-present Jingxc
Copyright © 2024 Jingxc