虽然网上已有很多人写关于HashMap源码分析的文章，但看完过一段时间后，又有点模糊了，觉得只有自己真正再将其履一遍，并真正把它能讲清楚，自己才算真正掌握了。在读本文之前如果你对以下几个问题都了如指掌，此文可略过。
1. HashMap的数据结构是什么？hash冲突是指什么？
2. HashMap是怎么解决hash冲突的，链表法是如何实现的？
3. 为什么HashMap的容量必须是2的指数幂？
4. LinkedHashMap的实现与HashMap有哪些不同？LinkedHashMap是怎么实现元素有序的？
5. 为什么重写equals方法必须重写hashcode方法?
6. HashMap的put方法实现过程？
1. 数据结构
hashmap实际上是一个数组+链表的数据结构，hashmap底层是一个数组结构，数组中每一项又是一个链表结构。链表是为了解决hash冲突。
/**
* 空表
*/
static final HashMapEntry<?,?>[] EMPTY_TABLE = {};
/**
* 内部是一个数组，数组的每一项是一个链表，数组的长度必须是2的指数幂，当需要时进行扩容
*/
transient HashMapEntry<K,V>[] table = (HashMapEntry<K,V>[]) EMPTY_TABLE;
/**
* 数组的每一项是一个链表结构，通过next属性指向下一项，链表的每一项的是一个map结构数据，包含key、value
*/
static class HashMapEntry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
HashMapEntry<K,V> next;
int hash;
}2. hashmap的初始化
hashmap的构造函数中会对hashmap容量进行初始化，默认初始容量是16,装载因为为0.75,即当容量达到12时，会对hashmap进行扩容，增大一部，变成32.我们也可以调用其构造函数，自己设定其容量大小。
//initialCapacity初始容量，默认16、loadFactor装载因子，默认0.75
public HashMap(int initialCapacity, float loadFactor) {
}3. hasmap存取实现
3.1 put操作
put操作实现的方式是：根据key计算出hash值，查找在数组中对应的位置，判断该数组中对应位置是否有值，有值再判断是否有相同的key值，有则将新值替换旧值，并将旧值返回，存储结束。该数组在对应位置中没有值，或是有值但没有相同的key值，则新建一个Entry元素，并将其放到对应的数组位置处。
先看下源代码：
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
//判断键是否为空，为空放到数组头部table[0]位置
return putForNullKey(value);
//步骤1:通过hash算法计算出key的hash值
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//步骤2:根据hash值找到其对应在hashmap数组中位置
int i = indexFor(hash, table.length);
//步骤3:查找hashmap的数组判断该位置是否有值，没有直接略过for循环，有则进入for循环中查找该位置对应的链表中元素的key值是否和当前要存储的元素的key值相同
for (HashMapEntry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//如果hash值相同且key值相同，会用新元素替换旧元素，并将旧元素返回
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
//步骤4:如果当前元素的hash值对应数组位置中链表不存在或是链表存在，但是链表中所有元素值的key与当前要存储的元素key值不一样的话，新建一个Entry保存到hashmap中
addEntry(hash, key, value, i);
return null;
}上述四个步骤并没有体现出hash冲突的处理方法，hash冲突是指key值不一样，但是计算出的hash值是一样的。我们接着看addEntry方法：
void addEntry(int hash, K key, V value, int bucketIndex) {
//步骤1：检查当前hashmap中有值的数组是否达到极限值（默认初始容量16*0.75），若超过，会进行数组扩容。重新计算出当前要存入元素hash值对应在新数组中的位置
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
//步骤2:新建一个Entry对象存入hashmap中
createEntry(hash, key, value, bucketIndex);
}我们再进入createEntry函数查看hashmap是怎么将新元素存入数组中的。
void createEntry(int hash, K key, V value, int bucketIndex) {
//步骤1:取出当前数组中的元素，是一个Entry链表结构数据
HashMapEntry<K,V> e = table[bucketIndex];
//步骤2:将当前元素加入到Entry中，将原值e和新值的key,value,hash传进去
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}在这里还没有体现出hashmap处理冲突的方式，我们接着看新建一个Entry元素方法。
HashMapEntry(int h, K k, V v, HashMapEntry<K,V> n) {
value = v;//新值value
next = n;//关键点，将旧值赋给新值的next，这样就相当于把新值放在链表头部，新元素的next指向原数组链表中的值
key = k;
hash = h;
}终于找到了hashmap处理冲突的代码，当发生hash冲突时，会将新元素放在链表头部，并将next指向原链表中元素。打个比方， 第一个键值对A进来，通过计算其key的hash得到的index=2，记做:Entry[2] = A。一会后又进来一个键值对B，通过计算其index也等于2，HashMap会将B.next = A,Entry[2] = B,如果又进来C,index也等于2,那么C.next = B,Entry[2] = C；这样我们发现index=2的地方其实存取了A,B,C三个键值对,他们通过next这个属性链接在一起。
3.2 根据hash值查找在数组中位置
static int indexFor(int h, int length) {
return h & (length-1);
}按位取并，作用上相当于取模mod或者取余%操作，但是利用二进制操作更快。这里就体现了为什么数组长度必须是2的指数幂，只有2的指数幂，比如16的二进制表示为 10000，那么length-1就是15，二进制为01111，同理扩容后的数组长度为32，二进制表示为100000，length-1为31，二进制表示为011111。而扩容后只有一位差异，也就是多出了最左位的1，这样在通过 h&(length-1)的时候，只要h对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致,大大减少了之前已经散列良好的老数组的数据位置重新调换.
3.3 存放key为空值实现
key值为空的所有元素都放到数组的头部table[0]位置处，这里会判断数组头部table[0]位置处是否有值，有值，再判断是否有相同的key值，有则替换，没有则新建一个Entry，步骤跟上面类似
private V putForNullKey(V value) {
for (HashMapEntry<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;
}4 get方法
get操作的源代码如下：
public V get(Object key) {
//如果key值为null，则从数组头部中查找
if (key == null)
return getForNullKey();
//根据元素的key值查找出对应的Entry
Entry<K,V> entry = getEntry(key);
//返回Entry对应的value值
return null == entry ? null : entry.getValue();
}我们再看看getEntry()方法的实现
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
//步骤一：计算出key对应的hash值
int hash = (key == null) ? 0 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
//步骤二：查找hash值对应在数组中是否存在值，存在则判断对应Entry的key是否和要查找元素的key值相同，相同则返回对应的Entry
for (HashMapEntry<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;
}5. hashmap遍历方法
1)采用Iterator遍历
Iterator iter = map.entrySet().iterator();
while (iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
Object key = entry.getKey();
Object val = entry.getValue();
}2)for each遍历
for (Entry<String, String> entry : map.entrySet()) {
Object key = entry.getKey();
Object val = entry.getValue();
}6. LinkedHashMap原理
LinkedHashMap是HashMap的子类，实现结构和HashMap类似，只是HashMap中的链表是单向链表，而LinkedHashMap是双向链表，只是在在HashMap的基础上加上了排序实现。
6.1 构造函数
LinkedHashMap的构造函数较HashMap多了一个排序参数accessOrder。
/**
* @param initialCapacity 初始容量，16
* @param loadFactor 装载因子0.75
* @param accessOrder 排序方式标识，为true代表数组元素按照访问顺序排序，为false代表按照插入顺序排序，默认按插入顺序排序
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}6.2 排序方式实现
在LinkedHashMapEntry中重写了recordAccess方法，在HashMap的HashMapEntry是个空方法。该方法判断是否按访问顺序进行排序，如果是调用addBefore()将当前被访问的元素移至链表头部。如果不是按访问顺序排序，则链表中元素没有变化。因为插入元素时，新插入的元素在HashMap中实现就是放到链表头部的。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
if (lm.accessOrder) {
lm.modCount++;
remove();
addBefore(lm.header);
}
}
/**
* 将当前元素移至链表头部
*/
private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
after = existingEntry;
before = existingEntry.before;
before.after = this;
after.before = this;
}6.3 put实现
LinkedHashMap没有对put方式进行重写，但对addEntry()、createEntry()和LinkedHashMapEntry中的recordAccess()方法进行了重写。因为在HashMap中put一个元素时，如果要存储的元素的hash值和key值在当前链表中存在的话，在替换旧值后，就调用了recordAccess()方法。而在createEntry()方法中,LinkedHashMap的实现如下，添加了addBefore()方法调用。将当前新插入的元素放至链表头部。
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> old = table[bucketIndex];
LinkedHashMapEntry<K,V> e = new LinkedHashMapEntry<>(hash, key, value, old);
table[bucketIndex] = e;
e.addBefore(header);//关键点，将当前元素放到链表头部，从而实现最近访问的元素都在链表头部
size++;
}6.3 get实现
LinkedHashMap中，在进行获取元素时，也调用了recordAccess方法，将访问元素移至链表头部
public V get(Object key) {
LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
if (e == null)
return null;
e.recordAccess(this);//关键点，如果是按访问顺序排序，会将当前访问的元素移至链表头部
return e.value;
}7. LruCache中调用LinkedHashMap的实现
final LinkedHashMap<T, Y> cache = new LinkedHashMap<T, Y>(100, 0.75f, true);通过设置accessOrder参数为true，就实现了按访问顺序排序。
8､为什么object类的equals()重写同时也要重写 hashcode ()?
Object对象的equals(Object)方法，对于任何非空引用值x和y，当且仅当x和y引用同一个对象时，此方法才返回true。
当equals()方法被重写时，通常必须重写hashcode()方法，hash协定声明相等对象必须具有相等的hashcode，如下：
1）当obj1.equals(obj2)为true时，obj1.hashCode()==obj2.hashCode()必须为true
2)当obj1.hashCode()==obj2.hashCode()为false时，obj1.equals(obj2)必须为false，若obj1.hashCode()==obj2.hashCode()为true时，obj1.equals(obj2)不一定为true.
若不重写equals，比较的将是对象的引用是否指向同一块内存地址，重写后目的是为了比较两个对象的value值是否相等。
Hashcode是用于散列数据快速存取，如利用HashSet\HashMap\Hashtable类来存储数据时，都是先进行hashcode值判断是否相同，不相同则没必要再进行equals比较。
如果重写了equeals()但没重写hashcode()，再new一个对象时，当原对象.equals(新对象)等于true时，两者的hashcode却不是一样的，由此会得出两个对象不相等的性况。在存储时，也会发生两个值一样的对象，hashcode不一样而存储两个，导致混淆。所以Object的equals()方法重写同时也要重写hashcode()方法。
经过自己撸一遍源码，自己再把它写下来，对HashMap实现的理解又加深了一点映象。