HashMap 里的“bucket”、“负载因子” 介绍

对于 HashMap 及其子类而言，它们采用 Hash 算法来决定集合中元素的存储位置。当系统开始初始化 HashMap 时，系统会创建一个长度为 capacity 的 Entry 数组，这个数组里可以存储元素的位置被称为“桶（bucket）”，每个 bucket 都有其指定索引，系统可以根据其索引快速访问该 bucket 里存储的元素。

无论何时，HashMap 的每个“桶”只存储一个元素（也就是一个 Entry），由于 Entry 对象可以包含一个引用变量（就是 Entry 构造器的的最后一个参数）用于指向下一个 Entry，因此可能出现的情况是：HashMap 的 bucket 中只有一个 Entry，但这个 Entry 指向另一个 Entry ——这就形成了一个 Entry 链。如图 1 所示：

66679083-1285-397d-860a-83fc41efeedd

HashMap 的读取实现

当 HashMap 的每个 bucket 里存储的 Entry 只是单个 Entry ——也就是没有通过指针产生 Entry 链时，此时的 HashMap 具有最好的性能：当程序通过 key 取出对应 value 时，系统只要先计算出该 key 的 hashCode() 返回值，在根据该 hashCode 返回值找出该 key 在 table 数组中的索引，然后取出该索引处的 Entry，最后返回该 key 对应的 value 即可。看 HashMap 类的 get(K key) 方法代码：

public V get(Object key)   
{   
 // 如果 key 是 null，调用 getForNullKey 取出对应的 value   
 if (key == null)   
     return getForNullKey();   
 // 根据该 key 的 hashCode 值计算它的 hash 码  
 int hash = hash(key.hashCode());   
 // 直接取出 table 数组中指定索引处的值，  
 for (Entry<K,V> e = table[indexFor(hash, table.length)];   
     e != null;   
     // 搜索该 Entry 链的下一个 Entr   
     e = e.next)         // ①  
 {   
     Object k;   
     // 如果该 Entry 的 key 与被搜索 key 相同  
     if (e.hash == hash && ((k = e.key) == key   
         || key.equals(k)))   
         return e.value;   
 }   
 return null;   
}

从上面代码中可以看出，如果 HashMap 的每个 bucket 里只有一个 Entry 时，HashMap 可以根据索引、快速地取出该 bucket 里的 Entry；在发生“Hash 冲突”的情况下，单个 bucket 里存储的不是一个 Entry，而是一个 Entry 链，系统只能必须按顺序遍历每个 Entry，直到找到想搜索的 Entry 为止——如果恰好要搜索的 Entry 位于该 Entry 链的最末端（该 Entry 是最早放入该 bucket 中），那系统必须循环到最后才能找到该元素。

归纳起来简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 Hash 算法来决定其存储位置；当需要取出一个 Entry 时，也会根据 Hash 算法找到其存储位置，直接取出该 Entry。由此可见：HashMap 之所以能快速存、取它所包含的 Entry，完全类似于现实生活中母亲从小教我们的：不同的东西要放在不同的位置，需要时才能快速找到它。

HashMap 扩容加载因子

public HashMap(int initialCapacity, float loadFactor) {
    //初始容量不能<0
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: "
                + initialCapacity);
    //初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    //负载因子不能 < 0
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: "
                + loadFactor);
    // 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
    int capacity = 1;
    while (capacity < initialCapacity)
        capacity <<= 1;
    this.loadFactor = loadFactor;
    //设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
    threshold = (int) (capacity * loadFactor);
    //初始化table数组
    table = new Entry[capacity];
    init();
}

在这里提到了两个参数：初始容量，加载因子。

这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中桶的数量，初始容量是创建哈希表时的容量，

加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。

对于使用链表法的散列表来说，查找一个元素的平均时间是O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；

如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。系统默认负载因子为0.75，一般情况下我们是无需修改的。

加载因子：

loadFactor

扩容：

void addEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold) // 这里是关键，一旦大于等于threshold的数值
            resize(2 * table.length); // 将会引起容量2倍的扩大
    }

void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity]; // 新的容器空间
        transfer(newTable); // 复制数据过去
        table = newTable;
        threshold = (int)(newCapacity * loadFactor); // 重新计算threshold的值
    }

void transfer(Entry[] newTable) {
         // 保留原数组的引用到src中，
         Entry[] src = table;
         // 新容量使新数组的长度
         int newCapacity = newTable.length;
 　　　　　// 遍历原数组
         for (int j = 0; j < src.length; j++) {
             // 获取元素e
             Entry<K,V> e = src[j];
             if (e != null) {
                 // 将原数组中的元素置为null
                 src[j] = null;
                 // 遍历原数组中j位置指向的链表
                 do {
                     Entry<K,V> next = e.next;
                     // 根据新的容量计算e在新数组中的位置
                     int i = indexFor(e.hash, newCapacity);
                     // 将e插入到newTable[i]指向的链表的头部
                     e.next = newTable[i];
                     newTable[i] = e;
                     e = next;
                 } while (e != null);
             }
         }
     }

通过上面的transfer方法可以看出，

e.next=newTable[i];

newTable[i]=e;

链表存储倒过来了，最先出来的会将其next指向null,后面的就指向前一个，当然数据只有原来的一部分。

===================================================================

随着HashMap中元素的数量越来越多，发生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响HashMap的速度，

为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理。

该临界点在当HashMap中元素的数量等于table数组长度*加载因子。

但是扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。

所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

问题：

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。