HashMap源码分析及冲突处理的细节

1.  首先看1下hashmap的数据结构，可以看到是数组加链表实现的。

transient Entry<K,V>[] table =(Entry<K,V>[]) EMPTY_TABLE;

可以看到它的实现是1个Entry<K,V>类型的名为table的数组。而Entry是HashMap中的1个内部类。

static class Entry<K,V> implementsMap.Entry<K,V> {

       final K key;

       V value;

       Entry<K,V> next;

       int hash;

       它有4个属性，key，value，next，hash。由于有next属性，所以自然会想到链表的结点类，事实上，当出现hash冲突时，由于HashMap使用链地址法来解决冲突。所以table数组的每个元素就会构成链表结构。所以可以说HashMap就是1个存储链表的数组。

2.   HashMap的table数组的默许大小是16，并且大小永久是2的n次方。它还有1个负载因子，默许为0.75，可以通过带参数的构造方法自己指定。负载因子loadFactor的作用是：HashMap中的实际的数据大小除以总容量(initialCapacity),当值到达时，的总容量自动扩大1倍。

  staticfinal int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

static final float DEFAULT_LOAD_FACTOR = 0.75f;

   计算threshold，值为capacity *loadFactor。

threshold = (int) Math.min(capacity * loadFactor,MAXIMUM_CAPACITY +1);

   这里就会判断，当size的值大于threshold（即capacity *loadFactor）时，就会进行扩容。

if ((size >= threshold) && (null != table[bucketIndex])){

            resize(2 * table.length);

3.接下来以put方法作为入口，进行分析。

1.首先进行hash运算，并求出将要存入的数组下标。

int hash = hash(key);

int i = indexFor(hash,table.length);

     接下来看看计算下标的算法是如何实现的。进入到indexFor方法中，实现的代码以下：

static int indexFor(int h,int length) {

        // assertInteger.bitCount(length) == 1 : "length must be a non-zero power of2";

        return h &(length⑴);

    }

    具体是h &(length⑴)，这样计算的值介于0和length⑴之间，有点类似于hash%length 的求模运算。之所以用&运算我认为是位运算的效力更高吧。

2.然后是下面这段代码：

for (Entry<K,V> e = table[i]; e != null; e = e.next) {

            Object k;

            if (e.hash == hash&& ((k = e.key) == key || key.equals(k))) {

                V oldValue =e.value;

                e.value =value;

               e.recordAccess(this);

                returnoldValue;

            }

        }

        modCount++;

        addEntry(hash,key,value,i);

        会判断table[i]是不是为null，这是会出现两种情况，先分析第1种情况，即table[i]还没有元素，是null的情况，这时候循环就没有履行，继续往下，去履行addEntry方法。addEntry方法中先进行判断是不是需要扩容，如果需要，就进行扩容。然后又进入到createEntry方法中。它的代码实现以下：

void createEntry(int hash,K key,V value,int bucketIndex) {

        Entry<K,V> e =table[bucketIndex];

        table[bucketIndex] =new Entry<>(hash,e);

        size++;

    }

        它做的工作就是把hash,e4个属性组装成1个Entry的对象e，并将它放在数组下标相应的位置，这时候如果加入的是第1个元素，e则为null,所以next指向了null。最后再把size加1.

        下面分析第2种情况，即即table[i]已有了元素，不是null的情况。这时候会履行上面的那1段for循环，这个循环的作用就是顺次遍历全部table[i]链表，并且判断这个链表的每个元素的key是不是和新加进来的元素的key相同，如果相同新的value就会覆盖旧的value，即保证HashMap中唯1的key有唯1的value.

         进行完了覆盖的操作后，就会履行剩下的代码，和第1种情况1样，履行addEntry方法。addEntry方法中先进行判断是不是需要扩容，如果需要，就进行扩容。再履行createEntry方法。这时候e = table[bucketIndex];计算出来的e就不为null了，为原来的i下标处的元素。然后又封装1个新的Entry对象，放入到table[i]位置，它的next指向了e,即原来的table[i]处的元素。

        所以通过分析我们可以发现，最后放入的元素总是在这个冲突链表的表头的位置。

        最后，可以看到，当出现冲突时，会把数据放入链表中，每次插入新的元素都会对全部链表进行遍历操作，影响程序的效力。所以当我们向HasnMap中放入的key的数据类型是自定义类型的时候，要依照规范公道的实现hashcode和equals方法，尽可能避免冲突。另外，由于它的底层实现也是数组，所以也要尽可能避免扩容。最好能估算出初始的大小，而对负载因子，听说0.75是计算出的最好值，所以还是用默许的吧。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!