面试题 HashMap 数据结构 实现原理

 null key的存取
 null key总是存放在Entry[]数组的第一个元素。

     private V putForNullKey(V value) { 
         for (Entry<K, V> e = table[0]; e != null; e = e.next) { 
             if (e.key == null) { 
                 V oldValue = e.value;
                 e.value = value;
                 e.recordAccess(this);
                 return oldValue;
             }
         }
         modCount++;
         addEntry(0, null, value, 0);
         return null;
     }
     private V getForNullKey() { 
         for (Entry<K, V> e = table[0]; e != null; e = e.next) { 
             if (e.key == null) return e.value;
         }
         return null;
    }
 

 确定数组index：hashcode % table.length取模
 HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，即计算数组下标；算法如下：

     /**  Returns index for hash code h.  */
     static int indexFor(int h, int length) { 
         return h & (length - 1);
    }

 按位取并，作用上相当于取模mod或者取余%。
 注意：不过的 hashCode进行运算后的值可能相等， 这意味着数组下标相同；但是，不要错误的理解为数组下标相同表示hashCode相同。
 
 初始大小 

 public HashMap(int initialCapacity, float loadFactor) { 
     .....
     // Find a power of 2 >= initialCapacity
     int capacity = 1;
     while (capacity < initialCapacity)
         capacity <<= 1;
     this.loadFactor = loadFactor;
     threshold = (int)(capacity * loadFactor);
     table = new Entry[capacity];
     init();
}

 注意初始大小并不是构造函数中的initialCapacity！而是 >= initialCapacity的2的n次幂！！！！！
 

 开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）
 再哈希法
 链地址法
 建立一个公共溢出区
 Java中 HashMap 的解决办法是采用的链地址法。

 当哈希表的容量超过默认容量时，必须调整table的大小。
 当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表映射到新表中。 

     /**
     * Rehashes the contents of this map into a new array with a
     * larger capacity.  This method is called automatically when the
     * number of keys in this map reaches its threshold.
     *
     * If current capacity is MAXIMUM_CAPACITY, this method does not
     * resize the map, but sets threshold to Integer.MAX_VALUE.
     * This has the effect of preventing future calls.
     *
     * @param newCapacity the new capacity, MUST be a power of two;
     *        must be greater than current capacity unless current
     *        capacity is MAXIMUM_CAPACITY (in which case value
     *        is irrelevant).
     */
     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);
             }
         }
    }