<p>以 Android 最新源码里面的 HashMap 为例，其实也和 JDK8 里面的 HashMap 差不多。</p>    <p>位置：[aosp]/libcore/ojluni/src/main/java/java/util/HashMap.java</p>    <h2><strong>思考</strong></h2>    <p>如果从零开始设计一个 HashMap 结构该如何思考？</p>    <p>栈？队列？数组？链表？树？图？</p>    <h2><strong>结构</strong></h2>    <p>早期的 HashMap 的确是只使用了数组和链表，但从 Java8 中开始引入树（红黑树）结构以提高链表过长情况下的性能。</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/b1a2c6a52565f64bdd3000f8e57766e0.png"></p>    <p>数组:</p>    <pre>  <code class="language-java">transient Node<K,V>[] table;  </code></pre>    <p>链表 Node(next)：</p>    <pre>  <code class="language-java">static class Node<K,V> implements Map.Entry<K,V> {   final int hash;   final K key;   V value;   Node<K,V> next;     Node(int hash, K key, V value, Node<K,V> next) {   this.hash = hash;   this.key = key;   this.value = value;   this.next = next;   }  }  </code></pre>    <p>红黑树 TreeNode(parent, left, right)：</p>    <pre>  <code class="language-java">staticfinalclassTreeNode<K,V>extendsLinkedHashMap.LinkedHashMapEntry<K,V>{   TreeNode<K,V> parent; // red-black tree links   TreeNode<K,V> left;   TreeNode<K,V> right;   TreeNode<K,V> prev; // needed to unlink next upon deletion  booleanred;   TreeNode(inthash, K key, V val, Node<K,V> next) {  super(hash,key,val,next);   }  }  </code></pre>    <h2><strong>基本原理</strong></h2>    <p>详细的细节后面会逐步阐述，HashMap 的核心原理就是，把数据的 key 转化为 hash 值，放到某 n 长度的数组中改 hash 对应的 position，比如 hash 为 0，则放在数组的第1个位置，如果 hash 为111，则放在数组的第 112 个位置。这样每次根据 hash 值就能直接知道放在什么位置，或者反过来，根据 hash 值就能直接知道从哪个位置取值。</p>    <p>但是这样做，会面临几个问题：</p>    <p>第一，hash 值一般都是很大，岂不是数组要很大？</p>    <p>这个问题好解决，hash按数组长度取模，这样无论多大的 hash 总能在数组的范围之内。</p>    <p>顺便一问，取模操作：(n - 1) & hash，想想为什么？</p>    <p>第二，取模后，那么多 hash 取模可能重复在数组的同一位置怎么办？</p>    <p>这个叫碰撞冲突，这个时候这个 hash 值对应的 Node 既不能放在正确的 position（已被其他占用），也不能随便的放在其他位置（否则下次就找不到了），我们发现，数组已经不能满足需求了。</p>    <p>上链表！</p>    <p>把这个 Node 挂到已经占用位置的 Node 的 next 上，如果 next 已经被挂了， 那就next-next顺藤摸瓜挂在最后一个 Node 的next上。</p>    <p>第三，挂起来容易，要查询的时候怎么找？</p>    <p>无碰撞冲突的情况下，定位到数组位置就找到了。</p>    <p>有碰撞冲突的情况下，定位到数组后，next-next顺藤摸瓜，根据key是否相等来判断是否找到（hash相同碰撞了，但是key总是不同的）。</p>    <p>第四， 好像没用到红黑树啊？</p>    <p>当链表过长时，可以用红黑树去优化性能，关于红黑树这里不多讲。</p>    <h2><strong>三个概念</strong></h2>    <p>容量、负载因子、阈值：</p>    <ul>     <li>容量</li>    </ul>    <pre>  <code class="language-java">// 因为用的是数组，定义一个容量是一个好事，比每次需要动态改变容量性能总是要好的多的。  // 初始化默认值 16  staticfinalintDEFAULT_INITIAL_CAPACITY =1<<4;  transientNode<K,V>[] table;  transientintsize;  </code></pre>    <ul>     <li>负载因子</li>    </ul>    <pre>  <code class="language-java">// 如果频繁的发生碰撞，那么性能就会直线下降。  // 为了提高性能，不要等到满了才扩容，而是当实际个数到达某个比例就扩容。  // 这个比例就是负载因子：loadFactor，默认为0.75。  finalfloatloadFactor;  </code></pre>    <ul>     <li>阈值</li>    </ul>    <pre>  <code class="language-java">// 超过这个值则以翻倍形式扩容(resize)  // 简单的计算：threshold = capacity * load factor  intthreshold;  </code></pre>    <h2><strong>插入(PUT)</strong></h2>    <p>见注释。</p>    <pre>  <code class="language-java">/**   * Implements Map.put and related methods   *   * @paramhash hash for key   * @paramkey the key   * @paramvalue the value to put   * @paramonlyIfAbsent if true, don't change existing value   * @paramevict if false, the table is in creation mode.   * @returnprevious value, or null if none   */  finalVputVal(inthash, K key, V value,booleanonlyIfAbsent,  booleanevict) {   Node<K,V>[] tab; Node<K,V> p; intn, i;  if((tab = table) ==null|| (n = tab.length) ==0)  // 空检查   n = (tab = resize()).length;  if((p = tab[i = (n -1) & hash]) ==null)  // 不存在，直接插入  // 注意 i = (n - 1) & hash 就是取模定位数组的索引   tab[i] = newNode(hash, key, value, null);  else{  // 已存在：一模一样的值或者碰撞冲突   Node<K,V> e; K k;  if(p.hash == hash &&   ((k = p.key) == key || (key != null&& key.equals(k))))  // 已经存在一个一模一样的值   e = p;  elseif(pinstanceofTreeNode)  // 树，略   e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);  else{  // 碰撞冲突，顺藤摸瓜挂在链表的最后一个next上  for(intbinCount =0; ; ++binCount) {  if((e = p.next) ==null) {   p.next = newNode(hash, key, value, null);  if(binCount >= TREEIFY_THRESHOLD -1)// -1 for 1st   treeifyBin(tab, hash);  break;   }  if(e.hash == hash &&   ((k = e.key) == key || (key != null&& key.equals(k))))  break;   p = e;   }   }  // 注意：if true, don't change existing value  if(e !=null) {// existing mapping for key   V oldValue = e.value;  if(!onlyIfAbsent || oldValue ==null)   e.value = value;   afterNodeAccess(e);  returnoldValue;   }   }   ++modCount;  if(++size > threshold)   resize();   afterNodeInsertion(evict);  returnnull;  }  </code></pre>    <h2><strong>查询(GET)</strong></h2>    <p>见注释。</p>    <pre>  <code class="language-java">/**   * Implements Map.get and related methods   *   * @paramhash hash for key   * @paramkey the key   * @returnthe node, or null if none   */  finalNode<K,V>getNode(inthash, Object key){   Node<K,V>[] tab; Node<K,V> first, e; intn; K k;  if((tab = table) !=null&& (n = tab.length) >0&&   (first = tab[(n - 1) & hash]) !=null) {  // 注意 i = (n - 1) & hash 就是取模定位数组的索引  if(first.hash == hash &&// always check first node   ((k = first.key) == key || (key != null&& key.equals(k))))  // 找到：hash相等 和 key也相等  returnfirst;  if((e = first.next) !=null) {  if(firstinstanceofTreeNode)  // 递归树查找  return((TreeNode<K,V>)first).getTreeNode(hash, key);   do {  // 遍历链表  if(e.hash == hash &&   ((k = e.key) == key || (key != null&& key.equals(k))))  returne;   } while((e = e.next) !=null);   }   }  returnnull;  }  </code></pre>    <h2><strong>扩容(Resize)</strong></h2>    <p>resize 的代码我就不贴了，这里只强调一点：</p>    <p>每次扩容都需要重新分配数组，并把老的值再分配到新的数组，代价还是挺大的，所以尽量避免扩容。</p>    <p>举个例子，现在可能大约有 100 个</p>    <p>，我们比较一下：</p>    <pre>  <code class="language-java">// 128 = 2^7 < 100/0.75 < 2^8 = 256  // 最简单的形式，只是纯粹的声明变量  // 初始化容量16 = 2^4，最后会到2^8才够用  // 中间会经历了4次扩容  newHashMap<String, String>();    // 指定容量，优化后，无扩容，又刚好够用  newHashMap<String, Strring>(256);  </code></pre>    <h2><strong>其他</strong></h2>    <p>常见的几个问题的简要说明。</p>    <p><strong>HashMap 和 HashTable 区别</strong></p>    <p>在 HashMap 的官方文档第一段里面就有句话：</p>    <p>The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.</p>    <p>简简单单的一句话道出了两点核心区别：</p>    <ol>     <li>HashMap是unsynchronized，要注意线程安全；</li>     <li>HashMap允许null而HashTable不允许null。</li>    </ol>    <p><strong>同步</strong></p>    <p>HashMap 不是线程安全的，如果有并发问题，请使用 ConcurrentHashMap （当然也可以用 HashTable ）。</p>    <p>这个问题其实很重要， 《疫苗：Java HashMap的死循环》 提到，淘宝因为没考虑到 HashMap 在并发的情况下会有问题，出现死循环，CPU 达到100%。</p>    <p><strong>Fail-Fast机制</strong></p>    <p>在创建迭代器后，如果发现 HashMap 发生变化，则抛出 ConcurrentModificationException 异常，这就是 Fail-Fast 机制。</p>    <p>这也是一种契约约束吧。</p>    <p>HashMap 主要是通过 modCount 来记录和检测的，大概代码片段如下（仅作示意）：</p>    <pre>  <code class="language-java">if(map.modCount != expectedModCount)  thrownewConcurrentModificationException();  </code></pre>    <p><strong>巧妙的取模</strong></p>    <p>加入数组长度是 n, 如果要对 hash 取模，大家可能想到的解法是：</p>    <pre>  <code class="language-java">hash % n  </code></pre>    <p>而 HashMap 采用的方法是：</p>    <pre>  <code class="language-java">// n 是 2 的次方，所以 n - 1 的而进制01111111111..  // hash “与” 01111111111实际上是取保留低位值，结果在 n 的范围之内，类似于取模。  // 对于我这种没见过市面的人来说，还是很巧妙的。  hash & (n - 1)  </code></pre>    <p>后者比前者性能据说要高好几倍，可以考虑一下为什么。</p>    <p><strong>数组长度为什么总是设定为 2 的 N 次方？</strong></p>    <p>从上面的问题的答案中，基本可以管中窥豹，一切都是为了性能。</p>    <p><strong>1. 取模快。</strong></p>    <p>其实就是上面为什么快的原因：位与取模比 % 取模要快的多。</p>    <p><strong>2. 分散平均，减少碰撞。</strong></p>    <p>这个是主要原因。</p>    <p>如果二进制某位包含 0，则此位置上的数据不同对应的 hash 却是相同，碰撞发生，而 (2^x - 1) 的二进制是 0111111…，分散非常平均，碰撞也是最少的。</p>    <h2><strong>小结</strong></h2>    <p>HashMap 做为一个经典的数据结构，值得我们去分析原理去理解透彻，很有帮助。</p>    <p>而且 HashMap 也是是最常见的面试问题。</p>    <p> </p>    <p>来自：http://www.jayfeng.com/2016/11/17/理解HashMap/</p>    <p> </p>