(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點。

?

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