HashMap工作原理

   <p>相信大家不管是在Java还是安卓面试过程中，或多或少都会被问及HashMap的工作原理，小编今天大概看了一下Android中HashMap的源码，将结果整理如下，如有不对之处请批评指正：</p>    <h2><strong>一、HashMap的数据结构</strong></h2>    <p>其实HashMap的存储数据结构是一个散列数组+链表的数据结构，如图：</p>    <p style="text-align:center"><img src="https://simg.open-open.com/show/0bf4b7deb54038997e65e0f133654875.png"></p>    <p style="text-align:center">HashMap的存储数据结构</p>    <p>我们都知道往HashMap里存储值时会传入key和value，HashMap首先会拿到key相对应的hash值，</p>    <p>接着通过hash值计算存放数组的下标，再将value值存放在数组对应下标下的链表里。</p>    <p>接下来我们就根据源码看看HashMap的存取实现。</p>    <h2><strong>二、HashMap的存取实现</strong></h2>    <p>1） put（key，value）</p>    <pre>  <code class="language-java">@Override   public V put(K key, V value) {          if (key == null) {                  return putValueForNullKey(value);          }            int hash = Collections.secondaryHash(key);          HashMapEntry<K, V>[] tab = table;          int index = hash & (tab.length - 1);          for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {                   if (e.hash == hash && key.equals(e.key)) {                           preModify(e);                           V oldValue = e.value;                           e.value = value;                           return oldValue;                   }           }             // No entry for (non-null) key is present; create one           modCount++;           if (size++ > threshold) {                   tab = doubleCapacity();                   index = hash & (tab.length - 1);           }           addNewEntry(key, value, hash, index);           return null;  }</code></pre>    <p>由源码可以看出，程序首先会检测key值是否为空，如果为空则做空值处理（null key总是存放在entryForNullKey对象中）；接着对key的hashCode()做hash，然后再计算index；接着在Entry[index]下的链表里查找是否存在hash和key值与插入key的一样的HashMapEntry对象，如果有的话，则将旧值替换成value，并返回旧值；否则通过addNewEntry插入新的HashMapEntry对象，源码如下：</p>    <pre>  <code class="language-java">void addNewEntry(K key, V value, int hash, int index) {          table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);  }</code></pre>    <pre>  <code class="language-java">HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {          this.key = key;          this.value = value;          this.hash = hash;          this.next = next;  }</code></pre>    <p>由方法可知，插入方法是将新的HashMapEntry对象当成table[index]下链表的头结点，而用新的HashMapEntry对象的next指向原table[index]下链表的头结点，以达成插入链表头结点的目的。</p>    <p>2） get（key）</p>    <pre>  <code class="language-java">public V get(Object key) {          if (key == null) {                  HashMapEntry<K, V> e = entryForNullKey;                  return e == null ? null : e.value;          }            int hash = Collections.secondaryHash(key);          HashMapEntry<K, V>[] tab = table;          for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];            e != null; e = e.next) {                    K eKey = e.key;                    if (eKey == key || (e.hash == hash && key.equals(eKey))) {                            return e.value;                    }           }           return null;  }</code></pre>    <p>由源码可以看出，程序首先会判断key值是否为空，如果为空，则检查entryForNullKey有没有存放值，有的话则返回；接着对key的hashCode()做hash，然后再计算index；接着在Entry[index]下的链表里查找是否存在hash和key值与插入key的一样的HashMapEntry对象，有的话则返回。</p>    <h2><strong>三、HashMap的大小问题</strong></h2>    <ul>     <li>如果没有设置初始大小，即直接new HashMap()，size为MINIMUM_CAPACITY 的二分之一 <pre>  <code class="language-java">/** * An empty table shared by all zero-capacity maps (typically from default  * constructor). It is never written to, and replaced on first put. Its size  * is set to half the minimum, so that the first resize will create a   * minimum-sized table.   */  private static final Entry[] EMPTY_TABLE              = new HashMapEntry[MINIMUM_CAPACITY >>> 1];  public HashMap() {          table = (HashMapEntry<K, V>[]) EMPTY_TABLE;          threshold = -1; // Forces first put invocation to replace EMPTY_TABLE  }</code></pre> </li>     <li> <p>如果有设置初始大小，即调用new HashMap(capacity)， 注意table初始大小并不是构造函数中的initialCapacity！！而是 >= initialCapacity并且是2的n次幂的整数！！！！</p> <pre>  <code class="language-java">public HashMap(int capacity) {         if (capacity < 0) {                 throw new IllegalArgumentException("Capacity: " + capacity);         }           if (capacity == 0) {                 @SuppressWarnings("unchecked")                 HashMapEntry<K, V>[] tab = (HashMapEntry<K, V>[]) EMPTY_TABLE;                 table = tab;                 threshold = -1; // Forces first put() to replace EMPTY_TABLE                 return;         }           if (capacity < MINIMUM_CAPACITY) {                 capacity = MINIMUM_CAPACITY;         } else if (capacity > MAXIMUM_CAPACITY) {                 capacity = MAXIMUM_CAPACITY;         } else {                 capacity = Collections.roundUpToPowerOfTwo(capacity);         }         makeTable(capacity);  }</code></pre> <p>其中Collections的roundUpToPowerOfTwo方法，就是获取大于等于 某个整数 并且是 2 的幂数的整数</p> </li>     <li>再散列 <strong>rehash</strong> ：当哈希表的容量超过默认容量时，doubleCapacity会调整table的为原来的2倍。这时，需要创建一张新表，将原表的映射到新表中。 <pre>  <code class="language-java">private HashMapEntry<K, V>[] doubleCapacity() {          HashMapEntry<K, V>[] oldTable = table;          int oldCapacity = oldTable.length;          if (oldCapacity == MAXIMUM_CAPACITY) {                  return oldTable;          }          int newCapacity = oldCapacity * 2;          HashMapEntry<K, V>[] newTable = makeTable(newCapacity);          if (size == 0) {                  return newTable;          }          for (int j = 0; j < oldCapacity; j++) {                  /*                    * Rehash the bucket using the minimum number of field writes.                    * This is the most subtle and delicate code in the class.                    */                   HashMapEntry<K, V> e = oldTable[j];                   if (e == null) {                           continue;                   }                   int highBit = e.hash & oldCapacity;                   HashMapEntry<K, V> broken = null;                   newTable[j | highBit] = e;                   for (HashMapEntry<K, V> n = e.next; n != null; e = n, n = n.next) {                            int nextHighBit = n.hash & oldCapacity;                            if (nextHighBit != highBit) {                                    if (broken == null)                                            newTable[j | nextHighBit] = n;                                    else                                            broken.next = n;                                        broken = e;                                        highBit = nextHighBit;                             }                   }                   if (broken != null)                       broken.next = null;           }           return newTable;  }</code></pre> </li>    </ul>    <p> </p>    <p>来自：http://www.jianshu.com/p/142aac8232e2</p>    <p> </p>