(1) 為啥要用HahSet?

????? 假如我們現(xiàn)在想要在一大堆數(shù)據(jù)中查找X數(shù)據(jù)。LinkedList的數(shù)據(jù)結(jié)構(gòu)就不說了，查找效率低的可怕。ArrayList哪，如果我們不知道X的位置序號(hào)，還是一樣要全部遍歷一次直到查到結(jié)果，效率一樣可怕。HashSet天生就是為了提高查找效率的。

?

(2) hashCode 散列碼

????? 散列碼是由對(duì)象導(dǎo)出的一個(gè)整數(shù)值。在Object中有一個(gè)hashCode方法來得到散列碼。基本上，每一個(gè)對(duì)象都有一個(gè)默認(rèn)的散列碼，其值就是對(duì)象的內(nèi)存地址。但也有一些對(duì)象的散列碼不同，比如String對(duì)象，它的散列碼是對(duì)內(nèi)容的計(jì)算結(jié)果：

    //String對(duì)象的散列碼計(jì)算
String str="hello";
int hash=0;
for(int i=0;i<length();i++)
    hash=31*hash+charAt(i);
  

????? 那么下面散列碼的結(jié)果不同也就好解釋了。s和t都還是String對(duì)象，散列碼由內(nèi)容獲得，結(jié)果一樣。sb和tb是StringBuffer對(duì)象，自身沒有hashCode方法，只能繼承Object的默認(rèn)方法，散列碼是對(duì)象地址，當(dāng)然不一樣了。

    String s=new String("OK");//散列碼: 3030
String t="Ok";  /散列碼: 3030
StringBuffer sb=new StringBuffer(s);  //散列碼：20526976
StringBuffer tb=new StringBuffer(t);  //散列碼：20527144
  

?

(3)? HashSet 散列表的內(nèi)部結(jié)構(gòu)

????? HashSet是個(gè)鏈表數(shù)組。每一個(gè)數(shù)組元素就是一個(gè)列表，我們稱為散列表元 。

????????? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ???????????????????

?

(4) HashSet 如何add機(jī)制

????? ? 假如我們有一個(gè)數(shù)據(jù)(散列碼76268)，而此時(shí)的HashSet有128個(gè)散列單元，那么這個(gè)數(shù)據(jù)將有可能插入到數(shù)組的第108個(gè)鏈表中(76268%128=108)。但這只是有可能，如果在第108號(hào)鏈表中發(fā)現(xiàn)有一個(gè)老數(shù)據(jù)與新數(shù)據(jù)equals()=true的話，這個(gè)新數(shù)據(jù)將被視為已經(jīng)加入，而不再重復(fù)丟入鏈表。

?????? 那么數(shù)據(jù)的散列碼我知道，但HashSet的散列單元大小如何指定那?

?????? Java默認(rèn)的散列單元大小全部都是2的冪，初始值為16（2的4次冪）。假如16條鏈表中的75%鏈接有數(shù)據(jù)的時(shí)候，則認(rèn)為加載因子達(dá)到默認(rèn)的0.75。HahSet開始重新散列，也就是將原來的散列結(jié)構(gòu)全部拋棄，重新開辟一個(gè)散列單元大小為32（2的5次冪）的散列結(jié)果，并重新計(jì)算各個(gè)數(shù)據(jù)的存儲(chǔ)位置。以此類推下去.....

?

(5) 為什么HashSet查找效率提高了。

????? 知道了HashSet的add機(jī)制后，查找的道理一樣。直接根據(jù)數(shù)據(jù)的散列碼和散列表的數(shù)組大小計(jì)算除余后，就得到了所在數(shù)組的位置，然后再查找鏈表中是否有這個(gè)數(shù)據(jù)即可。

????? 查找的代價(jià)也就是在鏈表中，但是真正一條鏈表中的數(shù)據(jù)很少，有的甚至沒有。幾乎沒有什么迭代的代價(jià)可言了。所以 散列表的查找效率建立在散列單元所指向的鏈表中的數(shù)據(jù)要少 。

?

(6) hashCode方法必須與equals方法必須兼容

????? 如果我們自己定義了一個(gè)類，想對(duì)這個(gè)類的大量對(duì)象組織成散列表結(jié)構(gòu)便于查找。有一點(diǎn)一定要注意：就是 hashCode方法必須與equals方法向兼容。

    //hashCode與equals方法的兼容
public class Employee{
       public int id;
       public String name="";
       //相同id對(duì)象具有相同散列碼
       public int hashCode(){ 
              return id;
       }
       //equals必須比較id
        public boolean equals(Employee x){
              if(this.id==x.id) return true;
              else return false;
       }
}
  

? ? ? ?? 為什么要這樣，因?yàn)镠ashSet不允許相同元素(equals==ture)同時(shí)存在在結(jié)構(gòu)中。假如employeeX(1111，“張三”)和employee(1111,"李四")，而Employee.equals比較的是name。這樣的話，employeeX和employeeY的equals不相等。它們會(huì)根據(jù)相同的散列碼1111加入到同一個(gè)散列單元所指向的列表中。這種情況多了，鏈表的數(shù)據(jù)將很龐大，散列沖突將非常嚴(yán)重，查找效率會(huì)大幅度的降低。

?

(6) 總結(jié)一下

????? 1、 HashSet不能重復(fù)存儲(chǔ)equals相同的數(shù)據(jù) 。原因就是equals相同，數(shù)據(jù)的散列碼也就相同（hashCode必須和equals兼容）。大量相同的數(shù)據(jù)將存放在同一個(gè)散列單元所指向的鏈表中，造成嚴(yán)重的散列沖突，對(duì)查找效率是災(zāi)難性的。

????? 2、 HashSet的存儲(chǔ)是無序的 ，沒有前后關(guān)系，他并不是線性結(jié)構(gòu)的集合。

????? 3、 hashCode必須和equals必須兼容， 這也是為了第1點(diǎn)。

?

Java集合類(4) —— 介紹HashSet