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