概述
文章的內(nèi)容基于JDK1.7進(jìn)行分析，之所以選用這個(gè)版本，是因?yàn)?.8的有些類做了改動(dòng)，增加了閱讀的難度，雖然是1.7，但是對(duì)于1.8做了重大改動(dòng)的內(nèi)容，文章也會(huì)進(jìn)行說(shuō)明。
HashMap基于Map接口實(shí)現(xiàn)，元素以鍵值對(duì)的方式存儲(chǔ)，并且允許使用null 建和null 值， 因?yàn)閗ey不允許重復(fù)，因此只能有一個(gè)鍵為null,另外HashMap不能保證放入元素的順序，它是無(wú)序的，和放入的順序并不能相同。HashMap是線程不安全的。
數(shù)據(jù)結(jié)構(gòu)
繼承關(guān)系
public class HashMap<K,V>extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
實(shí)現(xiàn)接口
Serializable, Cloneable, Map<K,V>
基本屬性
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默認(rèn)初始化大小 16
static final float DEFAULT_LOAD_FACTOR = 0.75f; //負(fù)載因子0.75
static final Entry<?,?>[] EMPTY_TABLE = {}; //初始化的默認(rèn)數(shù)組
transient int size; //HashMap中元素的數(shù)量
int threshold; //判斷是否需要調(diào)整HashMap的容量
源碼解析
HashMap底層數(shù)據(jù)存儲(chǔ)結(jié)構(gòu).png
在進(jìn)行源碼解析之前，先從總體上對(duì)HashMap的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)進(jìn)行一個(gè)大體上的說(shuō)明。存儲(chǔ)結(jié)構(gòu)如上圖所示。
HashMap采用Entry數(shù)組來(lái)存儲(chǔ)key-value對(duì)，每一個(gè)鍵值對(duì)組成了一個(gè)Entry實(shí)體，Entry類實(shí)際上是一個(gè)單向的鏈表結(jié)構(gòu)，它具有Next指針，可以連接下一個(gè)Entry實(shí)體，依次來(lái)解決Hash沖突的問(wèn)題，因?yàn)镠ashMap是按照Key的hash值來(lái)計(jì)算Entry在HashMap中存儲(chǔ)的位置的，如果hash值相同，而key內(nèi)容不相等，那么就用鏈表來(lái)解決這種hash沖突。
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
{
//默認(rèn)初始化的容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大的容量
static final int MAXIMUM_CAPACITY = 1 << 30;
//負(fù)載因子，當(dāng)容量達(dá)到75%時(shí)就進(jìn)行擴(kuò)容操作
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//當(dāng)數(shù)組還沒(méi)有進(jìn)行擴(kuò)容操作的時(shí)候，共享的一個(gè)空表對(duì)象
static final Entry<?,?>[] EMPTY_TABLE = {};
//table,進(jìn)行擴(kuò)容操作，長(zhǎng)度必須2的n次方
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
//Map中包含的元素?cái)?shù)量
transient int size;
//閾值，用于判斷是否需要擴(kuò)容（threshold = 容量*負(fù)載因子）
int threshold;
//加載因子實(shí)際的大小
final float loadFactor;
//HashMap改變的次數(shù)
transient int modCount;
static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;
//內(nèi)部類，通過(guò)vm來(lái)修改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)造方法，指定初始容量和負(fù)載因子
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è)置負(fù)載因子
threshold = initialCapacity; //初始容量
init(); //不做任何操作
}
//構(gòu)造方法，指定了初始容量
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//無(wú)參構(gòu)造方法，使用默認(rèn)的容量大小和負(fù)載因子，并調(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;
}
//擴(kuò)充表，HashMap初始化時(shí)是一個(gè)空數(shù)組，此方法執(zhí)行重新復(fù)制操作，創(chuàng)建一個(gè)新的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() {
}
//與虛擬機(jī)設(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;
}
//計(jì)算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,和表的長(zhǎng)度，返回存放的索引
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中鍵值對(duì)的數(shù)量
public int size() {
return size;
}
//判斷集合是否為空
public boolean isEmpty() {
return size == 0;
}
//返回key ，對(duì)應(yīng)的值
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實(shí)體，不存在返回null
final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key); //計(jì)算key的 hash值
//定位到Entry[] 數(shù)組中的存儲(chǔ)位置，開(kāi)始遍歷該位置是否有鏈表存在
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
//判斷是否有鍵位key 的entry實(shí)體。有就返回。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
//向map中添加key-value 鍵值對(duì)，如果可以包含了key的映射，則舊的value將被替換
public V put(K key, V value) {
if (table == EMPTY_TABLE) { //table如果為空，進(jìn)行初始化操作
inflateTable(threshold);
}
if (key == null) //key 為null ,放入數(shù)組的0號(hào)索引位置
return putForNullKey(value);
int hash = hash(key); //計(jì)算key的hash值
int i = indexFor(hash, table.length); //計(jì)算key在entry數(shù)組中存儲(chǔ)的位置
//判斷該位置是否已經(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實(shí)體，添加到Map中
return null;
}
//key = null, 對(duì)應(yīng)的操作，keyweinull ,存放在entry[]中的0號(hào)位置。并用新值替換舊值
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); //計(jì)算hash值
int i = indexFor(hash, table.length); //計(jì)算在HashMap中的存儲(chǔ)位置
//遍歷i號(hào)存儲(chǔ)位置的鏈表
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實(shí)體，存放到i號(hào)位置中
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());
}
//擴(kuò)容操作
void resize(int newCapacity) {
Entry[] oldTable = table; //將table賦值給新的引用
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
//創(chuàng)建一個(gè)長(zhǎng)度為newCapacity的數(shù)組
Entry[] newTable = new Entry[newCapacity];
//將table中的元素復(fù)制到newTable中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
//更改閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
//將table中的數(shù)據(jù)復(fù)制到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) { //是否需要重新計(jì)算Hash值
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); //計(jì)算存儲(chǔ)的位置
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));
}
//判斷是否需要擴(kuò)容
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對(duì)應(yīng)的value值
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
//返回key對(duì)應(yīng)的實(shí)體
final Entry<K,V> removeEntryForKey(Object key) {
if (size == 0) {
return null;
}
int hash = (key == null) ? 0 : hash(key); //計(jì)算key的hash值
int i = indexFor(hash, table.length); //計(jì)算存儲(chǔ)位置
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;
}
//刪除一個(gè)指定的實(shí)體
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的實(shí)體
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用來(lái)存儲(chǔ)鍵值對(duì)，HashMap中的Entry[]用來(lái)存儲(chǔ)entry
static class Entry<K,V> implements Map.Entry<K,V> {
final K key; //鍵
V value; //值
Entry<K,V> next; //采用鏈表存儲(chǔ)HashCode相同的鍵值對(duì)，next指向下一個(gè)entry
int hash; //entry的hash值
//構(gòu)造方法， 負(fù)責(zé)初始化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();
}
//當(dāng)使用相同的key的value被覆蓋時(shí)調(diào)用
void recordAccess(HashMap<K,V> m) {
}
//每移除一個(gè)entry就被調(diào)用一次
void recordRemoval(HashMap<K,V> m) {
}
}
//添加實(shí)體
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)建實(shí)體
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)部類實(shí)現(xiàn)Iterator接口，進(jìn)行遍歷操作
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)
;
}
}
//是否有下一個(gè)元素
public final boolean hasNext() {
return next != null;
}
//返回下一個(gè)元素
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();
}
}
//將對(duì)象寫入到輸出流中
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;
//從輸入流中讀取對(duì)象
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() //無(wú)參構(gòu)造方法
HashMap(int initialCapacity) //指定初始容量的構(gòu)造方法
HashMap(int initialCapacity, float loadFactor) //指定初始容量和負(fù)載因子
HashMap(Map<? extends K,? extends V> m) //指定集合，轉(zhuǎn)化為HashMap
HashMap提供了四個(gè)構(gòu)造方法，構(gòu)造方法中 ，依靠第三個(gè)方法來(lái)執(zhí)行的，但是前三個(gè)方法都沒(méi)有進(jìn)行數(shù)組的初始化操作，即使調(diào)用了構(gòu)造方法此時(shí)存放HaspMap中數(shù)組元素的table表長(zhǎng)度依舊為0 。在第四個(gè)構(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號(hào)位置
return putForNullKey(value);
int hash = hash(key); //計(jì)算hash值
int i = indexFor(hash, table.length); //計(jì)算在Entry[]中的存儲(chǔ)位置
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;
}
在該方法中，添加鍵值對(duì)時(shí)，首先進(jìn)行table是否初始化的判斷，如果沒(méi)有進(jìn)行初始化（分配空間，Entry[]數(shù)組的長(zhǎng)度）。然后進(jìn)行key是否為null的判斷，如果key==null ,放置在Entry[]的0號(hào)位置。計(jì)算在Entry[]數(shù)組的存儲(chǔ)位置，判斷該位置上是否已有元素，如果已經(jīng)有元素存在，則遍歷該Entry[]數(shù)組位置上的單鏈表。判斷key是否存在，如果key已經(jīng)存在，則用新的value值，替換點(diǎn)舊的value值，并將舊的value值返回。如果key不存在于HashMap中，程序繼續(xù)向下執(zhí)行。將key-vlaue, 生成Entry實(shí)體，添加到HashMap中的Entry[]數(shù)組中。
addEntry()
/*
* hash hash值
* key 鍵值
* value value值
* bucketIndex Entry[]數(shù)組中的存儲(chǔ)索引
* /
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); //擴(kuò)容操作，將數(shù)據(jù)元素重新計(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++;
}
添加到方法的具體操作，在添加之前先進(jìn)行容量的判斷，如果當(dāng)前容量達(dá)到了閾值，并且需要存儲(chǔ)到Entry[]數(shù)組中，先進(jìn)性擴(kuò)容操作，空充的容量為table長(zhǎng)度的2倍。重新計(jì)算hash值，和數(shù)組存儲(chǔ)的位置，擴(kuò)容后的鏈表順序與擴(kuò)容前的鏈表順序相反。然后將新添加的Entry實(shí)體存放到當(dāng)前Entry[]位置鏈表的頭部。在1.8之前，新插入的元素都是放在了鏈表的頭部位置，但是這種操作在高并發(fā)的環(huán)境下容易導(dǎo)致死鎖，所以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方法中，首先計(jì)算hash值，然后調(diào)用indexFor()方法得到該key在table中的存儲(chǔ)位置，得到該位置的單鏈表，遍歷列表找到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;
}
刪除操作，先計(jì)算指定key的hash值，然后計(jì)算出table中的存儲(chǔ)位置，判斷當(dāng)前位置是否Entry實(shí)體存在，如果沒(méi)有直接返回，若當(dāng)前位置有Entry實(shí)體存在，則開(kāi)始遍歷列表。定義了三個(gè)Entry引用，分別為pre, e ,next。 在循環(huán)遍歷的過(guò)程中，首先判斷pre 和 e 是否相等，若相等表明，table的當(dāng)前位置只有一個(gè)元素，直接將table[i] = next = null 。若形成了pre -> e -> next 的連接關(guān)系，判斷e的key是否和指定的key 相等，若相等則讓pre -> next ,e 失去引用。
JDK 1.8的 改變
在Jdk1.8中HashMap的實(shí)現(xiàn)方式做了一些改變，但是基本思想還是沒(méi)有變得，只是在一些地方做了優(yōu)化，下面來(lái)看一下這些改變的地方,數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)由數(shù)組+鏈表的方式，變化為數(shù)組+鏈表+紅黑樹(shù)的存儲(chǔ)方式，在性能上進(jìn)一步得到提升。
數(shù)據(jù)存儲(chǔ)方式
java1.8 HashMap數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)變化.png
put方法簡(jiǎn)單解析
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;
//計(jì)算存儲(chǔ)的索引位置，如果沒(méi)有元素，直接賦值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//節(jié)點(diǎn)若已經(jīng)存在，執(zhí)行賦值操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判斷鏈表是否是紅黑樹(shù)
else if (p instanceof TreeNode)
//紅黑樹(shù)對(duì)象操作
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);
//鏈表長(zhǎng)度8，將鏈表轉(zhuǎn)化為紅黑樹(shù)存儲(chǔ)
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;
//判斷是否需要擴(kuò)容
if (++size > threshold)
resize();
//空操作
afterNodeInsertion(evict);
return null;
}
下面將這個(gè)過(guò)程總結(jié)一下：
- 如果當(dāng)前map中沒(méi)有數(shù)據(jù)，執(zhí)行resize方法
- 如果要插入的鍵值對(duì)要存放的位置上剛好沒(méi)有元素，那么就把它封裝成Node對(duì)象，并放在這個(gè)位置上。
- 如果發(fā)生碰撞，判斷node的類型是紅黑樹(shù)還是鏈表：
3.1 如果為紅黑樹(shù)，則將K-V對(duì)插在紅黑樹(shù)對(duì)應(yīng)的位置。
3.2 如果為鏈表，遍歷鏈表：
a.如果為鏈表最后一個(gè)node ,則將新的node節(jié)點(diǎn)插入到鏈表尾
b.插入完，如果鏈表的node數(shù)量大于8，則將鏈表轉(zhuǎn)為紅黑樹(shù)的操作；如果當(dāng)前哈希表為空或數(shù)組長(zhǎng)度小于64，會(huì)擴(kuò)容，否則轉(zhuǎn)化為紅黑樹(shù)。轉(zhuǎn)化的過(guò)程：先遍歷鏈表 ，將鏈表的節(jié)點(diǎn)轉(zhuǎn)化為紅黑樹(shù)的節(jié)點(diǎn)；然后將鏈表轉(zhuǎn)化為紅黑樹(shù)。
c.遍歷鏈表時(shí)，如果key已存在，則直接bredk循環(huán)。 - 判斷是否要擴(kuò)容
- 返回
總結(jié)
HashMap采用hash算法來(lái)決定Map中key的存儲(chǔ)，并通過(guò)hash算法來(lái)增加集合的大小。hash表里可以存儲(chǔ)元素的位置稱為桶，如果通過(guò)key計(jì)算hash值發(fā)生沖突時(shí)，那么將采用鏈表的形式，來(lái)存儲(chǔ)元素。HashMap的擴(kuò)容操作是一項(xiàng)很耗時(shí)的任務(wù)，所以如果能估算Map的容量，最好給它一個(gè)默認(rèn)初始值，避免進(jìn)行多次擴(kuò)容。HashMap的線程是不安全的，多線程環(huán)境中推薦是ConcurrentHashMap。
