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);
            }
        }

    }