前提知识
首先要知道哈希表， 哈希表（Hash table，也叫散列表）
哈希表的思路：当我知道key值以后，我就可以直接计算出这个元素在集合中的位置，根本不需要一次又一次的查找！
正文
（Lrucache用到了LinkedHashMap）
像数组，栈，链表，队这种，都是线性结构，比如用到诸如Object[] 或者链表这样的线性结构。
HashMap里面存的是键值对 key value ，包含两个数据项，合起来叫entry（一种叫法）。
DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR默认传入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方法
JDK1.8 之前 HashMap 由 数组+链表 组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）.JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树，以减少搜索时间
JDK 1.8之前
https://www.androidos.net.cn/android/4.0.2_r1/xref/libcore/luni/src/main/java/java/util/HashMap.java
/** * 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; }
void addNewEntry(K key, V value, int hash, int index) { table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);//创建一个新的node在index所在的table中 }
1.8之后
HashMap扩容
那么hashmap什么时候进行扩容呢？当hashmap中的元素个数超过数组大小*loadFactor时，就会进行数组扩容，loadFactor的默认值为0.75，也就是说，默认情况下，数组大小为16，那么当hashmap中元素个数超过16*0.75=12的时候，就把数组的大小扩展为2*16=32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知hashmap中元素的个数，那么预设元素的个数能够有效的提高hashmap的性能。
关于与操作
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位