阿裡面試90%以上會問到的資料結構；HashMap

BAT面試必問；

關于hashmap，你知道多少？你知道hashmap的工作原理嗎？

1.該問題很有深度

2.能答出多少決定崗位和薪資.

3.問題的方式多種多樣

一.首先我們了解下HashMap是什麼

HashMap是Java常用的用來儲存鍵值對的資料結構，它是線程不安全的，可以儲存null鍵值，這些大家經常用，也都知道，接下來根據源碼分析一下HashMap的實作。

1、實作原理

HashMap采用數組散列+連結清單的方式來儲存鍵值對，鍵值對的對象實作如下：

static class Entry<K,V> implements Map.Entry<K,V> { 
 final K key; 
 V value; 
 Entry<K,V> next; 
 final int hash; 
 …… 
} 
           

通過一個Entry的數組table就實作了多個對象的儲存，使用哈希值和鍵值解決了在插入和查找時的沖突。

2、put方法，寫入鍵值對

public V put(K key, V value){
 //如果 key 為 null，調用 putForNullKey 方法寫入null鍵的值
 if (key == null){
 return putForNullKey(value);
}
//根據 key 的 keyCode 計算 Hash 值 
int hash = hash(key.hashCode());
//查找hash值在table中的索引
int i = indexFor(hash, table.length);
// 如果 i 索引處的 Entry 不為 null，通過循環不斷周遊連結清單查找是否在連結清單中有相同key的Entry
for (Entry<K,V> e = tablei; e != null; e = e.next) {
 Object k;
 //找到與插入的值的key和hash相同的Entry
 if (e.hash == hash && ((k = e.key) == key|| key.equals(k)){
 //key值相同時直接替換value值，跳出函數
 V oldValue = e.value;
 e.value = value; e.recordAccess(this); return oldValue; } }
// 如果 i 索引處的 Entry 為 null 或者key的hash值相同而key不同 ，則需要新增Entry
modCount++; 
// 将 key、value 添加到 i 索引處
addEntry(hash, key, value, i); 
return null; 
} 
           

在put方法中解決hash碰撞的方式很清楚，即當兩個entry的hash值相同時，需要對key值是否相同進行判斷，隻有key和hash都相同，才能進行修改，否則認為不是同一個entry。

3.addEntry的實作

代碼：

void addEntry(int hash, K key, V value, int bucketIndex) { // 擷取指定 bucketIndex 索引處的 Entry
Entry<K,V> e = tablebucketIndex; 
tablebucketIndex = new Entry<K,V>(hash, key, value, e); // 如果 Map 中的 key-value 對的數量超過了極限
if (size++ >= threshold)
 resize(2 table.length);
} 
           

在建立新Entry時如果table的bucketIndex處有元素的話，建立時需要将entry的next設定為原先存儲的元素。

二，HashMap工作原理

以下為目錄，有需要完整進階視訊可以加Android進階群；701740775免費擷取

1.目錄

2.順序表與連結清單

3.Hsh表

4.Hash源碼

5.碰撞

需要完整進階視訊詳解可以加Android進階群；701740775免費擷取！

附錄Android進階技術大綱和進階視訊；