(1) 為啥要用HahSet?
????? 假如我們現在想要在一大堆數據中查找X數據。LinkedList的數據結構就不說了,查找效率低的可怕。ArrayList哪,如果我們不知道X的位置序號,還是一樣要全部遍歷一次直到查到結果,效率一樣可怕。HashSet天生就是為了提高查找效率的。
?
(2) hashCode 散列碼
????? 散列碼是由對象導出的一個整數值。在Object中有一個hashCode方法來得到散列碼。基本上,每一個對象都有一個默認的散列碼,其值就是對象的內存地址。但也有一些對象的散列碼不同,比如String對象,它的散列碼是對內容的計算結果:
//String對象的散列碼計算 String str="hello"; int hash=0; for(int i=0;i<length();i++) hash=31*hash+charAt(i);
????? 那么下面散列碼的結果不同也就好解釋了。s和t都還是String對象,散列碼由內容獲得,結果一樣。sb和tb是StringBuffer對象,自身沒有hashCode方法,只能繼承Object的默認方法,散列碼是對象地址,當然不一樣了。
String s=new String("OK");//散列碼: 3030 String t="Ok"; /散列碼: 3030 StringBuffer sb=new StringBuffer(s); //散列碼:20526976 StringBuffer tb=new StringBuffer(t); //散列碼:20527144
?
(3)? HashSet 散列表的內部結構
????? HashSet是個鏈表數組。每一個數組元素就是一個列表,我們稱為散列表元 。
????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
???????????????????
?
(4) HashSet 如何add機制
????? ? 假如我們有一個數據(散列碼76268),而此時的HashSet有128個散列單元,那么這個數據將有可能插入到數組的第108個鏈表中(76268%128=108)。但這只是有可能,如果在第108號鏈表中發現有一個老數據與新數據equals()=true的話,這個新數據將被視為已經加入,而不再重復丟入鏈表。
?????? 那么數據的散列碼我知道,但HashSet的散列單元大小如何指定那?
?????? Java默認的散列單元大小全部都是2的冪,初始值為16(2的4次冪)。假如16條鏈表中的75%鏈接有數據的時候,則認為加載因子達到默認的0.75。HahSet開始重新散列,也就是將原來的散列結構全部拋棄,重新開辟一個散列單元大小為32(2的5次冪)的散列結果,并重新計算各個數據的存儲位置。以此類推下去.....
?
(5) 為什么HashSet查找效率提高了。
????? 知道了HashSet的add機制后,查找的道理一樣。直接根據數據的散列碼和散列表的數組大小計算除余后,就得到了所在數組的位置,然后再查找鏈表中是否有這個數據即可。
????? 查找的代價也就是在鏈表中,但是真正一條鏈表中的數據很少,有的甚至沒有。幾乎沒有什么迭代的代價可言了。所以 散列表的查找效率建立在散列單元所指向的鏈表中的數據要少 。
?
(6) hashCode方法必須與equals方法必須兼容
????? 如果我們自己定義了一個類,想對這個類的大量對象組織成散列表結構便于查找。有一點一定要注意:就是 hashCode方法必須與equals方法向兼容。
//hashCode與equals方法的兼容 public class Employee{ public int id; public String name=""; //相同id對象具有相同散列碼 public int hashCode(){ return id; } //equals必須比較id public boolean equals(Employee x){ if(this.id==x.id) return true; else return false; } }
? ? ? ?? 為什么要這樣,因為HashSet不允許相同元素(equals==ture)同時存在在結構中。假如employeeX(1111,“張三”)和employee(1111,"李四"),而Employee.equals比較的是name。這樣的話,employeeX和employeeY的equals不相等。它們會根據相同的散列碼1111加入到同一個散列單元所指向的列表中。這種情況多了,鏈表的數據將很龐大,散列沖突將非常嚴重,查找效率會大幅度的降低。
?
(6) 總結一下
????? 1、 HashSet不能重復存儲equals相同的數據 。原因就是equals相同,數據的散列碼也就相同(hashCode必須和equals兼容)。大量相同的數據將存放在同一個散列單元所指向的鏈表中,造成嚴重的散列沖突,對查找效率是災難性的。
????? 2、 HashSet的存儲是無序的 ,沒有前后關系,他并不是線性結構的集合。
????? 3、 hashCode必須和equals必須兼容, 這也是為了第1點。
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
