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需要重新调整大小了,它们会同时试着调整大小。

在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。

如果条件竞争发生了,那么就死循环了。

对于高并发情况下的扩容,下面有篇文章讲解的很好

http://mp.weixin.qq.com/s?__biz=MzIxMjE5MTE1Nw==&mid=2653192000&idx=1&sn=118cee6d1c67e7b8e4f762af3e61643e&chksm=8c990d9abbee848c739aeaf25893ae4382eca90642f65fc9b8eb76d58d6e7adebe65da03f80d&scene=21#wechat_redirect

链接引用:

http://www.javacui.com/Theory/377.html

http://blog.csdn.net/zhangerqing/article/details/8193118

http://www.cnblogs.com/matrix-skygirl/archive/2013/01/17/2864919.html

(全文完)

(转载本站文章请注明作者和出处 HashMap 里的“bucket”、“负载因子” 介绍