Java数据结构之HashMap

2019-11-30 本文已影响0人小马蛋

HashMap类图.png

0、HashMap 简介

HashMap是由数组、链表或红黑树组成的，应该是我们Java开发工作中用到的非常普遍的数据结构之一了，它以key-value键值对的形式进行存储。
HashMap是线程不安全的，如果你想使用线程安全的HashMap，那么请使用HashTable或者ConcurrentHashMap，主推ConcurrentHashMap，因为HashTable采用的是全表锁，效率低下，而Java 8里的ConcurrentHashMap采用的是节点锁，效率较高。
关于HashTable和ConcurrentHashMap我们后面会专门进行讲解。

1、HashMap 属性

`static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;` 默认初始容量

默认初始容量为16，必须是2的n次幂，HashMap在确定数组下标Index的时候，采用(length-1) & hash按位与的方式，只有当length为2的指数幂的时候才能较均匀的分布元素。

`static final int MAXIMUM_CAPACITY = 1 << 30;` 最大容量

必须是2的n次幂，最接近int最大值的2个指数幂用位运算符表示就是 1 << 30

`static final float DEFAULT_LOAD_FACTOR = 0.75f;` 默认加载因子

当构造函数中未指定加载因子时，使用的是0.75f这个默认值。

loadFactor加载因子是控制数组存放数据的疏密程度，loadFactor越趋近于1，那么数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor越小，也就是趋近于0，数组中存放的数据(entry)也就越少，也就越稀疏。

loadFactor太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor的默认值为0.75f是官方给出的一个比较好的临界值。

关于负载因子，我们在这里好好聊聊，当负载因子为 0.75 时，箱子中元素个数和概率的关系如下：

数量	概率
0	0.60653066
1	0.30326533
2	0.07581633
3	0.01263606
4	0.00157952
5	0.00015795
6	0.00001316
7	0.00000094
8	0.00000006

这就是为什么我们将0.75设为负载因子，同时针对箱子中链表长度超过8以后要做另外的优化（一是优化的概率较小，不一定能碰撞8次，二是优化过后的效率提升明显）。
所以，一般情况下负载因子不建议修改；同时如果在数量为8的链表的概率较大，则几乎可以认为是哈希函数设计有问题导致的。

`static final int TREEIFY_THRESHOLD = 8;` 树化阀值

节点对应的链表容量大于等于阀值时，链表转换为红黑树进行存储

`static final int UNTREEIFY_THRESHOLD = 6;` 树还原链表阀值

节点对应的红黑树容量小于等于阀值时，红黑树转换为链表进行存储

`static final int MIN_TREEIFY_CAPACITY = 64;` 最小的树形化容量

当链表的容量超过树化阀值时，一定会转换为红黑树吗？

不一定！因为在进行树化时，会判断当前HashMap的容量是否大于等于这个MIN_TREEIFY_CAPCITY
- 是，则进行链表的树化
- 否，会对HashMap（准确的说是tables数组）进行扩容，扩容时会对链表内节点再进行一次hash散列抖动，确定最终位置后，有可能链表的大小没有改变，那么很有可能在下次hash碰撞的时候进行树化或者再次扩容。

`static class Node<K,V>` 节点，真正存放键值对的节点

implements Map.Entry

Node的内部属性为：

int hash 当前node的hash值
K key 当前node对应的key，也就是存储的key
V value 当前node对应的value，也就是存储的value
Node<K,V> next 表示指向下一node的指针，hash值相同的node通过next进行遍历查找

Node的内部方法为：

Node(int hash, K key, V value, Node<K,V> next) 有参构造函数
getKey() 获取key值
getValue() 获取value值
hashCode() 通过对key和value的hashCode做 ^（异或操作）返回node的hashcode
setValue() 设置node值
equals() 重写equals方法 - 要么内存地址一样 - 要么就是key && value 相等
toString() toString()方法

`transient Node<K,V>[] table;` tables数组

