什么是HashMap
這一節(jié)課，我們來手寫一個簡單的HashMap，所謂HashMap，就是一個映射表。
比如現(xiàn)在我有一個客戶類，就用之前的就好。
現(xiàn)在我有100個客戶，名字各不相同，有叫張三的，也有叫李四的，還有的人叫張全蛋。如果現(xiàn)在要你從這100個人中找到一個叫做王尼瑪?shù)娜耍阍趺崔k？
這好像很簡單，我們不是剛剛做了一個TuziLinkedList嗎？一個個add進(jìn)去，數(shù)據(jù)初始化，然后再用foreach去遍歷不就行了？可是，這樣的效率是很低的，假如王尼瑪正好在鏈表的最后一個，那就需要遍歷100次才能找到。復(fù)雜度是o（n）
這個時候，要是有一種辦法能讓我們一下子就通過name，去找到王尼瑪這個人就好了。
其實這個辦法是有的，就是查表法，我們需要的就是這樣的一個映射表。
映射表分為key和value，在這個例子中，key就是name字段。這樣一來，復(fù)雜度就是o（1），只需要遍歷一次就可以了。
簡單來說，不管有多少個數(shù)據(jù)，如果你用關(guān)系映射表Map，只需要一次，你就直接通過某一個key，拿到了對應(yīng)的Customer對象。
為什么這么神奇呢？
那是因為，Map的底層是一個數(shù)組。
什么是數(shù)組？
數(shù)組的知識比較基礎(chǔ)，網(wǎng)上已經(jīng)被講爛了，直接參考菜鳥教程即可：
https://www.runoob.com/java/java-array.html
因為數(shù)組是直接用數(shù)字下標(biāo)去獲取對應(yīng)的值的，復(fù)雜度是最低的，所以Map的查詢才會這么快。
我們要做的一種映射關(guān)系表，寫法大概是這樣的。
public class TestMap {
public static void main(String[] args) {
Map csts = new HashMap<>();
csts.put("王大錘",new Customer("王大錘"));
csts.put("王尼瑪",new Customer("王尼瑪"));
csts.put("趙鐵柱",new Customer("趙鐵柱"));
//直接根據(jù)name拿到對應(yīng)的實體對象
Customer customer = (Customer) csts.get("王大錘");
System.out.println(customer.getName());
}
}
這是java自帶的HashMap，我們就需要實現(xiàn)類似的功能。
HashCode和數(shù)組
先考慮第一個問題，既然HashMap底層是用數(shù)組，可是key不一定是數(shù)字，那么就得想辦法把key轉(zhuǎn)化為一個數(shù)字。
HashCode就是一種hash碼值，任何一個字符串，對象都有自己的Hash碼，計算方式如下：
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
使用 int 算法，這里 s[i] 是字符串的第 i 個字符，n 是字符串的長度，^ 表示求冪。空字符串的哈希值為 0。
比如字符串是“abc”, 套用公式計算如下：
String a = "abc"; // 97 * 31^(3-1) + 98 * 31^(3-2) + 99 ^ (3-3) //= 93217 + 3038 + 99 = 96354 System.out.println(a.hashCode());
答案正是：
我們99%的情況，HashMap的key就是String，所以都可以用這個公式去計算。HashCode算法的牛逼之處在于，任何字符串都可以對應(yīng)唯一的一個數(shù)字。
相信你肯定有一個疑惑，就是為啥Hash算法用的是31的冪等運算？
在名著 《Effective Java》第 42 頁就有對 hashCode 為什么采用 31 做了說明：
之所以使用 31， 是因為他是一個奇素數(shù)。如果乘數(shù)是偶數(shù)，并且乘法溢出的話，信息就會丟失，因為與2相乘等價于移位運算（低位補0）。使用素數(shù)的好處并不很明顯，但是習(xí)慣上使用素數(shù)來計算散列結(jié)果。 31 有個很好的性能，即用移位和減法來代替乘法，可以得到更好的性能： 31 * i == (i << 5） - i， 現(xiàn)代的 VM 可以自動完成這種優(yōu)化。這個公式可以很簡單的推導(dǎo)出來。
反正大概意思就是一些數(shù)學(xué)家發(fā)現(xiàn)，用31計算hash值的話，性能是最好的。畢竟你也不希望算個HashCode花太多時間吧。
一開始，我們不需要做的太完美，剛開始的時候，完成永遠(yuǎn)優(yōu)于完美。
public class TuziHashMap {
private Object arr[];
private int capacity = 20; //初始化容量
public TuziHashMap(){
arr = new Object[capacity];
}
}
TuziHashMap內(nèi)部維護(hù)了一個數(shù)組，初識容量為20。接下來，實現(xiàn)put方法，put方法就是給這個Map添加新的元素。
public Object put(String key,Object value){
//1. 算出HashCode
int hashCode = key.hashCode();
//2. 直接取模，得到余數(shù)，這個余數(shù)就是數(shù)組的下標(biāo)
int index = hashCode % capacity;
//3. 將對應(yīng)的數(shù)據(jù)放入數(shù)組的對應(yīng)格子
this.arr[index] = value;
return value;
}
然后是get方法，接收對應(yīng)的key值，返回對應(yīng)的元素。
public Object get(String key){
//1. 算出HashCode
int hashCode = key.hashCode();
//2. 直接取模，得到余數(shù)，這個余數(shù)就是數(shù)組的下標(biāo)
int index = hashCode % capacity;
//3. 將對應(yīng)的數(shù)據(jù)放入數(shù)組的對應(yīng)格子
return this.arr[index];
}
代碼非常相似，先別管優(yōu)不優(yōu)化，實現(xiàn)功能再說，這就是踏出的第一步。
TuziHashMap map = new TuziHashMap();
map.put("王大錘",new Customer("王大錘"));
System.out.println(map.get("王大錘"));
效果：
Hash碰撞
Hash碰撞也叫做Hash沖突，就是當(dāng)兩個key算出來HashCode相同的情況下，就會產(chǎn)生沖突。
目前我們的Map類中，底層的數(shù)組長度默認(rèn)值20（真正的HashMap默認(rèn)值是16），當(dāng)存入的數(shù)據(jù)足夠多并且不進(jìn)行擴容的話，Hash碰撞是必然的。所謂Hash碰撞，就是比如說兩個key明明是不同的，但是經(jīng)過hash算法后，hash值竟然是相同的。那么另一個key的value就會覆蓋之前的，從而引起錯誤。
添加專門的hash方法，然后先寫死hashcode為10，那就一定會發(fā)生hash碰撞！
private int hash(String key){
//return key.hashCode();
return 10;
}
get方法也要改過來，用hash方法：
public Object get(String key){
//1. 算出HashCode
int hashCode = hash(key);
//2. 直接取模，得到余數(shù)，這個余數(shù)就是數(shù)組的下標(biāo)
int index = hashCode % capacity;
//3. 將對應(yīng)的數(shù)據(jù)放入數(shù)組的對應(yīng)格子
return this.arr[index];
}
TuziHashMap map = new TuziHashMap();
map.put("王大錘",new Customer("王大錘"));
map.put("王尼瑪",new Customer("王尼瑪"));
System.out.println(map.get("王大錘"));
結(jié)果：
Customer{name=‘王尼瑪", sex=‘null", birthDate=‘null", phoneNumber=‘null", status=0}
原因：產(chǎn)生了Hash碰撞，后面的王尼瑪直接把王大錘給覆蓋了。
怎么解決Hash碰撞呢？因為Hash碰撞在實際應(yīng)用中肯定會出現(xiàn)，所以，我們就不能在數(shù)組的每一個格子中直接存Object對象，而應(yīng)該弄一個鏈表。
假如出現(xiàn)Hash碰撞，就直接在鏈表中加一個節(jié)點。然后，下次取元素的時候，如果遇到Hash碰撞的情況就去循環(huán)那個鏈表，從而解決了Hash沖突的問題。
有了基本的思路，我們就得去修改put方法。
put方法接收一個key，一個value。如果發(fā)生Hash沖突，就得把新的key和value加到鏈表的末尾。
初步代碼如下：
但是，這樣有個問題，你沒法取。為什么沒法取呢？因為，鏈表上的每一個節(jié)點，我們只保存了value，沒有key。那么相同的key的情況，怎么去獲取對應(yīng)的元素呢？比如兩個key，分別是“王大錘”和“王尼瑪”，假如他們的HashCode是相同的，因為鏈表上沒有保存“王大錘”和“王尼瑪”兩個key，我們就沒法區(qū)分了。
沒有辦法，只好修改一下之前的Node。為什么之前沒有加key呢？因為之前的Node類是為LinkedList服務(wù)的，LinkedList不需要key這個東西。
在linkedList中，原來的add方法是不需要key的，所以也需要做一個修改：
/**
* 原來的add方法保留，調(diào)用重載的add方法
* @param object
* @return
*/
public boolean add(Object object){
return add(null,object);
}
/**
* 新增的add方法,增加參數(shù)key
*/
public boolean add(Object key,Object object){
//將數(shù)據(jù)用節(jié)點類包裝好，這樣才能實現(xiàn)下一個數(shù)據(jù)的指向
Node data = new Node(object);
if(key != null){
data.key = key;
}
//先判斷是否是第一個節(jié)點
if(this.firstNode == null){
this.firstNode = data;
this.currentNode = data;
}else{
//不是第一個節(jié)點，就指向當(dāng)前節(jié)點的下一個節(jié)點，即currentNode.next
this.currentNode.next = data;
//因為已經(jīng)指向下一個了，所以當(dāng)前節(jié)點也要移動過來
this.currentNode = data;
}
size++;
return true;
}
如果你讀過jdk里面的源碼，就一定會知道，在很多Java基礎(chǔ)類中，都有一大堆的構(gòu)造方法，一大堆方法重載。而且，很多方法里面都會調(diào)用同名的方法，只不過參數(shù)傳的不一樣罷了。
我之前也一直不理解，為什么要整的這么麻煩，后來當(dāng)自己嘗試寫一些數(shù)據(jù)結(jié)構(gòu)的時候，才明白，不這樣搞真的不行。方法重載的意義不是去秀肌肉的，而是減少代碼的工作量。
比如，因為LinkedList需要增加key的保存，原來的add方法是沒有的。我們不太好直接修改原來的add方法，因為萬一這個類被很多調(diào)用了，那么很多地方都會受到不同程度的影響。所以，類的設(shè)計思路有一條很重要，那就是：
做增量好過做修改。
還是原來的測試代碼：
TuziHashMap map = new TuziHashMap();
map.put("王大錘",new Customer("王大錘"));
map.put("王尼瑪",new Customer("王尼瑪"));
System.out.println(map.get("王大錘"));
因為我們修改了hash方法，強行導(dǎo)致Hash碰撞，所以目前是肯定沖突的。
運行：
Customer{name=‘王大錘", sex=‘null", birthDate=‘null", phoneNumber=‘null", status=0}
成功了，王尼瑪沒有覆蓋掉王大錘。
toString方法
為了更好的調(diào)試，我們給TuziHashMap添加toString方法
public String toString(){
StringBuffer sb = new StringBuffer("[
");
for (int i = 0; i < arr.length; i++) {
LinkedList list = arr[i];
if(list != null){
while(list.hasNext()){
Node node = list.nextNode();
sb.append(String.format(" {%s=%s}",node.key,node.data));
if(list.hasNext())
sb.append(",
");
else
sb.append("
");
}
}
}
sb.append("]");
return sb.toString();
}
運行之前的測試代碼，就是這樣的：
百萬級數(shù)據(jù)壓測
做一點性能測試，又有新的問題了。。。
步驟 1 來100w條數(shù)據(jù)，看看要花多久？
long startTime = System.currentTimeMillis(); //獲取開始時間
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 100000; i++) {
map.put("key" + i, "value--" + i);
}
System.out.println(map);
long overTime = System.currentTimeMillis(); //獲取結(jié)束時間
System.out.println("程序運行時間為："+(overTime-startTime)+"毫秒");
上面的代碼就是循環(huán)10w次，然后用一個toString全部打印出來，看看需要多久吧？
大概是800毫秒左右。
可如果是100w呢？
直接報錯了，原因是JVM內(nèi)存溢出。這是為什么呢？
那是因為，我們的Map初識容量是20,100w條數(shù)據(jù)插進(jìn)去，想也知道鏈表是扛不住了。
步驟 2 設(shè)計思路
1.初始化數(shù)組
2.每次put的時候，就計算是不是快溢出來了，如果是，數(shù)組翻倍。
3.由于數(shù)組容量翻倍了，原來的數(shù)據(jù)需要重新計算hash值，散列到新的數(shù)組中去。（不這樣做的話，數(shù)組利用率會不夠，很多數(shù)據(jù)全部擠在前半段）
步驟 3 添加一個size
現(xiàn)在的數(shù)組長度是20，最理想的情況，添加20個元素，一次Hash碰撞都沒有，均勻分布在20個格子里面。當(dāng)添加第21個的時候，一定會發(fā)生Hash碰撞，這個時候我們就需要去擴容數(shù)組了。
步驟 4 先設(shè)計，后實現(xiàn)
因為代碼寫到這里，已經(jīng)開始慢慢變得復(fù)雜了。我們可以參考之前接口的章節(jié)，先設(shè)計，再談如何實現(xiàn)。只要設(shè)計是合理了，就別擔(dān)心能不能實現(xiàn)的問題。如果你一開始就陷入到各種細(xì)節(jié)里面，那你就很難更進(jìn)一步。
利用DIEA的自動提示功能，生成擴容方法。
步驟 5 擴容方法
private void enlarge() {
capacity *= 2; // 等同于 capacity = capacity * 2 ，這么寫只是因為我想裝個逼。
LinkedList[] newArr = new LinkedList[capacity];
System.out.println("數(shù)組擴容到" + capacity);
int len = arr.length; //把arr的長度寫在外面，這樣能減少一丟丟的計算
for (int i = 0; i < len; i++) {
LinkedList linkedList = arr[i];
if(arr[i] != null){
while(linkedList.hasNext()){
Node node = linkedList.nextNode();
Object key = node.key;
Object value = node.data;
//將原有的數(shù)據(jù)一個個塞到新的數(shù)組
reHash(newArr,key,value);
}
}
}
//新數(shù)組正式上位
this.arr = newArr;
}
每個數(shù)組元素都是一個鏈表，這個鏈表里面每一個數(shù)據(jù)都應(yīng)該要遍歷到，需要再寫一個reHash方法，重新計算Hash值。
步驟 6 reHash方法
private void reHash(LinkedList[] newArr, Object key, Object value) {
//1. 算出HashCode
int hashCode = hash(key.toString());
//2. 直接取模，得到余數(shù)，這個余數(shù)就是數(shù)組的下標(biāo)
int index = hashCode % capacity ;
//3. 將對應(yīng)的數(shù)據(jù)放入數(shù)組的對應(yīng)格子
if(newArr[index] == null){
newArr[index] = new LinkedList();
}
newArr[index].add(key,value);
}
和put方法差不多，只是多了一個參數(shù)，如果是JDK的套路，肯定又得做函數(shù)重載了吧。不過現(xiàn)在趕進(jìn)度，就不做優(yōu)化了。
步驟 7 新的問題出現(xiàn)
做個測試，我們來個26條數(shù)據(jù)，肯定會觸發(fā)擴容的。
long startTime = System.currentTimeMillis(); //獲取開始時間
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 260; i++) {
map.put("key" + i, "value--" + i);
}
System.out.println(map);
long overTime = System.currentTimeMillis(); //獲取結(jié)束時間
System.out.println("程序運行時間為："+(overTime-startTime)+"毫秒");
天啊，竟然報錯了！
從錯誤信息看，index是-142，也就是說hashCode是負(fù)數(shù)。
hashCode怎么會是負(fù)數(shù)呢？
答案是：hashCode肯定有可能是負(fù)數(shù)。因為HashCode是int類型
int型的值取值范圍為
Integer.MIN_VALUE(-2147483648)～I(xiàn)nteger.MAX_VALUE(2147483647)
那怎么修改呢？可以想到取絕對值，其實還有一個更酷的方法，就是用與邏輯。
為了防止漏改，我們把取模的運算抽出來做成方法。
老規(guī)矩，先把方法寫出來，做設(shè)計。待會再去寫實現(xiàn)。
步驟 8 indexForTable方法
private int indexForTable(int hashCode) {
return hashCode & Integer.MAX_VALUE % capacity;
}
這樣的做法就是確保不會出現(xiàn)負(fù)數(shù)，效率還高。如果你問為什么，那就是計算機里面存的int，其實是有符號的。如果是負(fù)數(shù)，第一位也就是符號位就是1，而Integer.MAX_VALUE是正數(shù)。
0x是表示16進(jìn)制的前綴。
第一個7是16進(jìn)制的7，換算成2進(jìn)制，就是好多個1，如果算出來的hashCode是負(fù)數(shù)，那么第一個就是1，和0進(jìn)行&操作，就會變成0，于是就變成正數(shù)了。
假如我們的hashCode是10，換算成二進(jìn)制就是1010。你可以用1248法快速口算。
那么，進(jìn)行&運算：
可見，這個操作其實就是取絕對值，但是效率更高。
步驟 9 重新轉(zhuǎn)測
所有用到取模運算的地方，都改成indexForTable方法，代碼我就不貼了。
重新測試，就發(fā)現(xiàn)不報錯了。
步驟 10 再次測試100w數(shù)據(jù)
其實站長剛才測試的時候又報內(nèi)存溢出了，想著估計是System.out.print語句太多了。（可能之前也是這個原因，哈哈）
于是，我修改了一下測試代碼：
long startTime = System.currentTimeMillis(); //獲取開始時間
TuziHashMap map = new TuziHashMap();
for (int i = 0; i < 100 * 10000; i++) {
map.put("key" + i, "value--" + i);
}
System.out.println(map.get("key" + 99999));
long overTime = System.currentTimeMillis(); //獲取結(jié)束時間
System.out.println("程序運行時間為："+(overTime-startTime)+"毫秒");
只花了2秒多，這可是100w條數(shù)據(jù)啊，可見HashMap的性能還是很客觀的。
步驟 11 PK 原生JDK8的HashMap
long startTime = System.currentTimeMillis(); //獲取開始時間
HashMap map = new HashMap();
for (int i = 0; i < 100 * 10000; i++) {
map.put("key" + i, "value--" + i);
}
System.out.println(map.get("key" + 99999));
long overTime = System.currentTimeMillis(); //獲取結(jié)束時間
System.out.println("程序運行時間為："+(overTime-startTime)+"毫秒");
100w數(shù)據(jù)的情況下，時間測下來是差不多的。不過即便如此，我們也不要太較真，因為jdk8的HashMap肯定寫的比我們的好，完善。就比如我們在數(shù)組的每個節(jié)點放的是鏈表，而jdk8開始，則是鏈表+紅黑樹的結(jié)構(gòu)，當(dāng)Hash沖突很多的情況下，會自動轉(zhuǎn)換為紅黑樹，效率會更加高一點。
補丁
目前的HashMap還只是實現(xiàn)了最最基本的功能，好多方法都還未實現(xiàn)，比如remove方法。
步驟 1 put元素的bug
其實put方法是有一個bug的，不知道你發(fā)現(xiàn)了沒有？
原生的HashMap，當(dāng)put相同key的時候，是直接覆蓋的，而目前的情況是直接追加到鏈表了。這就會導(dǎo)致我們執(zhí)行
map.get("a")
得到的就是A，而不是AA，AA是永遠(yuǎn)拿不到了。
這個作為課后作業(yè)，歡迎進(jìn)群一起學(xué)習(xí)交流哦。
步驟 2 HashMap為什么是無序的？
Java面試題中經(jīng)常會遇到這個問題，HashMap為什么是無序的？
現(xiàn)在我們自己寫了一個HashMap，相信你肯定知道原因了吧？key在進(jìn)行hash算法的時候，誰知道會匹配到哪一個數(shù)組下標(biāo)呢？所以，肯定是無序的。
步驟 3 作業(yè)1答案
public Object put(String key,Object value){
if(size > capacity){
enlarge();
}
//1. 算出HashCode
int hashCode = hash(key);
//2. 直接取模，得到余數(shù)，這個余數(shù)就是數(shù)組的下標(biāo)
int index = indexForTable(hashCode);
//3. 將對應(yīng)的數(shù)據(jù)放入數(shù)組的對應(yīng)格子
if(this.arr[index] == null){
this.arr[index] = new LinkedList();
}
LinkedList linkedList = this.arr[index];
if(linkedList.size() == 0){
linkedList.add(key,value);
}
//遍歷這個node的鏈表，如果發(fā)現(xiàn)重復(fù)key，直接覆蓋
Node firstNode = linkedList.firstNode;
Node node = firstNode;
while(node != null){
if(node.key.equals(key)){
node.data = value;
}
node = node.next;
}
this.size++;
return value;
}
以上就是java編程進(jìn)階小白也能手寫HashMap的詳細(xì)內(nèi)容，更多關(guān)于手寫HashMap的資料請關(guān)注服務(wù)器之家其它相關(guān)文章！
原文鏈接：https://blog.csdn.net/weixin_39570751/article/details/120519747
