Java-读懂HashMap源码

前提知识：

首先要知道哈希表， 哈希表（Hash table，也叫散列表）
哈希表的思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！

正文：

Lrucache用到了LinkedHashMap

前面都是线性结构，用到Object[] 或者链表这样的线性结构

HashMap里面存的是键值对 key value ，包含两个数据项，合起来叫entry（一种叫法）。
默认传入4,0.75

public HashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
    }

当key的值是null的时候一定传到table[0]索引下的链表里面。

散列链表
HashMap继承自AbstractMap，AbstractMap实现了Map接口
AbstractMap中，

    transient Set<K>        keySet;
    transient Collection<V> values;

可以看到键不能相同，值可以相同，set里面的值不能重复

在HashMap中：

 /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

初始的容量必须是2的整数倍2的4次方即16,其实不同版本的jdk初始容量有不同下面的是Android API14中看到的

/**
     * Min capacity (other than zero) for a HashMap. Must be a power of two
     * greater than 1 (and less than 1 << 30).
     */
    private static final int MINIMUM_CAPACITY = 4;

也就是说初始容量是4.

/**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

由上可见，当HashMap容量达到75%的时候就准备开始扩容

HashMap核心

  /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
    transient Node<K,V>[] table;

再来看Node（就是HashMapEntry，不同版本的jdk），Node是定义在HashMap中的内部类

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

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

HashMap键值对是存放在这个table键值对数组里面的。
Node中的方法是对Map.Entry的方法实现。

put方法

  /**
     * Maps the specified key to the specified value.
     *
     * @param key
     *            the key.
     * @param value
     *            the value.
     * @return the value of any previous mapping with the specified key or
     *         {@code null} if there was no such mapping.
     */
    @Override public V put(K key, V value) {
        if (key == null) {
            return putValueForNullKey(value);
        }

        int hash = secondaryHash(key.hashCode());
        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;
    }

 static class HashMapEntry<K, V> implements Entry<K, V> {
        final K key;
        V value;
        final int hash;
        HashMapEntry<K, V> next;

        HashMapEntry(K key, V value, int hash, HashMapEntry<K, V> next) {
            this.key = key;
            this.value = value;
            this.hash = hash;
            this.next = next;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return value;
        }

        public final V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

int index = hash & (tab.length - 1);与运算的结果一定在0-tab.length之间，比如：
（散列方法是为了让数据分散开，不要全在某一个索引下面，这样才平均，查找起来才高效）

假如key1，key2产生的Hash值相同怎么办会不会key1的值被覆盖？

不会，因为HashMap为散列存储。看下面代码，HashMapEntry是链式存储的，next指针可以将相同key的值的元素连接起来，而不会覆盖（可见HashMap不仅仅是个单纯的一位数组）。也即先去找相应的索引，然后再根据这个索引去找该索引下的链表

上面代码的关键代码在这里：

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

for循环里，是在定位到某个索引后，循环该索引下面的链表（e = tab[index]一位数组的键值对，是对应链表的头结点，就是指向该索引的一个头结点，后面循环（e=e.next）里面就是对链表的遍历）。

if (e.hash == hash && key.equals(e.key))这个判断是为了判断如果两个键相同的情况。key是传进来的key。e.key是链表中节点的key。因为HashMap里面不允许有两个key相同值不同的存在，那就需要把旧的值覆盖掉。

preModify(e);方法在HashMap里面没有写方法体，留给子类去实现具体逻辑。LinkedHashMap里面就写了这个方法体。

如果两个hash值相同，那么key是否相同？

不一定的，否则就不存在散列表了，因为散列表就是利用了不同的key算出来的hash值相同来操作的。

那么key相同，两个hash值是否相同？

一定相同（前面key的值会被后面相同的key对应的值覆盖）

HashMap套路深啊，这样找起来方便快速！

---

其他：

1<<30的意思是2^30次方（左移是乘2，右边移是除2）
int类型的最大值：在Integer源码里看MAX_VALUE的值（2^31-1）一个int类型占4个字节，一个字节32位