以Node数组的形式存放信息，在必要时会重新调整大小，但长度总是2的n次幂

`transient Set<Map.Entry<K,V>> entrySet;` 保存缓存的entrySet()

注意，使用了AbstractMap字段用于keySet()和values()。

`transient int size;` map中key-value的数量

这个数量没有用volatile修饰，因为没有实际意义，HashMap并不是线程安全的，所以也就没有必要用volatile修饰的必要。

`transient int modCount;` 被修改的次数

这个HashMap在结构上被修改的次数结构修改是指改变HashMap中映射的数量或修改其内部结构的次数。
此字段用于使HashMap集合视图上的迭代器快速失败。(见ConcurrentModificationException)。在迭代的时候不允许修改HashMap，就是用这个参数做校验的。

`int threshold;` 临界值，当实际大小(容量*填充因子)超过临界值时，会进行扩容

capacity * load factor

`final float loadFactor;` 加载因子

一般情况下负载因子不建议修改，它是衡量哈希表的空/满程度，一定程度上也能体现查询的效率，负载因子越大，意味着哈希表越满，越容易导致冲突，因而查询效率也就更低。

其计算公式为：负载因子 = 总键值对数 / 箱子数量

2、HashMap 构造函数

public HashMap(int initialCapacity, float loadFactor) 有参构造函数
第一个参数是初始容量，第二个是加载因子
- 对内置loadFactor赋值
- 经过taleSizeFor方法计算，得出离initialCapacity最近的2的正数次幂的数，然后赋值给threshold
public HashMap(int initialCapacity) 有参构造函数
参数是初始容量大小，然后调用内部双参构造函数，加载因子为默认值0.75f
public HashMap() 无参构造函数
加载因子为默认值0.75f
public HashMap(Map<? extends K, ? extends V> m) 有参构造函数
参数是Map子类实例，加载因子为默认值0.75f
调用putMapEntries()方法，将Map子类实例的Entries放入到当前HashMap中

在调用前三种构造函数时，HashMap内部的tables数组并未初始化，tables采用的是lazy模式的，只有我们调用put时，才会对tables进行初始化。

在调用第四种构造函数时，HashMap需要将m存储的键值对"转存"到自己内部的tables数组，所以在putVal方法中会对tables数组进行初始化（resize）。

3、HashMap 核心解读

3.1 我们从从下面代码进行解读

    public class OneTest {
        @Test
        public void test() {
            Map<String, String> map = new HashMap();
            map.put("k1", "v1");
            map.get("k1");
        }
    }

上面代码很简单，使用HashMap无参构造，实例化一个HashMap，然后进行put和get操作

解读：

3.1.1 通过HashMap的空构造函数示例化了一个对象map

HashMap空构造函数源代码如下：

public HashMap() {
  // 加载因子使用默认的 0.75f
  this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

3.1.2 map调用put()方法，存入键值对

HashMap.put()源码如下：

public V put(K key, V value) {
  // 在调用putVal方法时，首先获取key的hash值
  return putVal(hash(key), key, value, false, true);
}

hash方法的源码：

/**
 * hashCode的高16位不变，低16位与高16位做一个异或。
 * 这样做的目的是同时把高16位和低16位的影响都考虑进来以减少小容量HashMap的散列冲突。
 */
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

putVal方法的源码：

/**
 * 向HashMap存储键值对
 * @param hash          经过计算的key的hash值
 * @param key           对应的key
 * @param value         要存储的value
 * @param onlyIfAbsent  如果为true不改变存在的值
 * @param evict         如果为false则处于创建模式
 * @return 旧值，如果没有则为空
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 局部变量
    Node<K,V>[] tab;
    Node<K,V> p;
    // ntables数组长度
    int n, i;
    // 判断当前内部的tables数组是否已初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        // 内部tables数组初始化
        n = (tab = resize()).length;
    // 经过hash散列抖动得出下标，不存在对应值，直接进行赋值
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 直接进行赋值操作
        tab[i] = newNode(hash, key, value, null);
    // 很不幸，即便对hash进行了散列抖动，但是依然发生了hash碰撞
    else {
        Node<K,V> e;
        K k;
        /*
        已存在的头节点hash值和传入的hash值是否相等 && key是否相等
            - 是 表示要进行覆盖操作
            - 否 表示就是单纯的hash碰撞
         */
        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);
                    /*
                     是否大于树化阀值
                        - 是 转为红黑树
                        - 否 break循环即可
                     */
                    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;
            /*
             !onlyIfAbsent（即是否不改变存在的值）或者 oldValue为null 都要进行覆写操作
             */
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            // 为LinkedHashMap留的后路？
            afterNodeAccess(e);
            return oldValue;
        }
    }

    // 覆写操作不累加修改次数
    ++modCount;
    /*
     存储后的容量是否大于临界值
        - 是 进行扩容操作
     */
    if (++size > threshold)
        resize();
    // 为LinkedHashMap留的后路？
    afterNodeInsertion(evict);
    return null;
}

