探究HashMap的工作原理

   <p>摘要：经过大学四年，我也刚刚毕业了3个月了，学习android也有一两年了，可是在大学的生活中，磨练出来的解决实际问题的能力是有的，完成开发任务还是可以的，但是总觉得技术遇到了瓶颈期，没有办法进步很多。因此想静下心来看JDK的源码，看看这些人是怎么设计出来的？为什么要这么设计？我能从中体会到什么？对我今后的职业生涯有什么帮助？跟着优秀的人一起成长吧。</p>    <p>我们用HaspMap最关心的两个方法和几个变量是：</p>    <pre>  <code class="language-java">/** 默认的初始化容量，2^4 */  static final int DEFAULT_INITIAL_CAPACITY = 16;    /** 默认的负载因子 */  static final float DEFAULT_LOAD_FACTOR = 0.75f;    /*数组，Entry是存放Key value的基础bean */  transient Entry[] table;    /** 负载因子*/  final float loadFactor;    /** *下一次的负载table容量 (capacity * load factor) *  int threshold;    public V put(K key,V value)    public V get(Object key)</code></pre>    <p>为了帮助理解和记忆，贴上两张图：</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/bcf9c4ef67b0a0dd35e425ad8cdf9c2c.png"></p>    <p style="text-align:center">Paste_Image.png</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/2269d168cdb5485e09c75fa72253dc02.png"></p>    <p style="text-align:center">Paste_Image.png</p>    <p>从上图我们可以发现哈希表是由 <strong>数组+链表</strong> 组成的，一个长度为 我们看到的第一个变量 <strong>DEFAULT_INITIAL_CAPACITY=16</strong> 的数组中，每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key.hashCode()%table.length)获得，也就是元素的key的哈希值对数组长度取模得到。</p>    <p>HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。HashMap里面实现一个静态内部类Entry，其重要的属性有key,value,next，从属性key,value我们就能很明显的看出来Entry就是HashMap键值对实现的一个基础bean，我们上面说到HashMap的基础就是一个线性数组，这个数组就是Entry[]，Map里面的内容都保存在Entry[]里面。</p>    <h3><strong>HashMap存取过程</strong></h3>    <pre>  <code class="language-java">public V put(K key, V value) {           if (key == null)              return putForNullKey(value);           int hash = hash(key.hashCode());          int i = indexFor(hash, table.length);          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);                      return oldValue;            }      }           modCount++;          addEntry(hash, key, value, i);    return null;  }</code></pre>    <p>看源码得出几个结论：</p>    <p>1.HashMap可以存储null的key。</p>    <p>2.通过key.hashCode找到hash值，然后跟table.length的取模，得到数组下标。然后遍历链表，如果hash值且key值相等，则替换原来的值。</p>    <p>3.table添加新的元素时并没有奇怪，奇怪的是我们知道数据的默认容量是16，超过了16怎么办，HashMap是怎么处理的呢？</p>    <p>所以要看一下上述代码中addEntry这个方法里面到底做什么操作。</p>    <pre>  <code class="language-java">void addEntry(int hash, K key, V value, int bucketIndex) {          Entry<K,V> e = table[bucketIndex];          table[bucketIndex] = new Entry<>(hash, key, value, e);          if (size++ >= threshold)              resize(2 * table.length);      }</code></pre>    <p>到这里已经很明显，我们发现了HashMap的处理方式，是size > threshold的时候就会去扩容。那么这个threshold是什么东西呢？文章的开头我们已经把他列出来了，threshold = capacity <em>loadFactor的结果，loadFactor是负载因此，capacity是容量。那么我们可以得出很简单的结论就是首次初始化的时候threshold = DEFAULT_INITIAL_CAPACITY（16）</em> DEFAULT_LOAD_FACTOR （0.75） ，就是超过了容量的75%的时候就会去扩容。</p>    <p>当哈希表的容量超过默认容量时，必须调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。</p>    <p>我带着好奇心继续探索resize这个方法。</p>    <pre>  <code class="language-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);      }        /**       * Transfers all entries from current table to newTable.       */      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;                      //重新计算index                      int i = indexFor(e.hash, newCapacity);                      e.next = newTable[i];                      newTable[i] = e;                      e = next;                  } while (e != null);              }          }      }</code></pre>    <p>到这里基本上清楚了HashMap的进行put时候的整个过程了。相同get方法我就不贴代码了。有兴趣可以去研究源码。</p>    <p>当我看源码看到这一步我可能比较困惑，HashMap究竟优势在哪儿？</p>    <p>我们要分析一下HashMap的数据结构，上述我们已经了解HashMap的数据结构是 <strong>数组加链表。</strong></p>    <p>数组存储区间是连续的，占用内存严重，故空间复杂的很大。但数组的二分查找时间复杂度小，为O(1)；数组的特点是：寻址容易，插入和删除困难；</p>    <p>链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大，达O（N）。链表 <strong>的特点是：寻址困难，插入和删除容易。</strong></p>    <p> </p>    <p> </p>    <p>来自：http://www.jianshu.com/p/006f9f446fcb</p>    <p> </p>