【上海校区】就业:HashMap实现原理和扩容机制 - 黑马程序员技术交流社区

当向HashMap中put(key,value)时，会首先通过hash算法计算出存放到数组中的位置，比如位置索引为i，将其放入到Entry中，如果这个位置上面已经有元素了，那么就将新加入的元素放在链表的头上，最先加入的元素在链表尾。比如，第一个键值对A进来，通过计算其key的hash得到的index=0，记做:Entry[0] = A。一会后又进来一个键值对B，通过计算其index也等于0，现在怎么办？HashMap会这样做:B.next = A,Entry[0] = B,如果又进来C,index也等于0,那么C.next = B,Entry[0] = C；这样我们发现index=0的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起,也就是说数组中存储的是最后插入的元素。

[Java] 纯文本查看 复制代码

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;      // HashMap初始容量大小(16) 

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

transient int size;                                       // The number of key-value mappings contained in this map

static final float DEFAULT_LOAD_FACTOR = 0.75f;          // 负载因子

HashMap的容量size乘以负载因子[默认0.75] = threshold;  // threshold即为开始扩容的临界值

transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;    // HashMap的基本构成Entry数组

   当HashMap中的元素个数超过数组大小(数组总大小length,不是数组中个数size)*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中元素个数超过16*0.75=12（这个值就是代码中的threshold值，也叫做临界值）的时候，就把数组的大小扩展为 2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置。
   0.75这个值成为负载因子，那么为什么负载因子为0.75呢？这是通过大量实验统计得出来的，如果过小，比如0.5，那么当存放的元素超过一半时就进行扩容，会造成资源的浪费；如果过大，比如1，那么当元素满的时候才进行扩容，会使get,put操作的碰撞几率增加。
   HashMap中扩容是调用resize()方法，方法源码：

[Java] 纯文本查看 复制代码

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

}

//旧数组中元素往新数组中迁移

void transfer(Entry[] newTable) {

    //旧数组

    Entry[] src = table;

    //新数组长度

    int newCapacity = newTable.length;

    //遍历旧数组

    for (int j = 0; j < src.length; j++) {

        Entry<K,V> e = src[j];

        if (e != null) {

            src[j] = null;

            do {

                Entry<K,V> next = e.next;

                int i = indexFor(e.hash, newCapacity);//放在新数组中的index位置

                e.next = newTable;//实现链表结构，新加入的放在链头，之前的的数据放在链尾

                newTable = e;

                e = next;

            } while (e != null);

        }

    }

}

可以看到HashMap不是无限扩容的，当达到了实现预定的MAXIMUM_CAPACITY，就不再进行扩容。