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