來源：Java集合，HashMap底層實現(xiàn)和原理（1.7數(shù)組+鏈表與1.8+的數(shù)組+鏈表+紅黑樹）
概述
文章的內(nèi)容基于JDK1.7進行分析诀艰，之所以選用這個版本柬甥，是因為1.8的有些類做了改動，增加了閱讀的難度其垄，雖然是1.7苛蒲，但是對于1.8做了重大改動的內(nèi)容，文章也會進行說明绿满。
HashMap基于Map接口實現(xiàn)臂外，元素以鍵值對的方式存儲，并且允許使用null 建和null 值棒口， 因為key不允許重復寄月，因此只能有一個鍵為null,另外HashMap不能保證放入元素的順序，它是無序的无牵，和放入的順序并不能相同。HashMap是線程不安全的厂抖。
數(shù)據(jù)結(jié)構(gòu)
繼承關(guān)系
public class HashMap<K,V>extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
實現(xiàn)接口
Serializable, Cloneable, Map<K,V>
基本屬性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默認初始化大小 16
static final float DEFAULT_LOAD_FACTOR = 0.75f; //負載因子0.75
static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默認數(shù)組
transient int size; //HashMap中元素的數(shù)量
int threshold; //判斷是否需要調(diào)整HashMap的容量
代碼有移位運算茎毁，不理解請點擊 Java二進制位運算、移位運算>>、<<七蜘、>>> 了解谭溉。
源碼解析
image
什么是鏈表
鏈表是由一系列非連續(xù)的節(jié)點組成的存儲結(jié)構(gòu)，簡單分下類的話橡卤，鏈表又分為單向鏈表和雙向鏈表扮念，而單向/雙向鏈表又可以分為循環(huán)鏈表和非循環(huán)鏈表，下面簡單就這四種鏈表進行圖解說明碧库。
1.單向鏈表
單向鏈表就是通過每個結(jié)點的指針指向下一個結(jié)點從而鏈接起來的結(jié)構(gòu)柜与，最后一個節(jié)點的next指向null。
image2.單向循環(huán)鏈表
單向循環(huán)鏈表和單向列表的不同是嵌灰，最后一個節(jié)點的next不是指向null弄匕，而是指向head節(jié)點，形成一個“環(huán)”沽瞭。
image3.雙向鏈表
從名字就可以看出迁匠，雙向鏈表是包含兩個指針的，pre指向前一個節(jié)點驹溃，next指向后一個節(jié)點城丧，但是第一個節(jié)點head的pre指向null，最后一個節(jié)點的tail指向null豌鹤。
image4.雙向循環(huán)鏈表
雙向循環(huán)鏈表和雙向鏈表的不同在于亡哄，第一個節(jié)點的pre指向最后一個節(jié)點，最后一個節(jié)點的next指向第一個節(jié)點傍药，也形成一個“環(huán)”磺平。而LinkedList就是基于雙向循環(huán)鏈表設(shè)計的。
image
在進行源碼解析之前拐辽，先從總體上對HashMap的數(shù)據(jù)存儲結(jié)構(gòu)進行一個大體上的說明拣挪。
存儲結(jié)構(gòu)如上圖所示。
HashMap采用Entry數(shù)組來存儲key-value對俱诸，每一個鍵值對組成了一個Entry實體菠劝，Entry類實際上是一個單向的鏈表結(jié)構(gòu)，它具有Next指針睁搭，可以連接下一個Entry實體赶诊，依次來解決Hash沖突的問題，因為HashMap是按照Key的hash值來計算Entry在HashMap中存儲的位置的园骆，如果hash值相同舔痪，而key內(nèi)容不相等，那么就用鏈表來解決這種hash沖突锌唾。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
//默認初始化的容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//負載因子锄码，當容量達到75%時就進行擴容操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//當數(shù)組還沒有進行擴容操作的時候夺英，共享的一個空表對象
static final Entry<?,?>[] EMPTY_TABLE = {};
//table,進行擴容操作，長度必須2的n次方
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//Map中包含的元素數(shù)量
transient int size;
//閾值滋捶，用于判斷是否需要擴容（threshold = 容量*負載因子）
int threshold;
//加載因子實際的大小
final float loadFactor;
//HashMap改變的次數(shù)
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//內(nèi)部類痛悯，通過vm來修改threshold的值
private static class Holder {
/**
* Table capacity above which to switch to use alternative hashing.
*/
static final int ALTERNATIVE_HASHING_THRESHOLD;
static {
String altThreshold = java.security.AccessController.doPrivileged(
new sun.security.action.GetPropertyAction(
"jdk.map.althashing.threshold")); //讀取值
int threshold;
try {
threshold = (null != altThreshold) //修改值
? Integer.parseInt(altThreshold)
: ALTERNATIVE_HASHING_THRESHOLD_DEFAULT;
// disable alternative hashing if -1
if (threshold == -1) {
threshold = Integer.MAX_VALUE; //設(shè)置為Integer能表示的最大值
}
if (threshold < 0) {
throw new IllegalArgumentException("value must be positive integer.");
}
} catch(IllegalArgumentException failed) {
throw new Error("Illegal value for 'jdk.map.althashing.threshold'", failed);
}
ALTERNATIVE_HASHING_THRESHOLD = threshold; //返回
}
}
//HashCode的初始值為 0
transient int hashSeed = 0;
//構(gòu)造方法，指定初始容量和負載因子
public HashMap(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; //設(shè)置負載因子
threshold = initialCapacity; //初始容量
init(); //不做任何操作
}
//構(gòu)造方法重窟，指定了初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//無參構(gòu)造方法载萌，使用默認的容量大小和負載因子，并調(diào)用其他的構(gòu)造方法
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//構(gòu)造函數(shù)巡扇，參數(shù)為指定的Map集合
public HashMap(Map<? extends K, ? extends V> m) {
this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
inflateTable(threshold);
putAllForCreate(m);
}
//選擇合適的容量值扭仁，最好是number的2的冪數(shù)
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;
}
//擴充表，HashMap初始化時是一個空數(shù)組霎迫，此方法執(zhí)行重新復制操作斋枢，創(chuàng)建一個新的Entry[]
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize); //capacity為2的冪數(shù)，大于等于toSize
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity]; //新建數(shù)組知给，并重新賦值
initHashSeedAsNeeded(capacity); //修改hashSeed
}
// internal utilities
//初始化
void init() {
}
//與虛擬機設(shè)置有關(guān)瓤帚，改變hashSeed的值
final boolean initHashSeedAsNeeded(int capacity) {
boolean currentAltHashing = hashSeed != 0;
boolean useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean switching = currentAltHashing ^ useAltHashing;
if (switching) {
hashSeed = useAltHashing
? sun.misc.Hashing.randomHashSeed(this)
: 0;
}
return switching;
}
//計算k 的 hash值
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
//根據(jù)hashcode,和表的長度，返回存放的索引
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";
return h & (length-1);
}
//返回Map中鍵值對的數(shù)量
public int size() {
return size;
}
//判斷集合是否為空
public boolean isEmpty() {
return size == 0;
}
//返回key 涩赢，對應的值
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
//返回null鍵的值
private V getForNullKey() {
if (size == 0) {
return null;
}
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
//是否包含鍵為key的元素
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
//返回鍵為key 的entry實體戈次，不存在返回null
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key); //計算key的 hash值
//定位到Entry[] 數(shù)組中的存儲位置，開始遍歷該位置是否有鏈表存在
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//判斷是否有鍵位key 的entry實體筒扒。有就返回怯邪。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
//向map中添加key-value 鍵值對，如果可以包含了key的映射花墩，則舊的value將被替換
public V put(K key, V value) {
if (table == EMPTY_TABLE) { //table如果為空悬秉，進行初始化操作
inflateTable(threshold);
}
if (key == null) //key 為null ,放入數(shù)組的0號索引位置
return putForNullKey(value);
int hash = hash(key); //計算key的hash值
int i = indexFor(hash, table.length); //計算key在entry數(shù)組中存儲的位置
//判斷該位置是否已經(jīng)有元素存在
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
//判斷key是否已經(jīng)在map中存在，若存在用新的value替換掉舊的value,并返回舊的value
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this); //空方法
return oldValue;
}
}
modCount++; //修改次數(shù)加1
addEntry(hash, key, value, i); //將key-value轉(zhuǎn)化為Entry實體冰蘑，添加到Map中
return null;
}
//key = null, 對應的操作和泌，keyweinull ,存放在entry[]中的0號位置。并用新值替換舊值
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 void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key); //計算hash值
int i = indexFor(hash, table.length); //計算在HashMap中的存儲位置
//遍歷i號存儲位置的鏈表
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
e.value = value;
return;
}
}
//創(chuàng)建Entry實體武氓，存放到i號位置中
createEntry(hash, key, value, i);
}
//將m中的元素添加到HashMap中
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
//擴容操作
void resize(int newCapacity) {
Entry[] oldTable = table; //將table賦值給新的引用
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//創(chuàng)建一個長度為newCapacity的數(shù)組
Entry[] newTable = new Entry[newCapacity];
//將table中的元素復制到newTable中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//更改閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//將table中的數(shù)據(jù)復制到newTable中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) { //是否需要重新計算Hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); //計算存儲的位置
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
//將m中的元素全部添加到HashMap中
public void putAll(Map<? extends K, ? extends V> m) {
int numKeysToBeAdded = m.size();
if (numKeysToBeAdded == 0) //為空返回
return;
if (table == EMPTY_TABLE) { //是否需要執(zhí)行初始化操作
inflateTable((int) Math.max(numKeysToBeAdded * loadFactor, threshold));
}
//判斷是否需要擴容
if (numKeysToBeAdded > threshold) {
int targetCapacity = (int)(numKeysToBeAdded / loadFactor + 1);
if (targetCapacity > MAXIMUM_CAPACITY)
targetCapacity = MAXIMUM_CAPACITY;
int newCapacity = table.length;
while (newCapacity < targetCapacity)
newCapacity <<= 1;
if (newCapacity > table.length)
resize(newCapacity);
}
//執(zhí)行添加操作
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
//刪除key ,并返回key對應的value值
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
//返回key對應的實體
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key); //計算key的hash值
int i = indexFor(hash, table.length); //計算存儲位置
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next; //鏈表刪除
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
//刪除一個指定的實體
final Entry<K,V> removeMapping(Object o) {
if (size == 0 || !(o instanceof Map.Entry))
return null;
Map.Entry<K,V> entry = (Map.Entry<K,V>) o;
Object key = entry.getKey();
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
if (e.hash == hash && e.equals(entry)) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
//刪除map
public void clear() {
modCount++;
Arrays.fill(table, null);
size = 0;
}
//判斷是否包含指定value的實體
public boolean containsValue(Object value) {
if (value == null)
return containsNullValue();
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (value.equals(e.value))
return true;
return false;
}
//是否包含value== null
private boolean containsNullValue() {
Entry[] tab = table;
for (int i = 0; i < tab.length ; i++)
for (Entry e = tab[i] ; e != null ; e = e.next)
if (e.value == null)
return true;
return false;
}
//重寫克隆方法
public Object clone() {
HashMap<K,V> result = null;
try {
result = (HashMap<K,V>)super.clone();
} catch (CloneNotSupportedException e) {
// assert false;
}
if (result.table != EMPTY_TABLE) {
result.inflateTable(Math.min(
(int) Math.min(
size * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY),
table.length));
}
result.entrySet = null;
result.modCount = 0;
result.size = 0;
result.init();
result.putAllForCreate(this);
return result;
}
//靜態(tài)內(nèi)部類 ，Entry用來存儲鍵值對仇箱，HashMap中的Entry[]用來存儲entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //鍵
V value; //值
Entry<K,V> next; //采用鏈表存儲HashCode相同的鍵值對县恕，next指向下一個entry
int hash; //entry的hash值
//構(gòu)造方法， 負責初始化entry
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry e = (Map.Entry)o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
//當使用相同的key的value被覆蓋時調(diào)用
void recordAccess(HashMap<K,V> m) {
}
//每移除一個entry就被調(diào)用一次
void recordRemoval(HashMap<K,V> m) {
}
}
//添加實體
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
//創(chuàng)建實體
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
//內(nèi)部類實現(xiàn)Iterator接口剂桥，進行遍歷操作
private abstract class HashIterator<E> implements Iterator<E> {
Entry<K,V> next; // next entry to return
int expectedModCount; // For fast-fail
int index; // current slot
Entry<K,V> current; // current entry
HashIterator() {
expectedModCount = modCount;
if (size > 0) { // advance to first entry
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
}
//是否有下一個元素
public final boolean hasNext() {
return next != null;
}
//返回下一個元素
final Entry<K,V> nextEntry() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) {
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)
;
}
current = e;
return e;
}
//刪除
public void remove() {
if (current == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
Object k = current.key;
current = null;
HashMap.this.removeEntryForKey(k);
expectedModCount = modCount;
}
}
private final class ValueIterator extends HashIterator<V> {
public V next() {
return nextEntry().value;
}
}
private final class KeyIterator extends HashIterator<K> {
public K next() {
return nextEntry().getKey();
}
}
private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
public Map.Entry<K,V> next() {
return nextEntry();
}
}
// Subclass overrides these to alter behavior of views' iterator() method
Iterator<K> newKeyIterator() {
return new KeyIterator();
}
Iterator<V> newValueIterator() {
return new ValueIterator();
}
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
// Views
private transient Set<Map.Entry<K,V>> entrySet = null;
//返回key組成的Set集合
public Set<K> keySet() {
Set<K> ks = keySet;
return (ks != null ? ks : (keySet = new KeySet()));
}
private final class KeySet extends AbstractSet<K> {
public Iterator<K> iterator() {
return newKeyIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsKey(o);
}
public boolean remove(Object o) {
return HashMap.this.removeEntryForKey(o) != null;
}
public void clear() {
HashMap.this.clear();
}
}
//返回Value組成的集合
public Collection<V> values() {
Collection<V> vs = values;
return (vs != null ? vs : (values = new Values()));
}
private final class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
return newValueIterator();
}
public int size() {
return size;
}
public boolean contains(Object o) {
return containsValue(o);
}
public void clear() {
HashMap.this.clear();
}
}
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<K,V> e = (Map.Entry<K,V>) o;
Entry<K,V> candidate = getEntry(e.getKey());
return candidate != null && candidate.equals(e);
}
public boolean remove(Object o) {
return removeMapping(o) != null;
}
public int size() {
return size;
}
public void clear() {
HashMap.this.clear();
}
}
//將對象寫入到輸出流中
private void writeObject(java.io.ObjectOutputStream s)
throws IOException
{
// Write out the threshold, loadfactor, and any hidden stuff
s.defaultWriteObject();
// Write out number of buckets
if (table==EMPTY_TABLE) {
s.writeInt(roundUpToPowerOf2(threshold));
} else {
s.writeInt(table.length);
}
// Write out size (number of Mappings)
s.writeInt(size);
// Write out keys and values (alternating)
if (size > 0) {
for(Map.Entry<K,V> e : entrySet0()) {
s.writeObject(e.getKey());
s.writeObject(e.getValue());
}
}
}
private static final long serialVersionUID = 362498820763181265L;
//從輸入流中讀取對象
private void readObject(java.io.ObjectInputStream s)
throws IOException, ClassNotFoundException
{
// Read in the threshold (ignored), loadfactor, and any hidden stuff
s.defaultReadObject();
if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
throw new InvalidObjectException("Illegal load factor: " +
loadFactor);
}
// set other fields that need values
table = (Entry<K,V>[]) EMPTY_TABLE;
// Read in number of buckets
s.readInt(); // ignored.
// Read number of mappings
int mappings = s.readInt();
if (mappings < 0)
throw new InvalidObjectException("Illegal mappings count: " +
mappings);
// capacity chosen by number of mappings and desired load (if >= 0.25)
int capacity = (int) Math.min(
mappings * Math.min(1 / loadFactor, 4.0f),
// we have limits...
HashMap.MAXIMUM_CAPACITY);
// allocate the bucket array;
if (mappings > 0) {
inflateTable(capacity);
} else {
threshold = capacity;
}
init(); // Give subclass a chance to do its thing.
// Read the keys and values, and put the mappings in the HashMap
for (int i = 0; i < mappings; i++) {
K key = (K) s.readObject();
V value = (V) s.readObject();
putForCreate(key, value);
}
}
// These methods are used when serializing HashSets
int capacity() { return table.length; }
float loadFactor() { return loadFactor; }
}
重要方法深度解析
構(gòu)造方法
HashMap() //無參構(gòu)造方法
HashMap(int initialCapacity) //指定初始容量的構(gòu)造方法
HashMap(int initialCapacity, float loadFactor) //指定初始容量和負載因子
HashMap(Map<? extends K,? extends V> m) //指定集合忠烛，轉(zhuǎn)化為HashMap
HashMap提供了四個構(gòu)造方法，構(gòu)造方法中 权逗，依靠第三個方法來執(zhí)行的况木，但是前三個方法都沒有進行數(shù)組的初始化操作垒拢，即使調(diào)用了構(gòu)造方法旬迹，此時存放HaspMap中數(shù)組元素的table表長度依舊為0 火惊。在第四個構(gòu)造方法中調(diào)用了inflateTable()方法完成了table的初始化操作，并將m中的元素添加到HashMap中奔垦。
添加方法
public V put(K key, V value) {
if (table == EMPTY_TABLE) { //是否初始化
inflateTable(threshold);
}
if (key == null) //放置在0號位置
return putForNullKey(value);
int hash = hash(key); //計算hash值
int i = indexFor(hash, table.length); //計算在Entry[]中的存儲位置
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
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++;
addEntry(hash, key, value, i); //添加到Map中
return null;
}
在該方法中屹耐，添加鍵值對時，首先進行table是否初始化的判斷椿猎，如果沒有進行初始化（分配空間惶岭，Entry[]數(shù)組的長度）。然后進行key是否為null的判斷犯眠，如果key==null ,放置在Entry[]的0號位置按灶。計算在Entry[]數(shù)組的存儲位置，判斷該位置上是否已有元素筐咧，如果已經(jīng)有元素存在鸯旁，則遍歷該Entry[]數(shù)組位置上的單鏈表。判斷key是否存在量蕊，如果key已經(jīng)存在铺罢，則用新的value值，替換點舊的value值残炮，并將舊的value值返回韭赘。如果key不存在于HashMap中，程序繼續(xù)向下執(zhí)行势就。將key-vlaue, 生成Entry實體泉瞻，添加到HashMap中的Entry[]數(shù)組中。
addEntry()
/*
* hash hash值
* key 鍵值
* value value值
* bucketIndex Entry[]數(shù)組中的存儲索引
* /
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //擴容操作苞冯，將數(shù)據(jù)元素重新計算位置后放入newTable中袖牙，鏈表的順序與之前的順序相反
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}
添加方法的具體操作，在添加之前先進行容量的判斷抱完，如果當前容量達到了閾值贼陶，并且需要存儲到Entry[]數(shù)組中，先進行擴容操作巧娱，擴充的容量為table長度的2倍碉怔。重新計算hash值，和數(shù)組存儲的位置禁添，擴容后的鏈表順序與擴容前的鏈表順序相反撮胧。然后將新添加的Entry實體存放到當前Entry[]位置鏈表的頭部。
在1.8之前老翘，新插入的元素都是放在了鏈表的頭部位置芹啥，但是這種操作在高并發(fā)的環(huán)境下容易導致死鎖锻离，所以1.8之后，新插入的元素都放在了鏈表的尾部墓怀。
獲取方法
public V get(Object key) {
if (key == null)
//返回table[0] 的value值
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
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方法中汽纠，首先計算hash值，然后調(diào)用indexFor()方法得到該key在table中的存儲位置傀履，得到該位置的單鏈表虱朵，遍歷列表找到key和指定key內(nèi)容相等的Entry，返回entry.value值钓账。
刪除方法
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key);
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;
while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}
return e;
}
刪除操作碴犬，先計算指定key的hash值，然后計算出table中的存儲位置梆暮，判斷當前位置是否Entry實體存在服协，如果沒有直接返回，若當前位置有Entry實體存在啦粹，則開始遍歷列表偿荷。定義了三個Entry引用，分別為pre, e ,next卖陵。 在循環(huán)遍歷的過程中遭顶，首先判斷pre 和 e 是否相等，若相等表明泪蔫，table的當前位置只有一個元素棒旗，直接將table[i] = next = null 。若形成了pre -> e -> next 的連接關(guān)系撩荣，判斷e的key是否和指定的key 相等铣揉，若相等則讓pre -> next ,e 失去引用。
總結(jié)：
1餐曹、實現(xiàn)原理
- HashMap是基于hashing的原理逛拱，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象台猴。
- 當我們給put(key, value)方法傳遞鍵和值時朽合，它先調(diào)用key.hashCode()方法，返回的hashCode值饱狂，用于找到bucket位置曹步，來儲存Entry對象。
- Map提供了一些常用方法休讳，如keySet()讲婚、entrySet()等方法。
keySet()方法返回值是Map中key值的集合俊柔；entrySet()的返回值也是返回一個Set集合筹麸，此集合的類型為Map.Entry活合。 - “如果兩個key的hashcode相同，你如何獲取值對象物赶？”答案：當我們調(diào)用get(key)方法白指，HashMap會使用key的hashcode值，找到bucket位置块差，然后獲取值對象侵续。
- “如果有兩個值對象，儲存在同一個bucket 憨闰？”答案：將會遍歷鏈表直到找到值對象。
- “這時會問因為你并沒有值對象去比較需五，你是如何確定確定找到值對象的鹉动？”答案：找到bucket位置之后，會調(diào)用keys.equals()方法宏邮，去找到鏈表中正確的節(jié)點泽示，最終找到要找的值對象。
完美的回答：
- HashMap基于hashing原理蜜氨，我們通過put(key,value)和get(key)方法儲存和獲取對象械筛。
- 當儲存對象時，我們將鍵值對傳遞給put(key,value)方法時飒炎，它調(diào)用鍵對象key的hashCode()方法來計算hashcode埋哟，然后找到bucket位置，來儲存值對象value郎汪。
- 當獲取對象時赤赊，通過key的equals()方法找到正確的鍵值對key-value，然后返回值對象value煞赢。
- HashMap使用鏈表來解決碰撞問題抛计，當發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中照筑。
- HashMap在每個鏈表節(jié)點中吹截，儲存 鍵值對key-value 對象。
- 當兩個不同的鍵對象key的hashcode相同時凝危，會發(fā)生什么波俄？它們會儲存在同一個bucket位置的鏈表中，并通過鍵對象key的equals()方法用來找到鍵值對key-value媒抠。
因為HashMap的好處非常多弟断，我曾經(jīng)在我的應用中使用HashMap作為緩存。因為金融領(lǐng)域非常多的運用Java趴生，也出于性能的考慮阀趴，我們會經(jīng)常用到HashMap和ConcurrentHashMap昏翰。
2、底層的數(shù)據(jù)結(jié)構(gòu)
HashMap的底層主要是基于數(shù)組和鏈表來實現(xiàn)的刘急，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置棚菊。
- HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同叔汁，計算出來的hash值就一樣统求。
- 如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的据块，這就出現(xiàn)了所謂的hash沖突码邻。
- 學過數(shù)據(jù)結(jié)構(gòu)的同學都知道，解決hash沖突的方法有很多另假，HashMap底層是通過鏈表來解決hash沖突的像屋。
補充知識：
- HashMap是基于哈希表的 Map 接口的實現(xiàn)。
- 此實現(xiàn)提供所有可選的映射操作边篮，并允許使用 null 值和 null 鍵己莺。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同戈轿。）
- 此類不保證映射的順序凌受，特別是它不保證該順序恒久不變谐算。
- 值得注意的是HashMap不是線程安全的析珊，如果想要線程安全的HashMap忆矛，可以通過Collections類的靜態(tài)方法synchronizedMap獲得線程安全的HashMap硝训。
Map map = Collections.synchronizedMap(new HashMap());
- HashMap結(jié)合了ArrayList與LinkedList兩個實現(xiàn)的優(yōu)點陕贮，雖然HashMap并不會向List的兩種實現(xiàn)那樣粉寞，在某項操作上性能較高拘鞋，但是在基本操作（get 和 put）上具有穩(wěn)定的性能珊擂。
JDK 1.8的 改變
在Jdk1.8中HashMap的實現(xiàn)方式做了一些改變杈湾，但是基本思想還是沒有變得解虱，只是在一些地方做了優(yōu)化，下面來看一下這些改變的地方,數(shù)據(jù)結(jié)構(gòu)的存儲由數(shù)組+鏈表的方式漆撞，變化為數(shù)組+鏈表+紅黑樹的存儲方式殴泰，在性能上進一步得到提升。
數(shù)據(jù)存儲方式
image
put方法簡單解析
public V put(K key, V value) {
//調(diào)用putVal()方法完成
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷table是否初始化浮驳，否則初始化操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//計算存儲的索引位置悍汛，如果沒有元素，直接賦值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//節(jié)點若已經(jīng)存在至会，執(zhí)行賦值操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷鏈表是否是紅黑樹
else if (p instanceof TreeNode)
//紅黑樹對象操作
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//為鏈表离咐，
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長度8，將鏈表轉(zhuǎn)化為紅黑樹存儲
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key存在，直接覆蓋
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//記錄修改次數(shù)
++modCount;
//判斷是否需要擴容
if (++size > threshold)
resize();
//空操作
afterNodeInsertion(evict);
return null;
}
總結(jié)
- HashMap采用hash算法來決定Map中key的存儲宵蛀，并通過hash算法來增加集合的大小昆著。
- hash表里可以存儲元素的位置稱為桶（bucket），如果通過key計算hash值發(fā)生沖突時术陶，那么將采用鏈表的形式凑懂，來存儲元素。
- HashMap的擴容操作是一項很耗時的任務(wù)梧宫，所以如果能估算Map的容量接谨，最好給它一個默認初始值，避免進行多次擴容塘匣。
- HashMap的線程是不安全的脓豪，多線程環(huán)境中推薦是ConcurrentHashMap。
1馆铁、實現(xiàn)原理
- HashMap是基于hashing的原理跑揉，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象埠巨。
- 當我們給put(key, value)方法傳遞鍵和值時，它先調(diào)用key.hashCode()方法现拒，返回的hashCode值辣垒，用于找到bucket位置，來儲存Entry對象印蔬。
- Map提供了一些常用方法勋桶，如keySet()、entrySet()等方法侥猬。
keySet()方法返回值是Map中key值的集合例驹；entrySet()的返回值也是返回一個Set集合，此集合的類型為Map.Entry退唠。 - “如果兩個key的hashcode相同鹃锈，你如何獲取值對象？”答案：當我們調(diào)用get(key)方法瞧预，HashMap會使用key的hashcode值屎债，找到bucket位置，然后獲取值對象垢油。
- “如果有兩個值對象盆驹，儲存在同一個bucket ？”答案：將會遍歷鏈表直到找到值對象滩愁。
- “這時會問因為你并沒有值對象去比較躯喇，你是如何確定確定找到值對象的？”答案：找到bucket位置之后硝枉，會調(diào)用keys.equals()方法廉丽，去找到鏈表中正確的節(jié)點倦微，最終找到要找的值對象。
完美的回答：
- HashMap基于hashing原理雅倒，我們通過put(key,value)和get(key)方法儲存和獲取對象璃诀。
- 當儲存對象時，我們將鍵值對傳遞給put(key,value)方法時蔑匣，它調(diào)用鍵對象key的hashCode()方法來計算hashcode劣欢，然后找到bucket位置，來儲存值對象value裁良。
- 當獲取對象時凿将，通過key的equals()方法找到正確的鍵值對key-value，然后返回值對象value价脾。
- HashMap使用鏈表來解決碰撞問題牧抵，當發(fā)生碰撞了，對象將會儲存在鏈表的下一個節(jié)點中侨把。
- HashMap在每個鏈表節(jié)點中犀变，儲存 鍵值對key-value 對象。
- 當兩個不同的鍵對象key的hashcode相同時秋柄，會發(fā)生什么获枝？它們會儲存在同一個bucket位置的鏈表中，并通過鍵對象key的equals()方法用來找到鍵值對key-value骇笔。
因為HashMap的好處非常多省店，我曾經(jīng)在我的應用中使用HashMap作為緩存。因為金融領(lǐng)域非常多的運用Java笨触，也出于性能的考慮懦傍，我們會經(jīng)常用到HashMap和ConcurrentHashMap。
2芦劣、底層的數(shù)據(jù)結(jié)構(gòu)
HashMap的底層主要是基于數(shù)組和鏈表來實現(xiàn)的粗俱，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來決定存儲的位置。
- HashMap中主要是通過key的hashCode來計算hash值的持寄，只要hashCode相同源梭，計算出來的hash值就一樣。
- 如果存儲的對象對多了稍味，就有可能不同的對象所算出來的hash值是相同的废麻，這就出現(xiàn)了所謂的hash沖突。
- 學過數(shù)據(jù)結(jié)構(gòu)的同學都知道模庐，解決hash沖突的方法有很多烛愧，HashMap底層是通過鏈表來解決hash沖突的。
補充知識：
- HashMap是基于哈希表的 Map 接口的實現(xiàn)。
- 此實現(xiàn)提供所有可選的映射操作怜姿，并允許使用 null 值和 null 鍵慎冤。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同沧卢。）
- 此類不保證映射的順序蚁堤，特別是它不保證該順序恒久不變。
- 值得注意的是HashMap不是線程安全的但狭，如果想要線程安全的HashMap披诗，可以通過Collections類的靜態(tài)方法synchronizedMap獲得線程安全的HashMap。
Map map = Collections.synchronizedMap(new HashMap());
- HashMap結(jié)合了ArrayList與LinkedList兩個實現(xiàn)的優(yōu)點立磁，雖然HashMap并不會向List的兩種實現(xiàn)那樣呈队，在某項操作上性能較高，但是在基本操作（get 和 put）上具有穩(wěn)定的性能唱歧。