resize方法源码：

/**
 * Initializes or doubles table size.  If null, allocates in
 * accord with initial capacity target held in field threshold.
 * Otherwise, because we are using power-of-two expansion, the
 * elements from each bin must either stay at same index, or move
 * with a power of two offset in the new table.
 *
 * tables 扩容 || 初始化
 *
 * @return the table
 */
final Node<K,V>[] resize() {
    // 局部变量
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    /*
     局部变量存储当前`临界值`
     两种可能
        - 调用无餐构造，默认的为0
        - 传递了初始容量，然后在构造函数里计算出来的
     */
    int oldThr = threshold;
    // 新的数组容量、下次数组调整的大小
    int newCap, newThr = 0;
    // step-1 如果数组长度大于0 说明不是第一次进来
    if (oldCap > 0) {
        /*
         判断如果tables数组的长度大于 1<<30（即2的30次幂）
         说明已经是最大长度了，无法再扩容了
         */
        if (oldCap >= MAXIMUM_CAPACITY) {
            // 将`下次调整数组大小的阀值`设置为Integer.MAX_VALUE （即int最大值，2的31幂）
            threshold = Integer.MAX_VALUE;
            // 返回现有的tables数组
            return oldTab;
        }
        /*
         如果当前数组的容量，向左位移1位后小于最大容量 && 当前数组大于或等于默认初始容量
         那么将原threshold向左位移1位得到的数赋值给newThr
         */
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    // step-2 第一次进来，说明在实例化时传递了初始容量大小
    else if (oldThr > 0)
        // 将`临界值`赋值给newCap
        newCap = oldThr;
    // step-3 第一次进来
    else {
        // 赋值默认的初始容量大小
        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
    threshold = newThr;
    // 实例化一个容量为newCap的数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    // 将tables指针指向newTab
    table = newTab;
    /*
     这里就是判断是否第一次进来
        - 是，直接将上面实例化后的数组返回
        - 否，需要将原数组的内容"转移"到新数组里
     */
    if (oldTab != null) {
        // 循环将数据导入到新数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // 数组的每一个格子并不一定会被使用，所以需要判断，当前的下标是否存在数据
            if ((e = oldTab[j]) != null) {
                // 将原数组格子清空
                oldTab[j] = null;
                // 如果当前node没有链表，也就是说这个下标未发生key的hash碰撞
                if (e.next == null)
                    // 将原值导入到新数组对应的位置
                    newTab[e.hash & (newCap - 1)] = e;
                // 如果当前node的类型为树节点（红黑树）
                else if (e instanceof TreeNode)
                    // 将树节点的数据导入到新数组对应的位置
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 当前node为链表状了
                else {
                    // 下标不变的头结点、尾节点
                    Node<K,V> loHead = null, loTail = null;
                    // 下标发生变化的头结点、尾节点
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // 遍历链表
                    do {
                        // 当前节点的下一个node节点
                        next = e.next;
                        /*
                         这行代码我愣是看了好长时间，一直在推敲这行代码的意义
                         后来想通了，扩容以后，数组的长度增加了，会影响改变到hash散列抖动后的下标
                         也就是说，在原数组里发生hash碰撞的key，在新数组里可能不再发生碰撞，所以要重新计算一下节点下标是否发生了变化
                         在put时确定数组下标的代码是这样的：
                            (length - 1) & hash
                         */
                        // 下标不变
                        if ((e.hash & oldCap) == 0) {
                            // 尾节点为null 赋值头结点=当前节点
                            if (loTail == null)
                                loHead = e;
                            // 尾节点不为null 赋值尾节点=当前节点
                            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;
                        // 原下标+oldCap 放到新数组里
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

因为tables数组还未初始化，所以会对当前HashMap的tables进行扩容操作。
进入resize方法内部，tables数组还未初始化，即oldCap为0，实例化对象时，调用的是空构造函数，在空构造函数并未对threshold进行相关赋值，即oldThr为0，进入step-3分支。
step-3步骤中：
- 对新数组容量变量newCap，赋值为默认的初始容量（16）
- 对触发扩容的条件变量newThr赋值为(int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY
将HashMap的threshold指向newThr
初始化容量为newCap的新数组，并将tables指向newTab
将新数组newTab返回
==resize方法结束==
key的hash值和数组长度-1进行按位与计算，得出下标，不存在对应值，直接进行赋值操作
累加修改次数
判断存储后的HashMap容量是否大于threshold（临界值）
return null

3.1.3 map调用get()方法，获取key对应的value。

get()方法源码：

/**
 * 通过key获取value，如果key没有对应的值，则返回null
 */
public V get(Object key) {
    Node<K,V> e;
    // 首先获取key的hash值
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

getNode方法源码：

/**
 * Implements Map.get and related methods.
 * 通过hash 和 key 获取node
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab;
    Node<K,V> first, e;
    int n;
    K k;
    if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
        // 首先检查头节点是否是要取出的节点
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 如果头结点不是要取出的节点，说明节点为链表或者红黑树
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // do while循环找到对应的节点
            do {
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

get()方法其实并不难，只是在getNode方法里需要注意节点类型即可。

知识点总结：

HashMap

基于数组实现的散列表，继承于AbstractMap骨架抽象类（此类是为了减少实现Map接口需要做的工作量），实现Map接口。以key-value的形式进行put，以key的形式get

1、容量

默认初始容量16，且容量都是2的n次幂整数，用户可以在调用构造函数时，传递一个容量数值，假使传递的是3，实际的HashMap容量是4而不是3。
因为在构造函数里，有调用tableSizeFor(int)方法，此方法的源码如下：

static final int tableSizeFor(int cap) {
    /*
     为什么要减1？
     因为如果我们传递8，如果不减1，就会返回16，所以在进行计算之前进行了-1的操作
     */
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

这个方法的目的在于返回大于（输入参数-1）且最近的2的整数次幂的数。

在HashMap第一次进行put的时候，会初始化保存数据的数组（table）大小。

ps：不包括调用public HashMap(Map<? extends K, ? extends V> m)构造函数，因为在这个构造函数里，会对table进行初始化。公式为((float)m.size() / loadFactor) + 1.0F

2、加载因子 & 扩容

提到扩容，必须提到loadFactor（加载因子），这个加载因子是什么意思呢？又在哪里用到呢？

作为一般规则，默认负载因子（.75）是时间和空间成本之间的良好折中。更高的值会降低空间开销，但会增加查找成本。

在调用构造函数时，用户可以传递加载因子（float），如不传，默认是.75f

使用到的地方：

1、 public HashMap(Map<? extends K, ? extends V> m)构造函数
传递一个Map类型的实例，并将次m的所有元素放入HashMap，其内部调用了putMapEntries(Map<? extends K, ? extends V> m, boolean evict)。

putMapEntries源码：

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    // 获取传入的map容量大小
    int s = m.size();
    // 如果容量大于0才进行操作
    if (s > 0) {
        /*
        为什么加上 table == null判断，因为HashMap有个构造函数就是传递Map实例，进行实例化的，在实例化期间，table肯定weinull
         */
        if (table == null) { // pre-size
            /*
             为了避免再次扩容，采用的是((实际存储容量 / 加载因子) + 1)的公式，来获取初步的HashMap容量
             为什么+1？因为在putVal中，++size > threshold 就会触发resize操作，如果不+1，就会产生两次扩容，影响性能和效率
             */
            float ft = ((float)s / loadFactor) + 1.0F;
            // 得到最终的HashMap容量，如果大于内置的最大容量阀值，则使用最大阀值
            int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
            // 这条件判断为什么要加上，是为了以防万一吗？
            if (t > threshold)
                /*
                 获取离t最近的2的整数次幂的数
                 赋值临界值
                 */
                threshold = tableSizeFor(t);
        }
        // 如果不是初始化时传递Map实例，则判断map容量是否大于下次调整的值
        else if (s > threshold)
            // 调整HashMap大小
            resize();
        // 将Map实例的key 和value全部导入到当前的HashMap中
        for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
            K key = e.getKey();
            V value = e.getValue();
            putVal(hash(key), key, value, false, evict);
        }
    }
}

在放入m的所有元素前，HashMap会对内部的table进行初始化，容量的大小是通过公式((float)m.size() / loadFactor) + 1.0F得出的。

这里用到了loadFactor

2、HashMap的扩容方法resize()
在HashMap扩容时，通过加载因子计算出下一次扩容的触发临界值（threshold属性）。

3、在反序列化HashMap时
有兴趣可以看看源码里的readObject方法。

从上，我们知道了，加载因子的作用，就是通过公式容量 * 加载因子而计算出触发HashMap扩容的临界值。

网上有一道经典的HashMap扩容面试题：

准备用HashMap存1w条数据，构造时传1w还会触发扩容吗？

解析题目：

调用HashMap的构造函数并传递10000作为HashMap的容量，同时计算出threshold（触发扩容临界值）的数值为16384（调用了tableSizeFor方法得出的）。
在第一次put的时候会触发HashMap的扩容，初始化数组容量大小（newCap）为threshold（源码就是这么写的）即16384，同时重新赋值threshold为16384*0.75f即12288，也就是说，触发下次HashMap扩容的临界值是12288。
当我们put到第1w条数据时，由于10000 < 12288，所以不会触发HashMap的扩容机制。

ps：如果在构造时传小于（1w / 16384）的加载因子，在put时，是可以触发扩容机制的。

3、存储key-value

HashMap底层是采用数组+链表or红黑树来存储数据的，通过计算出key的散列值，来确定数组的存储位置（下标）。

key 和 value 都可以为null

3.1 put

hash方法源码：

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

因为key的hashCode为int型，也就是4个字节，32位，所以HashMap在计算散列值时，使用高16位和低16位做异或，这样做的目的是同时把高16位和低16位的影响都考虑进来以减少小容量HashMap的散列冲突。
当进行put操作时，计算出key的hash值后与(table.length - 1)做 &（按位与）得出数组的存储位置（下标）。

3.2 hash冲突

我们知道，即使我们散列值的再均匀分散，也有可能会产生冲突，如果hash冲突，HashMap会怎么处理呢？

在数据结构的相关书籍中有介绍，解决这种冲突的方法有几种，分离链接法（链表法）、开放地址法、再散列和公共溢出区。

而HashMap采用的是分离链接法，但是我这里说采用分离链接法是不准确的，因为Java 8的HashMap采用的是链表 + 红黑树（当链表长度超过8 且当前table的长度大于64时会将链表转化为红黑树进行存储）。

Java 7里的HashMap采用的是纯正的分离链接法，且插入链表的方式是头插，Java 8 插入链表的的方式是尾插

3.3 尾插法

为什么Java 8采用尾插？

因为在Java 7的HashMap在多线程并发的场景下，执行扩容会导致环形链，在之后调用get方法或者扩容，会产生死循环的bug（可以称之为bug，即使HashMap宣称了自己是线程不安全的，但是这个死循环却是设计理念引起的，而不是共享资源引起的）。

具体原因就是因为使用了头插法，想了解原理可以查阅Java 7扩容方法源码。

Java 8 采用尾插法可以避免死循环的bug，但是，在多线程的情况下，依然是线程不安全的。

3.4 树化

为什么在链表长度大于8 & table.length >= MIN_TREEIFY_CAPACITY(64)，将链表转换为红黑树。
链表长度为什么大于8？而不是6、10、16、20等等？这其实是和加载因子有点关系。

在源码中有这样一段注释

 Because TreeNodes are about twice the size of regular nodes, we
 use them only when bins contain enough nodes to warrant use
 (see TREEIFY_THRESHOLD). And when they become too small (due to
 removal or resizing) they are converted back to plain bins.  In
 usages with well-distributed user hashCodes, tree bins are
 rarely used.  Ideally, under random hashCodes, the frequency of
 nodes in bins follows a Poisson distribution
 (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 parameter of about 0.5 on average for the default resizing
 threshold of 0.75, although with a large variance because of
 resizing granularity. Ignoring variance, the expected
 occurrences of list size k are (exp(-0.5) * pow(0.5, k) / factorial(k)).
 The first values are:

 0:    0.60653066
 1:    0.30326533
 2:    0.07581633
 3:    0.01263606
 4:    0.00157952
 5:    0.00015795
 6:    0.00001316
 7:    0.00000094
 8:    0.00000006
 more: less than 1 in ten million

理想情况下，在随机哈希码下，节点出现的频率在table桶中遵循泊松分布。当加载因子是0.75f时，碰撞8次的概率微乎其微。
同时针对箱子中链表长度超过8以后要做另外的优化（一是优化的概率较小，不一定能碰撞8次，二是优化过后的效率提升明显）。

如果table.length < MIN_TREEIFY_CAPACITY(64)，那么会触发HashMap扩容机制，table的长度调整为现table长度的2倍，扩容后会重新计算桶中各节点的新位置下标。

初始化传入的容量为32

+---+
| 0 |
+---+
+---+    +---+    +---+    +---+    +---+    +---+    +---+    +---+    +---+
| 1 | -> |i1 | -> |i2 | -> |i3 | -> |i4 | -> |i5 | -> |i6 | -> |i7 | -> |i8 |
+---+    +---+    +---+    +---+    +---+    +---+    +---+    +---+    +---+
+---+
| 2 |
+---+
+---+
| 3 |
+---+
more than...

在put i9到下标为1的桶中时，会触发是否转换为红黑树的条件判定，最后得出，需要对当前table进行扩容，扩容后重新计算桶中各节点的新位置下标，有可能是下面的情况：

+---+
| 0 |
+---+
+---+    +---+    +---+    +---+    +---+
| 1 | -> |i1 | -> |i2 | -> |i3 | -> |i4 |
+---+    +---+    +---+    +---+    +---+
+---+    +---+    +---+    +---+    +---+
| 2 | -> |i5 | -> |i6 | -> |i7 | -> |i8 |
+---+    +---+    +---+    +---+    +---+
+---+
| 3 |
+---+

实际情况会产生各种各样的情况，这里我只是举个例子。这样一来put i9到下标为1的桶中时，就不会将桶1中的链表转换为红黑树。

3.5 回归链表存储

当我们某个桶中的红黑树容量退化到UNTREEIFY_THRESHOLD（6）时，会将红黑树转化为链表进行存储。
remove方法和红黑树节点的拆分方法，会触发校验是否退回到链表。

Java数据结构之HashMap

0、HashMap 简介

1、HashMap 属性

`static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;` 默认初始容量

`static final int MAXIMUM_CAPACITY = 1 << 30;` 最大容量

`static final float DEFAULT_LOAD_FACTOR = 0.75f;` 默认加载因子

`static final int TREEIFY_THRESHOLD = 8;` 树化阀值

`static final int UNTREEIFY_THRESHOLD = 6;` 树还原链表阀值

`static final int MIN_TREEIFY_CAPACITY = 64;` 最小的树形化容量

`static class Node<K,V>` 节点，真正存放键值对的节点

`transient Node<K,V>[] table;` tables数组

`transient Set<Map.Entry<K,V>> entrySet;` 保存缓存的entrySet()

`transient int size;` map中key-value的数量

`transient int modCount;` 被修改的次数

`int threshold;` 临界值，当实际大小(容量*填充因子)超过临界值时，会进行扩容

`final float loadFactor;` 加载因子

2、HashMap 构造函数

3、HashMap 核心解读

3.1 我们从从下面代码进行解读

3.1.1 通过HashMap的空构造函数示例化了一个对象map

3.1.2 map调用put()方法，存入键值对

3.1.3 map调用get()方法，获取key对应的value。

HashMap

1、容量

2、加载因子 & 扩容

3、存储key-value

3.1 put

3.2 hash冲突

3.3 尾插法

3.4 树化

3.5 回归链表存储

猜你喜欢

热点阅读

Java数据结构之HashMap

0、HashMap 简介

1、HashMap 属性

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 默认初始容量

static final int MAXIMUM_CAPACITY = 1 << 30; 最大容量

static final float DEFAULT_LOAD_FACTOR = 0.75f; 默认加载因子

static final int TREEIFY_THRESHOLD = 8; 树化阀值

static final int UNTREEIFY_THRESHOLD = 6; 树还原链表阀值

static final int MIN_TREEIFY_CAPACITY = 64; 最小的树形化容量

static class Node<K,V> 节点，真正存放键值对的节点

transient Node<K,V>[] table; tables数组

transient Set<Map.Entry<K,V>> entrySet; 保存缓存的entrySet()

transient int size; map中key-value的数量

transient int modCount; 被修改的次数

int threshold; 临界值，当实际大小(容量*填充因子)超过临界值时，会进行扩容

final float loadFactor; 加载因子

2、HashMap 构造函数

3、HashMap 核心解读

3.1 我们从从下面代码进行解读

3.1.1 通过HashMap的空构造函数示例化了一个对象map

3.1.2 map调用put()方法，存入键值对

3.1.3 map调用get()方法，获取key对应的value。

HashMap

1、容量

2、加载因子 & 扩容

3、存储key-value

3.1 put

3.2 hash冲突

3.3 尾插法

3.4 树化

3.5 回归链表存储

猜你喜欢

热点阅读

`static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;` 默认初始容量

`static final int MAXIMUM_CAPACITY = 1 << 30;` 最大容量

`static final float DEFAULT_LOAD_FACTOR = 0.75f;` 默认加载因子

`static final int TREEIFY_THRESHOLD = 8;` 树化阀值

`static final int UNTREEIFY_THRESHOLD = 6;` 树还原链表阀值

`static final int MIN_TREEIFY_CAPACITY = 64;` 最小的树形化容量

`static class Node<K,V>` 节点，真正存放键值对的节点

`transient Node<K,V>[] table;` tables数组

`transient Set<Map.Entry<K,V>> entrySet;` 保存缓存的entrySet()

`transient int size;` map中key-value的数量

`transient int modCount;` 被修改的次数

`int threshold;` 临界值，当实际大小(容量*填充因子)超过临界值时，会进行扩容

`final float loadFactor;` 加载因子