前言
本篇文章我們將帶領大家一起看看HashMap的源碼涉瘾，從源碼角度出發(fā)溺欧，看看HashMap里面的數(shù)據(jù)結構是這么樣的，怎么往HashMap里面put和get數(shù)據(jù)色迂，什么是HashMap指針碰撞等等
在JDK 1.7 Android 24之前（包括）屉栓，HashMap的數(shù)據(jù)結構是數(shù)組+鏈表</br>
在JDK 1.8 Android 25之后俺夕，HashMap的數(shù)據(jù)結構是數(shù)組+鏈表+紅黑樹</br>
HashMap的put()方法
接下來我們一起看下Android 24里面HashMap的源碼
我們往HashMap里面put元素的時候都有哪些操作呢促王？
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
if (key == null)
return putForNullKey(value);
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
int i = indexFor(hash, table.length);
for (HashMapEntry<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);
return null;
}
首先我們會拿到key對應的一個hash值瞒大，indexFor()方法會拿到一個table數(shù)組的索引i系洛，i的值是hash值與數(shù)組長度-1之后的與操作
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);
}
key value一一對應
在開發(fā)中經(jīng)常會重復往同一個key里面put幾個值俊性，HashMap是如何保證key value的一對一映射關系的
for (HashMapEntry<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;
}
}
如果當前index對應的鏈表有數(shù)據(jù)，就循環(huán)遍歷描扯，如果key值存在定页，將新傳進來的value復制給e的vlue
如果不存在就要去重新創(chuàng)建了。</br>
碰撞問題
key是唯一的绽诚，key對應的hashcode也唯一典徊，但是hashcode與length-1的與結果不唯一。當兩個不同的key的hashcode & length -1 相同的時候就會出現(xiàn)常說的hash碰撞問題恩够。哈希表是如何解決碰撞問題的呢宫峦？一起看下源碼。</br>
addEntry() -> createEntry()
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMapEntry<K,V> e = table[bucketIndex];
table[bucketIndex] = new HashMapEntry<>(hash, key, value, e);
size++;
}
會把key value作為新的鏈表的key和value玫鸟，之前的鏈表作為當前鏈表的next節(jié)點导绷，然后生成新的鏈表重新賦值給數(shù)組對應的元素。這就是我們常說的HashMap的碰撞問題屎飘。
HashMap就是采用頭插法解決hash沖突的妥曲。
get()方法
public V get(Object key) {
if (key == null)
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 : sun.misc.Hashing.singleWordWangJenkinsHash(key);
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;
}
前面了解了怎么存數(shù)據(jù)的，取數(shù)據(jù)就容易理解了钦购。通過key算出hash值和index檐盟，找到對應的table[index]，遍歷鏈表找到value押桃。</br>
擴容
當hashmap所有的put操作都沖突的時候葵萎，即所有的元素都在一個table[index]里面，這個時候hashmap退化成了單鏈表唱凯，效率最低羡忘。</br>
為了盡量避免這種情況，hashmap需要擴容磕昼。length越大卷雕，沖突的概率就越低了。</br>
加載因子 DEFAULT_LOAD_FACTOR 默認 0.75
HashMap創(chuàng)建的時候如果不設置的話票从，默認的大小是16漫雕。
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
閾值 = DEFAULT_LOAD_FACTOR * CAPACITY 默認是12
當hashmap的元素大于閾值時就會擴容滨嘱。
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length);
hash = (null != key) ? sun.misc.Hashing.singleWordWangJenkinsHash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void resize(int newCapacity) {
HashMapEntry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
HashMapEntry[] newTable = new HashMapEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
當hashmap resize()的時候，hashmap的length發(fā)生了變化浸间，那么值錢計算的index 是錯誤的了太雨，就需要重新計算了。
/**
* Transfers all entries from current table to newTable.
*/
void transfer(HashMapEntry[] newTable) {
int newCapacity = newTable.length;
for (HashMapEntry<K,V> e : table) {
while(null != e) {
HashMapEntry<K,V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
所以哈希表的擴容的操作是很消耗性能的魁蒜，因此我們在new HashMap(size)的時候應該將size傳給構造函數(shù)囊扳，大小為 hashmap所有元素的大小/0.75 + 1</br>
在put()方法最開始我們還有一個地方?jīng)]講
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
/**
* Inflates the table.
*/
private void inflateTable(int toSize) {
// Find a power of 2 >= toSize
int capacity = roundUpToPowerOf2(toSize);
// Android-changed: Replace usage of Math.min() here because this method is
// called from the <clinit> of runtime, at which point the native libraries
// needed by Float.* might not be loaded.
float thresholdFloat = capacity * loadFactor;
if (thresholdFloat > MAXIMUM_CAPACITY + 1) {
thresholdFloat = MAXIMUM_CAPACITY + 1;
}
threshold = (int) thresholdFloat;
table = new HashMapEntry[capacity];
}
private static int roundUpToPowerOf2(int number) {
// assert number >= 0 : "number must be non-negative";
int rounded = number >= MAXIMUM_CAPACITY
? MAXIMUM_CAPACITY
: (rounded = Integer.highestOneBit(number)) != 0
? (Integer.bitCount(number) > 1) ? rounded << 1 : rounded
: 1;
return rounded;
}
這個方法主要是初始化哈希表，計算哈希表的大忻饭摺（必須為2的冪）</br>
