HashMap的存取解析

   今天想了解点别的了，HashMap的存取解析。大家都知道HashMap是键值对存在的，key-value的形式。但，内部是怎么存储的？我们一起来看看吧

  标注：基于的jdk版本为1.6.0_45

  First，大家都知道Map的entrySet方法返回的是Set<Entry>，所以就好奇Entry到底是个什么东西？

    Entry是接口，是Map接口中的一个内部接口，Map提供的接口就不给大家介绍了，Entry提供的接口方法有：

      K getKey() //获取Entry的key值

      V getValue() //获取Entry的value值

      setValue(V value) //替换value值

      equals(Object o)//你懂的

      hashCode() //你也懂的

 其实这些方法大家也不陌生  

    Second，HashMap.Entry实现Map.Entry接口？

       看代码，我们发现HashMap.Entry是一个Link结构，并且key和value为其属性，并使用next指向下一个Entry。

        关于方法的实现就不介绍了，HashMap额外提供了两个空方法，一个是recordAccess，一个是recordRemoval，在HashMap的介绍中，不多做介绍，在后面的LinkedHashMap再详细说明

 

   Third，HashMap怎么利用Entry存放key-Value呢？并且，HashMap是怎么遍历的呢？是对Entry的Link遍历？有了这一连串的疑问之后，继续探索吧！

       HashMap使用Entry数组，如下图1：

 上图中transient修饰符是啥意思呢？

    是一个临时非序列化的变量，不可以被序列化存放起来。生命周期仅存于内存中。

 Third_First：存放

     HashMap提供的put方法执行操作，请注意putForNullKey和put的方法类似，只是putForNullKey定好了table的存放位置：

     1.获取key的hash。其中的hash方法只是为了保证它有唯一的值，并且null的hash一定是0.

     2.在图1中的table中找到key对应的位置使用的方式 hash & length，确定index

     3.在table[i]存放的Entry对象中继续遍历，看其中是否存在hash、key是否完全一样的，如果是则直接替换

      4.如果步骤3找不到完全匹配的，则直接在table[i]对应的地方最后一个链表节点增加该元素

  

 

    addEntry的处理：1.取到index的Entry；2.重新给一个新的链接，链接的是最新放入的，完全符合队列link；3.长度超过设定扩展至两倍

   

 Third_Second:遍历

  其中用内部类HashIterator处理的，设定一个next Entry和current Entry。next为下一个点，current是当前点。咱们使用的Iterator.next接口具体实现方法为HashIterator的nextEntry。nextEntry方法中1.是对Entry链进行遍历，如果到这个链的队尾，则从table中取得下一个Entry链。2.将之前查找到的Entry返回给前台。源码如下：

 

 一位姓丁的NB同事曾经排查过一个高并发的情况下：HashMap如果EntryA的next指向EntryB，而EntryB的next指向EntryA,会导致get死循环。

 

评论

1 楼 chenliangzg 2016-04-12  

  受益匪浅！