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),当值到达loadFactor时,HashMap的总容量自动扩大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, key, value, e);

        size++;

    }

 

        它做的工作就是把hash,key, value, 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是计算出的最好值,所以还是用默许的吧。

 

 

 

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

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

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