原始碼衝浪之HashMap
HashMap是我們最常用到的集合之一，是java非常典型的資料結構。學習它的原始碼是非常只有必要的，我們所要了解的並不僅僅是“HashMap不是執行緒安全的，HashTable是執行緒安全的，通過synchronized實現的。HashMap取值非常快”等等。
瞭解hashmap必須要先對hashmap的儲存結構有個瞭解 複製程式碼
它是屬於陣列及連結串列相結合的儲存結構。如上圖 x軸為陣列，y軸為連結串列。 陣列儲存方式在記憶體地址是連續大小固定，一旦分配無法被其他引用佔用，查詢迅速，時間複雜度O(1)，插入刪除比較慢，時間複雜度為O(n)。 而連結串列儲存方式則與陣列相反，屬於非連續性，大小非固定，插入及刪除塊，查詢速度慢。 所以HashMap相對中庸。
1 HashMap的資料結構是啥？資料結構上儲存的資料物件結構是啥？ HashMap是一個儲存資料物件<封裝了K,V屬性的物件>的集合，而這個集合是陣列+連結串列型別的資料結構。
2 根據原始碼來分析hashMap內部的精髓 hash演算法如何保證雜湊均勻衝突的解決方式
談到hash 通常我們jdk的equals在比較的時候就會使用hash演算法，此演算法會定位到物件的儲存位置 具體hash的原理是： hash函式：找到儲存過程 被重寫的hashCode（key）
index=h=Hash(int hashCode)
(key.hashCode)&&length -1
length 2^n 通過h就可以找到陣列下標的位置
例子如下： 2^4=16 length-1 =15 二進位制為 01111 h返回的是 10101 陣列上儲存的位置為： 00101 【上下都是1才是1】
好處： 1 雜湊的範圍被低位限制---》雜湊位置一定在我們的索引範圍（即length-1）之內。 2 低位的0如果越多 代表我們雜湊的結果越固定。【想象一個若是非length-1就會發生 10000 低位0較多，導致雜湊結果幾乎就是一致】，導致衝突越多，導致陣列位置的利用率不高。
3 手寫一個自己的hashmap集合
首先我們會寫一個自己的介面 面向介面程式設計【介面內部只保留最基礎的put及get方法，然後定義內部介面】
然後就是寫自定義的hashMap來繼承此介面
定義引數並且補充了Spring門面模式的構造【即可以傳參，如果不傳參的話呼叫此類上面定義好的引數】
書寫put方法
其中注意的是擴容的方法及原理
獲取陣列下標的方法並且重寫hash演算法
定義內部類，重寫·Entry類
然後就是寫get方法
程式碼清單如下：
MyMap介面
package com.epoint.HashMap;
/**
* ，面向介面程式設計
*
* @author lulf
*
* @param <K>
* @param <V>
*/
public interface MyMap<K, V> {
// MyMap 基本功能是快速存
public V put(K k, V v);
// 快速取
public V get(K k);
// 定義一個內部的介面
public interface Entry<K, V> {
public K getKey();
public V getValue();
}
}`
myhashMap
`package com.epoint.HashMap;
import java.util.ArrayList;
import java.util.List;
public class MyHashMap<K, V> implements MyMap<K, V> {
// 定義陣列大小 16
// 結合著下面的擴容因子來解釋一波：假如陣列用了 4 usesize/defaulLenth =4/16=0.25 即使用率<0.75,不會擴容
private static int defaulLenth = 1 << 4;
// 擴容標準 所使用的useSize / 陣列長度 >0.75
// defaulAddSizeFactor 過大 造成擴容概率變低 儲存小 但是就是存與取的效率降低
// 0.9 有限的陣列長度空間位置內會形成連結串列 在存與取值中都必須進行大量的遍歷和判斷(邏輯)
// 過小 記憶體使用比較多，使用率不高，造成浪費
private static double defaulAddSizeFactor = 0.75;
// 使用陣列位置的總數
private int useSize;
// 定義Map 骨架 只要 陣列之一 陣列
private Entry<K, V>[] table = null;
// Spring 門面模式運用
public MyHashMap() {
this(defaulLenth, defaulAddSizeFactor);
}
public MyHashMap(int length, double defaulAddSizeFactor) {
if (length < 0)
throw new IllegalArgumentException("引數不能為負數" + length);
if (defaulAddSizeFactor <= 0 || Double.isNaN(defaulAddSizeFactor)) {
throw new IllegalArgumentException("擴容標準必須是大於0的數字" + defaulAddSizeFactor);
}
this.defaulLenth = length;
this.defaulAddSizeFactor = defaulAddSizeFactor;
table = new Entry[defaulLenth];
}
@Override
public V put(K k, V v) {
// 儲存是判斷是否需要擴容
if (useSize > defaulAddSizeFactor * defaulLenth) {
up2Size();
}
// 獲取陣列下標
int index = getIndex(k, table.length);
Entry<K, V> entry = table[index];
// 判斷這個entry是否為空，為空意味著未被雜湊到
if (entry == null) {
table[index] = new Entry(k, v, null);
useSize++;
} else if (entry != null) {
// 形成了連結串列結構
table[index] = new Entry(k, v, entry);
}
return table[index].getValue();
}
// 尋找陣列的下標
private int getIndex(K k, int length) {
int m = length - 1;
int index = hash(k.hashCode()) & m;
return index;
}
// 自定義寫自己的hash演算法
private int hash(int hashCode) {
hashCode = hashCode ^ ((hashCode >>> 20) ^ (hashCode >>> 12));
return hashCode ^ ((hashCode >>> 7) ^ (hashCode >>> 4));
}
// 擴容
private void up2Size() {
// 如何擴容，無非就是新建一個2倍空間的陣列
Entry<K, V>[] newTable = new Entry[2 * defaulLenth];
// 老陣列的內容拿到新陣列中
againHash(newTable);
}
// 將老陣列內容雜湊到新陣列中
private void againHash(MyHashMap<K, V>.Entry<K, V>[] newTable) {
List<Entry<K, V>> entryList = new ArrayList<MyHashMap<K, V>.Entry<K, V>>();
// for迴圈 即老陣列內容被全部遍歷到了entryList中
for (int i = 0; i < table.length; i++) {
if (table[i] == null) {
continue;
}
// 繼續找存到陣列上的entry物件
foundEntryByNext(table[i], entryList);
}
// 設定entryList
if (entryList.size() > 0) {
useSize = 0;
defaulLenth = 2 * defaulLenth;
for (Entry<K, V> entry : entryList) {
if (entry.next != null) {
entry.next = null;
}
put(entry.getKey(), entry.getValue());
}
}
}
private void foundEntryByNext(MyHashMap<K, V>.Entry<K, V> entry, List<MyHashMap<K, V>.Entry<K, V>> entryList) {
// 形成了連結串列結構
if (entry != null && entry.next != null) {
entryList.add(entry);
// 遞迴，不斷地一層層取存entry
foundEntryByNext(entry.next, entryList);
} else {
// 沒有連結串列的情況
entryList.add(entry);
}
}
public int getUseSize() {
return useSize;
}
@Override
public V get(K k) {
// hashCode (new Person(10,'llf'))--->hash---getindex--->最終位置
int index = getIndex(k, table.length);
if (table[index] == null) {
throw new NullPointerException();
}
return findByValueByEqualKey(k, table[index]);
}
private V findByValueByEqualKey(K k, MyHashMap<K, V>.Entry<K, V> entry) {
if (k == entry.getKey() || k.equals(entry.getKey())) {
return entry.getValue();
} else if (entry.next != null) {
return findByValueByEqualKey(k, entry.next);
}
return null;
}
// 建立一個內部儲存的物件型別
class Entry<K, V> implements MyMap.Entry<K, V> {
K k;
V v;
// 指向那被this擠壓轄區的Entry物件
Entry<K, V> next;
public Entry(K k, V v, Entry<K, V> next) {
this.k = k;
this.v = v;
this.next = next;
}
@Override
public K getKey() {
return k;
}
@Override
public V getValue() {
return v;
}
}
}
複製程式碼