散列表
也叫哈希表
散列表本質(zhì)是數(shù)組存儲揍庄，通過 key-value 的形式存儲數(shù)據(jù)，所以當取 value 的時候心软，實際上取數(shù)組某個位置的元素颗祝，并且以 key 的 hashCode 作為 value 在數(shù)組中的位置。
List vs Set
1泌枪、List 是按 add 順序存儲概荷，且元素可以重復，元素有索引碌燕，可以根據(jù)元素位置進行 get误证。
2、Set 存儲元素無序(hashCode)修壕，元素不可重復(HashMap)雷厂，沒有 get 方法，只能通過迭代器獲取元素叠殷。
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
HashMap
- 相同的鍵值對將被覆蓋改鲫。需保證Key已經(jīng) 重寫equals()
- 存儲位置與Key的hashcode()相關(guān)，需確保 重寫hashcode()
equals
Object：返回==林束，判斷地址
String：== && 所有字符相等
- 最多允許一條數(shù)據(jù)的Key為Null像棘，可允許多條的值為Null
- 存儲數(shù)據(jù)的順序不確定，且可能因為擴容而數(shù)據(jù)改變
- 數(shù)組的存儲方式在內(nèi)存的地址是連續(xù)的壶冒，大小固定缕题，一旦分配不能被其他引用占用。它的特點是查詢快胖腾，時間復雜度是O(1)烟零，插入和刪除的操作比較慢，時間復雜度是O(n)咸作，鏈表的存儲方式是非連續(xù)的锨阿，大小不固定，特點與數(shù)組相反记罚，插入和刪除快墅诡，查詢速度慢。
原理
image
1. key == Null? Enrty[0] : 步驟2
2. key的 hashCode() 經(jīng)過兩次Hash桐智，特征值是int
3. 對Entry[]的length求余hash & (length-1)末早，得到Entry的index
4. 如果該位置上已經(jīng)有元素了烟馅，就說明存在hash沖突，這樣會在index位置生成鏈表
JDK的String的Hash算法
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
選擇31是因為它是一個奇素數(shù)然磷，如果它做乘法溢出的時候郑趁，信息會丟失，而且當和2做乘法的時候相當于移位姿搜。
31的一個很好的特性就是做乘法的時候可以被移位和減法代替的時候有更好的性能體現(xiàn)寡润。例如31i相當于是i左移5位減去i，即31i == (i<<5)-i』居現(xiàn)代的虛擬內(nèi)存系統(tǒng)都使用這種自動優(yōu)化
put方法
1. 判斷key是否已經(jīng)存在，存在則替換攻礼，返回舊值
2. 檢查容量是否到達閾值threshold
3. 如果元素個數(shù)已經(jīng)達到閾值业踢，則擴容，
并把原來的元素移動過去礁扮。
4.擴容實現(xiàn)：這里會新建一個更大的數(shù)組
并通過transfer方法知举，移動元素。
5.移動的邏輯：遍歷原來table中每個位置的鏈表太伊，
并對每個元素進行重新hash雇锡，
在新的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;
}
}
}
