本解析源碼來自JDK1.7，JDK1.7對String類型的key進行了差別處理，但是JDK1.8中已經做出了修改，是以本文不讨論相關内容
HashMap概要
- HashMap是基于hash的map接口的非同步實作，與HashTable的差別HashTable是同步的，可以通過
Map m = Collections.synchronizedMap(new HashMap(...));
- 允許使用null鍵和null值
- 不保證映射順序和順序的不變性
- 在散列合理的情況下，HashMap的操作時間複雜度是O(1)
- 周遊HashMap的時間複雜度與HashMap的元素的個數（size）和HashMap的容量（table數組bucket的個數）有關，是以非必須設定較大的初始容量會造成周遊的效率變低
- 兩個重要概念：capacity和loadFactor
- capacity 表示的是HashTable中的桶的數量，也即table數組的大小
- loadFactor 表示的是進行擴容之前，Hash Table的擁擠程度，它代表了HashMap空間和時間權衡，初始為0.75，這個值越大，空間消耗越小，但是put,get等操作的時間效率會降低
- 當HashTable的元素的數量 size>capacity*loadFactor時，HashMap進行擴容，大緻會擴容至原先的2倍
- 如果HashMap的size可以預計，應當在初始化的時候設計initialCapacity>=size/loadFactor，進而避免頻繁的擴容和rehash(擴容後需要重新計算hash值)操作，提高效率
- 通過HashMap傳回的Iterator對HashMap周遊時，有fast-fail機制，即在周遊過程中如果出現對map的結構上的修改（更新已有key的value值不算結構修改）時會直接抛出異常，以免造成混亂，但是這種機制不保證一定可以正确執行（非同步）
-
設計初衷
Java中的兩種存儲結構
數組：尋址容易，插入和删除困難
連結清單：尋址困難，插入和删除容易
折中方案，連結清單的數組，即散清單是HashMap的底層存儲資料結構
HashMap實作的接口
- HashMap類頭部
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable - HashMap的Clone方法為淺拷貝，雖然建立了新的Entry，但是是基于原(key,value)對的，并沒有建立新的(key,value)
- HashMap實作了特殊的序列化機制，對key和value分别寫入，在另一端分别讀出(key,value)，然後将(key,value)對put進map的方法進行反序列化
- Map接口主要方法
public interface Map<K,V> {
// Query Operations
int size();
boolean isEmpty();
boolean containsKey(Object key);
boolean containsValue(Object value);
V get(Object key);
// Modification Operations
V put(K key, V value);
V remove(Object key);
// Bulk Operations
void putAll(Map<? extends K, ? extends V> m);
void clear();
// Views
Set<K> keySet();
Collection<V> values();
Set<Map.Entry<K, V>> entrySet();
interface Entry<K,V> {
K getKey();
V getValue();
V setValue(V value);
boolean equals(Object o);
int hashCode();
}
// Comparison and hashing
boolean equals(Object o);
int hashCode();
} Entry HashMap的基本節點
- HashMap的靜态内部類Entry，主要成員 Key，Value，next，hash
- table Entry的數組，Entry包含指向下一節點的引用next，進而table為連結清單的數組
/**
* 大小必要時可調整的數組。 其長度必須是2的指數次.
*/
transient Entry<K,V>[] table; //transient 序列化時不被序列化
static class Entry<K,V> implements Map.Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
int hash;
/**
* Creates new entry.
*/
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
...........
} 幾個重要成員
- 預設的capacity（table數組大小）為16
- 預設loadFactor（裝載因子）為0.75
- 初始化空HashMap時，table為空，不包含元素
- HashMap最大容量為 2^30
- threshold用來表示擴容的門檻值，大緻為capacity*loadFactor
- modCount用來實作fail-fast機制，通過計數HashMap結構修改的次數來确認在周遊過程中沒有被修改
- hashSeed用來影響String類型的key的hash值的計算
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final int MAXIMUM_CAPACITY = 1 << 30;
static final float DEFAULT_LOAD_FACTOR = 0.75f;
static final Entry<?,?>[] EMPTY_TABLE = {};
transient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;
transient int size;
// If table == EMPTY_TABLE then this is the initial capacity at which the
// table will be created when inflated.
int threshold;
final float loadFactor;
transient int modCount;
transient int hashSeed = 0; 構造方法
主要包含兩種構造方法:
- HashMap（int initialCapacity, float loadFactor）
- initialCapacity table數組的初始化大小，預設為16，如果不是2的指數次幂，調整為大于initialCapacity的最小的2的指數幂，但是不能大于MAXIMUM_CAPACITY（預設為2^30）
- loadFactor 影響table容量調整，當數組容量
loadFactor<HashMap元素（Entry）
-
HashMap(Map<? extends K,? extends V> m)
- 按照給定的map的大小與defaultInitialCapacity和defaultLoadFactor進行初始化
- 将原map中的資料拷貝到新的map中
- 這個過程中需要對Hash Table數組進行擴容（inflateTable），首先取大于等于原map size的最小的2的指數作為capacity，然後乘以loadFactor計算threshold
- 這裡面有一個小算法Integer.highestbit((number-1)<<1)來求大于等于number的最小2的指數。本來number右移一位取二進制最高位即為所求，但是考慮number本來就是2的指數時直接取number的情況
/**根據指定容量和負載因子構造HashMap*/
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);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
useAltHashing = sun.misc.VM.isBooted() &&
(capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
init();
}
/**根據指定的容量和預設的負載因子構造HashMap*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//預設的空的構造器
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
/**通過指定一個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);
}
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
table = new Entry[capacity];
initHashSeedAsNeeded(capacity);
}
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值
- String類型的key的hashcode是根據與字元串内容相關的，由于可能引起很多碰撞，是以值單獨計算
- Object類型的key的HashCode是基于其記憶體位址的。為了充分利用Integer值的高位，需要将高位的影響引入低位，（由于多數map的length是比較小的）
- 由于length是2的指數倍，是以可以用hash&（length-1）代替 hash%length，位運算有更高的效率
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);
}
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);
} 存入更新元素 put(key,value)
- 如果是key為null，周遊查找table中key是否有null，如果有更新value，否則添加null，value節點
- 如果key不為null，根據Key的hashcode擷取Hash值，根據Hash計算其在table中的索引，hash值計算時利用高位與低位進行異或操作，加入高位因素，來減少Hash碰撞
- 由于tablelength 都是2的指數次幂，是以indexFor用 HashCode&（table.lenght-1）取HashCode的低位
- 如果table[i]不為null(并不表示Hash值相同，HashCode不同也可能碰撞)，也就是發生了Hash碰撞，如果存在與keyHash相等（equals）或相同（==）的key，那麼更新value
- 如果table[i]為null，或者table[i]連結清單中不存在Hash值與Key相同且equals函數傳回true的情況就根據Hash值添加新的節點
- addEntry()方法首先判斷大小是否超過門檻值，然後使用頭插法，插入元素
- 此外HashMap還實作了一個私有的putForCreate()方法，用來在初始化建立map時使用，由于不需要檢查hash table是需要擴容以及modcount檢查，是以有更高的效率
NOTE
在判斷插入Entry是否為覆寫時，會先判斷Key的hashCode是否和map中的key相等，然後判斷Equals方法或者==，是以如果重寫了equals方法，要記得重寫hashcode方法，使得其邏輯相同，否則即使equals方法判斷相等也不會發生覆寫
public V put(K key, V value) {
// HashMap允許存放null鍵和null值。
// 當key為null時，調用putForNullKey方法，将value放置在數組第一個位置。
if (key == null)
return putForNullKey(value);
// 根據key的keyCode重新計算hash值。
int hash = hash(key);//注意這裡的實作是jdk1.7和以前的版本有差別的
// 搜尋指定hash值在對應table中的索引。
int i = indexFor(hash, table.length);
// 如果 i 索引處的 Entry 不為 null，通過循環不斷周遊 e 元素的下一個元素。
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;
}
}
// 如果i索引處的Entry為null，表明此處還沒有Entry。
modCount++;
// 将key、value添加到i索引處。
addEntry(hash, key, value, i);
return null;
}
/**産生哈希碼*/
final int hash(Object k) {
int h = 0;
if (useAltHashing) {
if (k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h = hashSeed;
}
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).
/*加入高位計算，防止低位不變，高位變化是引起hash沖突*/
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
/**産生索引，由于索引産生是不确定的，是以也就造成了HashMap順序的不确定性。
需要注意的是不同的hash産生的索引完全有可能相同的
該方法的實作十分的巧妙，它通過h & (length-1)來的到對象儲存的
索引，有可知道底層數組為2的n次方，這在速度上就有了明顯的優化
*/
static int indexFor(int h, int length) {
return h & (length-1);
}
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;
}
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);
}
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++;
}
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
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;
}
}
createEntry(hash, key, value, i);
} 讀取元素 get(key)
- 如果key為null，不能使用hash碼來定址，隻能通過周遊table的方法來找null
- 如果key不為null，就可以通過計算key的hash值定位到table數組中對應的連結清單，然後周遊連結清單找到hash值和equals方法傳回true或==成立的節點
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);
return null == entry ? null : entry.getValue();
}
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;
}
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;
} 元素删除 remove(key)
- 根據key的hash值定位table數組位置，然後周遊連結清單，找到hash值與equals為true或==成立點，做連結清單删除操作
- 其中删除注意頭結點的處理（e==prev），直接 table[i]=next
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;
} 元素查找 containsKey(key) containsValue(value)
- containsKey(key) 先用key的hash碼定位到table數組中的對應連結清單，然後周遊連結清單進行查詢，效率取決于連結清單的長度
- containsValue(value) 對table數組進行周遊，然後周遊數組中的每個連結清單，時間複雜度取決于table數組的長度與map.size()，效率低
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;
}
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 boolean containsKey(Object key) {
return getEntry(key) != null;
}
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;
} 調整大小 resize(newLength)
- 調整的時機 （負載因子）x（容量）>（Map 大小），則調整 Map大小 為之前的二倍，該過程包含了table的複制，性能消耗較大，如果map大小已知，可以在初始化時合理設定map的初始大小，避免擴容。
- 如果數組大小已經到達最大容量，将門檻值置為Integer.MAX_VAlUE,不再進行擴容
- 新申請數組，重新定址并将原數組中的Entry轉移到新數組中，由于容量變化，即使Hash值不變，Entry的index也會改變，index=hash&(length-1),hash值對length取餘，length變化，index也會變化
- transfer使用頭插法将原hashtable所有元素進行複制，首先儲存原原數組的e.next節點，然後将e頭插插入新的hash table，e移動到原數組next
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);
}
/**
* Transfers all entries from current table to 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) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
} 疊代器 Iterator
由于數組大小調整後，元素的index都需要重新計算，是以HashMap并不能保證元素的周遊順序不變
- KeyIterator，ValueIterator都是基于HashIterator的，隻是重寫的next方法
- 由于hash table 是稀疏的，是以需要找到第一個元素，關鍵算法
while (index < t.length && (next = t[index++]) == null)
- next算法要考慮current為一個連結清單的尾節點，這時需要查找table中下一個不為null的節點
- 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();
}
} KeySet視圖
- 通過KeySet視圖更改HashMap和通過HashMap做出的更改有同樣的效果，會互相影響
- set視圖支援remove，removeAll，retainAll,clear删除操作但是不支援添加操作（add,addAll）
- 通過繼承Collection的add方法，當調用add方法時直接抛出UnsupportedOperationException，由于addAll方法需要調用add，也就禁止了addAll方法
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();
}
}
//Collection.java
public boolean add(E e) {
throw new UnsupportedOperationException();
} Values視圖
- Values傳回的是Collection而不是Set，因為Values不保證元素不重複
- Values更改與HashMap的更改等效，互相影響
- Values同樣隻支援删除操作，不支援添加操作
- EntrySet與Values類似
疑問：為什麼EntrySet()還要調用EntrySet0()，并沒有發現這一步調用的必要性
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();
}
} 解決hash碰撞的方法
-
開放定址法
從發生沖突的那個單元開始，按照一定的次序，從散清單中查找出一個空閑的存儲單元，把發生沖突的待插入元素存入到該單元中的一類處理沖突的方法。
- 再哈希法
- 鍊位址法（JDK1.7使用）
- 建立一 公共溢出區
modCount fast-fail機制
modCount 記錄修改此清單的次數：包括改變清單的結構，改變清單的大小，打亂清單的順序等使正在進行疊代産生錯誤的結果.(僅僅設定元素的值并不是結構的修改),如果在使用疊代器的過程中有其他的線程修改了Map就會抛出ConcurrentModificationException這就是Fail-Fast機制。
Clone方法
Clone實作的是淺拷貝，雖然重新建立了Entry但是并沒有重新建立key，value，即如果通過原HashMap的key的引用改變了key的屬性，clone出來的HashMap的key也會跟着改變，克隆出來的Map的數組的大小也不一定與原Map相同
- 首先會建立一個空的HashMap對象
- 然後對該HashMap進行擴容，容量大小取Math.min(目前table大小，HashMap的最大容量，目前的Size*（Math.min(1/loadFactor,4))，克隆出來的HashMap的數組初始大小并不會與目前Map一緻，而是考慮合理的初始化loadFactor之後的結果。
- 最後調用putAllForCreate(this)依次将目前Map的(key,value)放到Map中去，過程中雖然建立了新的Entry但是并沒有建立新的key，value，通過原HashMap和通過克隆出來的HashMap改變(key,value)效果是等同的。
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;
}
private void putAllForCreate(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putForCreate(e.getKey(), e.getValue());
}
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
/**
* Look for preexisting entry for key. This will never happen for
* clone or deserialize. It will only happen for construction if the
* input Map is a sorted map whose ordering is inconsistent w/ equals.
*/
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;
}
}
createEntry(hash, key, value, i);
}
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(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
} 序列化
- 存儲hashmap的元素的數組被聲明為transient，即在初始化時忽略，因為相同對象的Hash值在不同機器上可能是不同的，是以直接序列化後map的get(key)方法會出現錯誤
- HashMap重寫了readObject()和writeObject()方法來保證序列化的正确性
- 政策在序列化時，針對Entry的key與value分别單獨序列化，當反序列化時，再單獨處理即可
transient Entry<K,V>[] table; //transient 序列化時不被序列化
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);
}
}
private void putForCreate(K key, V value) {
int hash = null == key ? 0 : hash(key);
int i = indexFor(hash, table.length);
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;
}
}
createEntry(hash, key, value, i);
} 與HashTable的差別
- 繼承的對象不同 HashMap extends AbstractMap HashTable extends Dictionary
- HashTable 是同步的，且不允許key為null，其根據hash值獲得索引的方法也不同，都是取模，但是HashMap采用位運算更高效
public synchronized V put(K key, V value) { //###### 注意這裡1
// Make sure the value is not null
if (value == null) { //###### 注意這裡 2
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry tab[] = table;
int hash = key.hashCode(); //###### 注意這裡 3
int index = (hash & 0x7FFFFFFF) % tab.length;### 注意這裡 4
for (Entry e = tab[index]; e != null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V old = e.value;
e.value = value;
return old;
}
}
modCount++;
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
rehash();
tab = table;
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
Entry e = tab[index];
tab[index] = new Entry(hash, key, value, e);
count++;
return null;
} 與JDK1.8的差別
-
JDK1.8不再單純使用連結清單來進行存儲，而是使用連結清單（元素較少）與紅黑樹（元素較多）
在jdk8中，仍然會根據key.hashCode()計算出hash值，再通過這個hash值去定位這個key，但是不同的是，當發生沖突時，會采用連結清單和紅黑樹兩種方法去處理，當結點個數較少時用連結清單（用Node存儲），個數較多時用紅黑樹（用TreeNode存儲），同時結點也不叫Entry了，而是分成了Node和TreeNode。再最壞的情況下，連結清單查找的時間複雜度為O(n),而紅黑樹一直是O(logn),這樣會提高HashMap的效率。jdk8中的HashMap中定義了一個變量TREEIFY_THRESHOLD，當節點個數>= TREEIFY_THRESHOLD - 1時，HashMap将采用紅黑樹存儲
-
不再差別對待String類key
由于String對象的Hash值計算方法較弱，jdk7中在面對key為String的時候采用了差別對待，會有alternative hashing，但是這個在jdk8中已經被删除了
![C經典書籍筆記——C陷阱與缺陷②(文法陷阱之優先級)一、錯誤案列 二、優先級規律[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)