深入浅出理解HashMap1.8源码设计思想&手写HashMapV1.0
深入浅出理解HashMap1.8源码设计思想&手写HashMapV1.0
深入浅出学Java——HashMap
哈希表（hash table） 也叫散列表，是一种非常重要的数据结构，应用场景及其丰富，许多缓存技术（比如memcached）的核心其实就是在内存中维护一张大的哈希表，本文会对java集合框架中HashMap的实现原理进行讲解。
一、什么是哈希表
在讨论哈希表之前，我们先大概了解下其他数据结构在新增，查找等基础操作执行性能
数组：采用一段连续的存储单元来存储数据。对于指定下标的查找，时间复杂度为O(1)；通过给定值进行查找，需要遍历数组，逐一比对给定关键字和数组元素，时间复杂度为O(n)，当然，对于有序数组，则可采用二分查找，插值查找，斐波那契查找等方式，可将查找复杂度提高为O(logn)；对于一般的插入删除操作，涉及到数组元素的移动，其平均复杂度也为O(n)
线性链表：对于链表的新增，删除等操作（在找到指定操作位置后），仅需处理结点间的引用即可，时间复杂度为O(1)，而查找操作需要遍历链表逐一进行比对，复杂度为O(n)
二叉树：对一棵相对平衡的有序二叉树，对其进行插入，查找，删除等操作，平均复杂度均为O(logn)。
哈希表：相比上述几种数据结构，在哈希表中进行添加，删除，查找等操作，性能十分之高，不考虑哈希冲突的情况下（后面会探讨下哈希冲突的情况），仅需一次定位即可完成，时间复杂度为O(1)，接下来我们就来看看哈希表是如何实现达到惊艳的常数阶O(1)的。
我们知道，数据结构的物理存储结构只有两种：顺序存储结构和链式存储结构（像栈，队列，树，图等是从逻辑结构去抽象的，映射到内存中，也这两种物理组织形式），而在上面我们提到过，在数组中根据下标查找某个元素，一次定位就可以达到，哈希表利用了这种特性，哈希表的主干就是数组。
比如我们要新增或查找某个元素，我们通过把当前元素的关键字 通过某个函数映射到数组中的某个位置，通过数组下标一次定位就可完成操作。 这个函数可以简单描述为：存储位置 = f(关键字) ，这个函数f一般称为哈希函数，这个函数的设计好坏会直接影响到哈希表的优劣。举个例子，比如我们要在哈希表中执行插入操作：
插入过程如下图所示
查找操作同理，先通过哈希函数计算出实际存储地址，然后从数组中对应地址取出即可。
哈希冲突
然而万事无完美，如果两个不同的元素，通过哈希函数得出的实际存储地址相同怎么办？也就是说，当我们对某个元素进行哈希运算，得到一个存储地址，然后要进行插入的时候，发现已经被其他元素占用了，其实这就是所谓的哈希冲突，也叫哈希碰撞。前面我们提到过，哈希函数的设计至关重要，好的哈希函数会尽可能地保证 计算简单和散列地址分布均匀,但是，我们需要清楚的是，数组是一块连续的固定长度的内存空间，再好的哈希函数也不能保证得到的存储地址绝对不发生冲突。那么哈希冲突如何解决呢？哈希冲突的解决方案有多种:开放定址法（发生冲突，继续寻找下一块未被占用的存储地址），再散列函数法，链地址法，而HashMap即是采用了链地址法，也就是数组+链表的方式。
二、HashMap的实现原理
HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元，每一个Entry包含一个key-value键值对。（其实所谓Map其实就是保存了两个对象之间的映射关系的一种集合）
//HashMap的主干数组，可以看到就是一个Entry数组，初始值为空数组{}，主干数组的长度一定是2的次幂。 //至于为什么这么做，后面会有详细分析。 transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
Entry是HashMap中的一个静态内部类。代码如下
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;//存储指向下一个Entry的引用，单链表结构
int hash;//对key的hashcode值进行hash运算后得到的值，存储在Entry，避免重复计算
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
} 所以，HashMap的总体结构如下：
简单来说，HashMap由数组+链表组成的，数组是HashMap的主体，链表则是主要为了解决哈希冲突而存在的，如果定位到的数组位置不含链表（当前entry的next指向null）,那么查找，添加等操作很快，仅需一次寻址即可；如果定位到的数组包含链表，对于添加操作，其时间复杂度为O(n)，首先遍历链表，存在即覆盖，否则新增；对于查找操作来讲，仍需遍历链表，然后通过key对象的equals方法逐一比对查找。所以，性能考虑，HashMap中的链表出现越少，性能才会越好。
其他几个重要字段
/**实际存储的key-value键值对的个数*/
transient int size;
/**阈值，当table == {}时，该值为初始容量（初始容量默认为16）；当table被填充了，也就是为table分配内存空间后，
threshold一般为 capacity*loadFactory。HashMap在进行扩容时需要参考threshold，后面会详细谈到*/
int threshold;
/**负载因子，代表了table的填充度有多少，默认是0.75
加载因子存在的原因，还是因为减缓哈希冲突，如果初始桶为16，等到满16个元素才扩容，某些桶里可能就有不止一个元素了。
所以加载因子默认为0.75，也就是说大小为16的HashMap，到了第13个元素，就会扩容成32。
*/
final float loadFactor;
/**HashMap被改变的次数，由于HashMap非线程安全，在对HashMap进行迭代时，
如果期间其他线程的参与导致HashMap的结构发生变化了（比如put，remove等操作），
需要抛出异常ConcurrentModificationException*/
transient int modCount;HashMap有4个构造器，其他构造器如果用户没有传入initialCapacity 和loadFactor这两个参数，会使用默认值
initialCapacity默认为16，loadFactory默认为0.75
我们看下其中一个
public HashMap(int initialCapacity, float loadFactor) {
//此处对传入的初始容量进行校验，最大不能超过MAXIMUM_CAPACITY = 1<<30(230)
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
threshold = initialCapacity;
init();//init方法在HashMap中没有实际实现，不过在其子类如 linkedHashMap中就会有对应实现
}从上面这段代码我们可以看出，在常规构造器中，没有为数组table分配内存空间（有一个入参为指定Map的构造器例外），而是在执行put操作的时候才真正构建table数组
OK,接下来我们来看看put操作的实现
public V put(K key, V value) {
//如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
//此时threshold为initialCapacity 默认是1<<4(24=16)
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
//如果key为null，存储位置为table[0]或table[0]的冲突链上
if (key == null)
return putForNullKey(value);
int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
int i = indexFor(hash, table.length);//获取在table中的实际位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
//如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
addEntry(hash, key, value, i);//新增一个entry
return null;
}inflateTable这个方法用于为主干数组table在内存中分配存储空间，通过roundUpToPowerOf2(toSize)可以确保capacity为大于或等于toSize的最接近toSize的二次幂，比如toSize=13,则capacity=16;to_size=16,capacity=16;to_size=17,capacity=32.
private void inflateTable(int toSize) {
int capacity = roundUpToPowerOf2(toSize);//capacity一定是2的次幂
/**此处为threshold赋值，取capacity*loadFactor和MAXIMUM_CAPACITY+1的最小值，
capaticy一定不会超过MAXIMUM_CAPACITY，除非loadFactor大于1 */
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}roundUpToPowerOf2中的这段处理使得数组长度一定为2的次幂，Integer.highestOneBit是用来获取最左边的bit（其他bit位为0）所代表的数值.
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
return number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;
}hash函数
/**这是一个神奇的函数，用了很多的异或，移位等运算
对key的hashcode进一步进行计算以及二进制位的调整等来保证最终获取的存储位置尽量分布均匀*/
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}以上hash函数计算出的值，通过indexFor进一步处理来获取实际的存储位置
/**
* 返回数组下标
*/
static int indexFor(int h, int length) {
return h & (length-1);
}h&（length-1）保证获取的index一定在数组范围内，举个例子，默认容量16，length-1=15，h=18,转换成二进制计算为index=2。位运算对计算机来说，性能更高一些（HashMap中有大量位运算）
所以最终存储位置的确定流程是这样的：
再来看看addEntry的实现：
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}通过以上代码能够得知，当发生哈希冲突并且size大于阈值的时候，需要进行数组扩容，扩容时，需要新建一个长度为之前数组2倍的新的数组，然后将当前的Entry数组中的元素全部传输过去，扩容后的新数组长度为之前的2倍，所以扩容相对来说是个耗资源的操作。
三、为何HashMap的数组长度一定是2的次幂？
我们来继续看上面提到的resize方法
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, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}如果数组进行扩容，数组长度发生变化，而存储位置 index = h&(length-1),index也可能会发生变化，需要重新计算index，我们先来看看transfer这个方法
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//for循环中的代码，逐个遍历链表，重新计算索引位置，将老数组数据复制到新数组中去（数组不存储实际数据，所以仅仅是拷贝引用而已）
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
//将当前entry的next链指向新的索引位置,newTable[i]有可能为空，有可能也是个entry链，如果是entry链，直接在链表头部插入。
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}这个方法将老数组中的数据逐个链表地遍历，扔到新的扩容后的数组中，我们的数组索引位置的计算是通过 对key值的hashcode进行hash扰乱运算后，再通过和 length-1进行位运算得到最终数组索引位置。
HashMap的数组长度一定保持2的次幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。从下图可以我们也能看到这样会保证低位全为1，而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致(大大减少了之前已经散列良好的老数组的数据位置重新调换)，个人理解。
还有，数组长度保持2的次幂，length-1的低位都为1，会使得获得的数组索引index更加均匀
我们看到，上面的&运算，高位是不会对结果产生影响的（hash函数采用各种位运算可能也是为了使得低位更加散列），我们只关注低位bit，如果低位全部为1，那么对于h低位部分来说，任何一位的变化都会对结果产生影响，也就是说，要得到index=21这个存储位置，h的低位只有这一种组合。这也是数组长度设计为必须为2的次幂的原因。
如果不是2的次幂，也就是低位不是全为1此时，要使得index=21，h的低位部分不再具有唯一性了，哈希冲突的几率会变的更大，同时，index对应的这个bit位无论如何不会等于1了，而对应的那些数组位置也就被白白浪费了。
get方法：
public V get(Object key) {
//如果key为null,则直接去table[0]处去检索即可。
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}get方法通过key值返回对应value，如果key为null，直接去table[0]处检索。我们再看一下getEntry这个方法
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//通过key的hashcode值计算hash值
int hash = (key == null) ? 0 : hash(key);
//indexFor (hash&length-1) 获取最终数组索引，然后遍历链表，通过equals方法比对找出对应记录
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
} 可以看出，get方法的实现相对简单，key(hashcode)–>hash–>indexFor–>最终索引位置，找到对应位置table[i]，再查看是否有链表，遍历链表，通过key的equals方法比对查找对应的记录。要注意的是，有人觉得上面在定位到数组位置之后然后遍历链表的时候，e.hash == hash这个判断没必要，仅通过equals判断就可以。其实不然，试想一下，如果传入的key对象重写了equals方法却没有重写hashCode，而恰巧此对象定位到这个数组位置，如果仅仅用equals判断可能是相等的，但其hashCode和当前对象不一致，这种情况，根据Object的hashCode的约定，不能返回当前对象，而应该返回null，后面的例子会做出进一步解释。
四、重写equals方法需同时重写hashCode方法
最后我们再聊聊老生常谈的一个问题，各种资料上都会提到，“重写equals时也要同时覆盖hashcode”，我们举个小例子来看看，如果重写了equals而不重写hashcode会发生什么样的问题
public class MyTest {
private static class Person{
int idCard;
String name;
public Person(int idCard, String name) {
this.idCard = idCard;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o == null || getClass() != o.getClass()){
return false;
}
Person person = (Person) o;
//两个对象是否等值，通过idCard来确定
return this.idCard == person.idCard;
}
}
public static void main(String []args){
HashMap<Person,String> map = new HashMap<Person, String>();
Person person = new Person(1234,"乔峰");
//put到hashmap中去
map.put(person,"天龙八部");
//get取出，从逻辑上讲应该能输出“天龙八部”
System.out.println("结果:"+map.get(new Person(1234,"萧峰")));
}
}
实际输出结果：null如果我们已经对HashMap的原理有了一定了解，这个结果就不难理解了。尽管我们在进行get和put操作的时候，使用的key从逻辑上讲是等值的（通过equals比较是相等的），但由于没有重写hashCode方法，所以put操作时，key(hashcode1)–>hash–>indexFor–>最终索引位置 ，而通过key取出value的时候 key(hashcode1)–>hash–>indexFor–>最终索引位置，由于hashcode1不等于hashcode2，导致没有定位到一个数组位置而返回逻辑上错误的值null（也有可能碰巧定位到一个数组位置，但是也会判断其entry的hash值是否相等，上面get方法中有提到。）
所以，在重写equals的方法的时候，必须注意重写hashCode方法，同时还要保证通过equals判断相等的两个对象，调用hashCode方法要返回同样的整数值。而如果equals判断不相等的两个对象，其hashCode可以相同（只不过会发生哈希冲突，应尽量避免）。
五、JDK1.8中HashMap的性能优化
假如一个数组槽位上链上数据过多（即拉链过长的情况）导致性能下降该怎么办？ JDK1.8在JDK1.7的基础上针对增加了红黑树来进行优化。即当链表超过8时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。 关于这方面的探讨我们以后的文章再做说明。 附：HashMap put方法逻辑图（JDK1.8）
手写HashMap1.8 v1.0版本
定义统一接口
package day03;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Set;
/**
* @since 2019/11/28
**/
public interface IHashMap<K ,V> {
/**
* put()
*
* @param key
* @param value
* @return
*/
V put(K key, V value);
/**
* size()
*
* @return
*/
int size();
/**
* entrySet()
*
* @return
*/
Set<IHashMap.Entry<K, V>> entrySet();
/**
* get()
* @param key
* @return
*/
V get(Object key);
/**
* Entry
* @param <K>
* @param <V>
*/
interface Entry<K, V> {
K getKey();
V getValue();
V setValue(V value);
}
}实现类
package day03;
import java.util.Set;
/**
* <p>
* IHashMap接口实现类
* </p>
* @since 2019/11/28
**/
public class IHashMapImpl<K,V> implements IHashMap<K,V> {
/**
* The load factor for the hash table.
* 哈希表的加载因子
* @serial
*/
final float loadFactor;
/**
* The load factor used when none specified in constructor.
* 构造函数中未指定时的加载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 存储元素的数组
* 第一次使用时初始化的表，大小调整为必要的。分配时，长度总是2的幂
*/
transient Node<K,V>[] table;
/**
* 转红黑树的阈值
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 此哈希映射在结构上被修改的次数
* 此字段用于对的集合视图生成迭代器
* 哈希映射失败得很快
*/
transient int modCount;
/**
* 键值映射数（存储元素的个数）
*/
transient int size;
/**
*临界值，当实际大小（容量*加载因子）超过临界值时，会进行扩容
*/
int threshold;
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认初始化大小为16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 构造函数1
* @param initialCapacity：自定义初始化容量大小
* @param loadFactor：自定义哈希表加载因子大小
*/
public IHashMapImpl(int initialCapacity, float loadFactor) {
//限制指定的初始容量为非负
if (initialCapacity < 0) {
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
}
//如果指定的初始容量大于最大容量，那么就设置为最大容量
if (initialCapacity > MAXIMUM_CAPACITY) {
initialCapacity = MAXIMUM_CAPACITY;
}
//限制哈希表的加载因子为正
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
}
//给加载因子赋值（自定义加载因子大小）
this.loadFactor = loadFactor;
//新的扩容临界值
this.threshold = tableSizeFor(initialCapacity);
}
/**
* Returns a power of two size for the given target capacity.
* 使得给定容量为（2^n）
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
* 构造函数2
* @param initialCapacity：自定义哈希表的加载因子大小
*/
public IHashMapImpl(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 构造函数3（默认属性值）
*/
public IHashMapImpl() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**
* 构造函数4：用m的元素初始化散列映射
* @param m
*/
public IHashMapImpl(IHashMap<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 把IHashMap作为参数传入
* @param m
* @param evict
*/
final void putMapEntries(IHashMap<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) {
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY);
if (t > threshold) {
threshold = tableSizeFor(t);
}
}
else if (s > threshold) {
resize();
}
for (IHashMap.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
/**
* put()逻辑处理：
* 下面简单说下添加键值对put(key,value)的过程：
* 1，判断键值对数组tab[]是否为空或为null，否则以默认大小resize()；
* 2，根据键值key计算hash值得到插入的数组索引i，如果tab[i]==null，直接新建节点添加，否则转入3
* 3，判断当前数组中处理hash冲突的方式为链表还是红黑树(check第一个节点类型即可),分别处理
* @param key
* @param value
* @return
*/
@Override
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
@Override
public int size() {
return 0;
}
@Override
public Set<Entry<K, V>> entrySet() {
return null;
}
/**
* get()处理逻辑:
* get(key)方法时获取key的hash值，计算hash&(n-1)得到在链表数组中的位置
* first=tab[hash&(n-1)],先判断first的key是否与参数key相等，
* 不等就遍历后面的链表找到相同的key值返回对应的Value值即可
* @param key
* @return
*/
@Override
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* getNode()具体实现
* @param hash
* @param key
* @return
*/
final Node<K,V> getNode(int hash, Object key) {
//Entry数组对象
Node<K,V>[] tab;
//在tab数组中经过散列的第一个位置
Node<K,V> first;
Node<K,V> e;
int n; K k;
//找到插入的第一个Node，方法是hash值和n-1相与，也就是说在一条链上的hash值相同
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//检查第一个node是不是要找到的node，判断条件是hash值要相同，key值要相同
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) {
return first;
}
//检查first后面的node
if ((e = first.next) != null) {
if (1==2) {
//TODO:红黑树处理逻辑
}
//遍历后面的链表，找到key值和hash值都相同的key
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
return e;
}
} while ((e = e.next) != null);
}
}
return null;
}
/**
* 计算hash
* @param key
* @return
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
/**
* put()方法具体业务逻辑实现
* @param hash
* @param key
* @param value
* @param onlyIfAbsent
* @param evict
* @return
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
//1.如果tab为空或者tab的长度为0
if ((tab = table) == null || (n = tab.length) == 0) {
n = (tab = resize()).length;
}
//2.如果table在计算出的index下标对应的tab数组Node节点未初始化，就新创建一个Node节点插入到该位置
if ((p = tab[i = (n - 1) & hash]) == null) {
tab[i] = newNode(hash, key, value, null);
}
//3.这个分支说明计算出index值在tab数组中找到已经初始化的Node节点，就开始处理index冲突
else {
Node<K,V> e = null;
K k;
//检查第一个Node，p是不是要找的值
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) {
//如果是，则把Node e 指向Node p
e = p;
//如果不是则判断Node p 是否是红黑树类型
} else if (1==2) {
//TODO 条件判断转红黑树的操作
} else {
//如果前面两种情况都不满足，则循环单链表
for (int binCount = 0; ; ++binCount) {
//如果Node p 的下一个节点为空就挂在后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果链表长度大于等于8，看是否需要转为红黑树进行处理
if (binCount >= TREEIFY_THRESHOLD - 1) {
//treeifyBin首先判断当前hashMap的长度，如果不足64，只进行
//resize，扩容table，如果达到64，那么将冲突的存储结构为红黑树
treeifyBin(tab, hash);
}
//终止循环条件
break;
}
//如果Node p 的下一个节点不为空，检查下一个Node节点是否是我们要找的值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
//如果找到了相同的key就结束遍历
break;
}
//将Node p节点指向Node e
p = e;
}
}
//走到这个分支，说明链表上有相同的key值
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) {
e.value = value;
}
afterNodeAccess(e);
//返回存在的value值
return oldValue;
}
}
//安全，便与并发下的快速失败
++modCount;
//如果当前node节点个数大于临界值（初始容量*0.75）
if (++size > threshold) {
//扩容两倍
resize();
}
afterNodeInsertion(evict);
return null;
}
private void afterNodeInsertion(boolean evict) {
}
private void treeifyBin(Node<K,V>[] tab, int hash) {
}
private void afterNodeAccess(Node<K,V> e) {
}
private Node<K,V> newNode(int hash, K key, V value, Node next) {
return new Node(hash, key, value, next);
}
/**
* 扩容机制
* @return
*/
private Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//扩容临界值
int oldThr = threshold;
int newCap;
int newThr = 0;
//1.如果旧表的长度大于0
if (oldCap > 0) {
//如果扩容临界值大于等于最大容量，直接赋值为最大容量
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//把新表的长度扩容为旧表长度的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) {
newThr = oldThr << 1;
}
}
//2.如果旧表的长度为0，则说明是第一次初始化表
else if (oldThr > 0) {
newCap = oldThr;
} else {
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//新表长度乘以加载因子
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
/**下面开始构造新表，初始化表中数据**/
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//把新表赋值给table
table = newTab;
//原表不为空，把原表中的数据移到新表中
if (oldTab != null) {
/**遍历原来的旧表**/
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) {
newTab[e.hash & (newCap - 1)] = e;
} else if (1==2) {
//TODO:红黑树处理业务逻辑代码
//如果e后边有链表，到这里表示e后面带着单个链表，需要遍历链表
} else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//重新计算在新表中的位置，并进行搬运
do {
//记录下一个节点
next = e.next;
//新表是旧表的两倍容量，实例上就把单链表拆分为两队，
//e.hash&oldCap为偶数一队，e.hash&oldCap为奇数一对
if ((e.hash & oldCap) == 0) {
if (loTail == null) {
loHead = e;
} else {
loTail.next = e;
}
loTail = e;
}
else {
//lo队不为null，放在新表原位置
if (hiTail == null) {
hiHead = e;
//hi队不为null，放在新表j+oldCap位置
} else {
hiTail.next = e;
}
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
static class Node<K,V> implements IHashMap.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;
}
@Override
public final K getKey() { return key; }
@Override
public final V getValue() { return value; }
@Override
public final String toString() { return key + "=" + value; }
@Override
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
}
}未完待续....