?

在之前的博文中本屌已經介紹過java的Collection接口.

作為實現了Collection接口的容器中, List容器無疑是最常用的, 無論是Arraylist, Linklist, Vector 都不難理解.

我們已經知道List容器的特點就是其里面的元素是有序的, 而且允許放入重復的元素.

一, 實現Set接口的容器.

跟List接口一樣, Set接口也是繼承自Collection接口. ?
實現Set接口的容器可以與數學上的"集合" 概念相對應.
但是實現Set接口的容器的元素是沒有順序的, 而且不會存有多個重復的元素.

1.1 為何需要set容器

咋一看, 對比list容器, ?Set容器的兩個特點都是缺點啊.
例如Set容器里的元素沒有順序, 就導致Set容器沒有List容器的兩個很常用的方法, ?set(index) ?和 object get(index).
因為set() 方法和get()方法都需要1個序號(index)作為參數, 告訴List容器到底想存取哪1個對象.
但是Set()沒有index這東西(因為元素無序), 所以自然就沒有set(index) 和 get(index) 方法了.

那么Java中Set容器的意義何在呢?
答案很簡單, 因為現實中有一些東西很適合用Set容器來模擬.

例子1:
電視臺安排節目單, ? 節目單里的節目必須是有序的, 一個節目播完才到下1個, ?而且同1個節目可以出現在節目單多個不同的位置(重播).
那么電視節目單在coding中, 就應該用List容器來模擬了. ? ?
而且當節目單某1個節目被其他節目替換時, set(index)方法就發揮作用.?
當想獲得節目單某個特定位置的節目時, ?get(index)就適用了.

例子2:
但是顯示中也有一些容器是不需要次序, 而且不允許重復元素的, ?1個最簡單的例子就是足球教練選撥國家隊成員.
國家隊就像1個Set容器, ?里面的隊員沒必要按任何順序排列(元素無序), 而且國家隊也不允許同1個隊員占用兩個位置(不允許重復元素).

所以在生產中, 如果需要1個元素無序, 不允許重復的容器, ? 請選擇Set容器.

1.2 Set容器的常用方法.

Set接口繼承自Collection接口, ?并沒有提供額外的方法, 但是具有下列繼承自Collection接口的方法:
我們用回上面國家隊的例子解釋.

boolean add(Object o)
就如國家領隊選撥1個球員作為國家隊員, ?作為1個容器, add方法是必須具有的.

void clear()
相當于領隊遣散國家隊, 過一段時間重新選人.

boolean contains(object o)
判斷國家隊中是否包括某個球員, 也就是判斷1個球員是否國家隊員.. ?

boolean isEmtpy
判斷國家隊是否為空.

boolean?remove(Object o)

把1個隊員踢出國家隊, 前提是這個隊員本來就存在與國家隊中, 否則返回False

int size()
返回當前國家隊員的數量.

二, HashSet 簡介以及優點.

Java中是沒有Set這個容器的, Set只是1個接口.
Java有兩個常用的實現了Set接口的容器, 1個就是HashSet, 另1個是TreeSet. 本文Focus on HashSet.
HashSet 作為1種Set容器, 自然包含了上述提到的各種方法.
但是大家其實可以發現, ?Hashset容器的方法其實都可以在List容器找到替換的方法.
例如ArrayList 容器也有 contains(Object o), remove(Object o) 的方法.

也就是說, 在coding中, HashSet的方法完全可以用ArrayList來取代.?
但是HashSet自然有它的優點. 這個優點就是訪問數據的性能.

就比如同于同1個方法boolean contains(Object o), ?無論是ArrayList 還是 LinkList, 都是需要遍歷List的, 值到找到該元素為止.
而HashSet是基于Hashcode() 找到該元素的位置, 大大減少(非避免)遍歷的行為.

三, HashSet 的內存存儲結構.

3.1 Java 里 List的存儲結構.

我們知道, 無論是ArrayList, 還是 LinkList, 它們的元素都是一塊一塊存放地址的內存, 存放的地址再指向各個不同的對象.
如圖:




上面左邊的內存塊就是Java里的一段ArrayList的內存, 它存放了5個元素(對象地址), 指向了4個對象. ? 因為List中第2個地址和第4個地址都指向同1個對象object2, ?所以相當于object2在List存放了2次.

如果要判斷object4是否在List存在, 則很可能從List第1個位置向后逐個遍歷.
當然Collections類中提供了2分查找法的靜態方法, 但是前提是List中的元素必須排序, 而排序是比遍歷更耗成本的操作.

3.2 Java 里 HashSet的存放機制(add)

HashSet 里的存儲結構跟List的存儲結構完全不同.
假如一段Hashset中含有10個內存位置(并一定是連續的), ?而我要將1個對象object1 放入1個HashSet中.


如果要大概分成下面若干個步驟:

3.2.1 第一步: 根據object1的hashCode()方法獲得hashCode()的返回值, 經過算法后獲得object1在HashSet中的位置.

看下圖:
假如一段Hashset中含有10個內存位置(并一定是連續的), ?而我要把object1存放到HashSet中.






假如經過hashCode()的計算, 這個object1應該存入位置3中.

值得注意的是, 不同的hashCode值經過算法轉換后, 有可能得到同1個位置, 也就表明HashSet中位置3可能已經存在數據了!

3.2.2 第二步情況1: 假如Hashset中的位置3是空的

經過第1步, 根據hashCode()的轉換計算出位置是3. ? ?java并不會直接把object1的地址寫入位置3中.
首先會判斷位置3的內容是否為空.?
如果是空的話, 仍然不會直接將object1的地址寫入.
而是新建1個LinkList(鏈表), ?將object1的地址寫入到鏈表的第1個位置, 然后將鏈表的頭部地址寫入到位置3中.
如下圖:

3.2.2 第二步情況2: 假如Hashset中的位置3不是空的, 而是已經存在一條鏈表.

那么Java會逐個遍歷這條LinkList(所以說還是回遍歷), ?逐個利用equals()方法來跟要插入的object1比較.
1. 假如發現里面其中1個對象 object2.equals(object1) == 1. ?那么java就回認為object2 跟 object1是重復的元素. 不會將object1 放入HashSet容器中.







2. 假如遍歷Linklist所有元素后, 都沒發現重復的對象, 那么就將object1 放到該LinkList的尾部.

3.2 Java 里 HashSet的查找機制(例如 contains())

上面已經介紹過對象是怎樣存放入HashSet容器中的了.
那么如何查找1個對象是否在HashSet容器中存在呢?

無非也是分兩步.
1. 首先根據對象的hashCode 獲得 應該在HashSet的位置.
2. 遍歷HashSet中對應位置的鏈表, 如果存在1個對象o , 且o.equals(要放入的對象)是真(即使o是另1個對象), 則認為該對象在鏈表中存在.?

3.3 小結: Java 里 HashSet的本質

通過上面的分析, ?我們可以得出HashSet在內存中的存放本質.
參考下圖:





1., ?HashSet實際上存放的是多個子鏈表, 這些子鏈表的元素再指向各個對象.
2. ? HashSet 各個位置的子鏈表長度(對象個數)是差不多的, 因為Hash另1個名稱是"散列", 所謂散列就是分散均勻分布的意思. 這取決與HashCode的轉換算法.
3. ?HashSet 根據對象的hashCode()來決定對象在HashSet里的位置(哪一條鏈表), 但是不同hashCode值的對象可能存在同1個位置(鏈表)中.
4. HashSet 根據對象的equals()方法來判斷兩個對象是否重復, 也就是說兩個不同的對象只要ob1.equals(ob2) == True, HashSet 就回認為 ob1 與 ob2 重復.
5. HashSet查找1個對象, 只需要遍歷其中1個子鏈表, 而不需要遍歷整個容器, 所以如果存在大量無序數據. ?HashSet的訪問性能會比List容器高.

四, HashSet的對象必須同時重寫對象的hashCode 和 ?equals() 方法.

很多人都會get到這個建議: ?放入HashSet容器的對象, 最好重寫其hashCode() 和 equals()方法.
這里就詳細解釋重寫這兩個方法的原因.


下面是1個簡單例子:
import java.util.HashSet;class Student{private int id;private String name;public Student(int id, String name){this.id = id;this.name = name;}//overwritepublic String toString(){return this.id + ":" + this.name;} }public class Hashset1{public static void f(){HashSet hs = new HashSet();hs.add(1);hs.add(2);hs.add(1);hs.add(1);System.out.println(hs);hs.clear();hs.add(new Student(1,"Jack"));hs.add(new Student(2,"Bill"));hs.add(new Student(1,"Jack"));hs.add(new Student(1,"Jack"));System.out.println(hs);} }
上面簡單定義了1個class Student, 只有兩個成員id和name.
在下面的啟動方法f()中, 首先向1個HashSet容器hs放入4個int 元素(實際上被自動裝箱成Integer對象), ?然后輸出hs所有元素
接著清空容器, 放入4個Student對象. 其中3個對象的id和 name都是相同的(1, "Jack"), 再輸出這個元素.
輸出如下:
[java] [1, 2][java] [1:Jack, 1:Jack, 1:Jack, 2:Bill]
? ?可見, 第一次輸出1 和 2 符合了Set容器不放入重復元素的原則.
但是第次輸出, 輸出了3個 1: Jack ? ?... 符合了無序的原則, 但是貌似允許重復數據啊.
其實原因很簡單, 我們是用new Student()方法來構建1個對象的, 所以我們實際上放入了3個不同的對象, 即使3個對象的id和name屬性都一樣.
而java是根據這3個對象的hashCode()值來決定對象在HashSet的位置的.
而Student對象的hashCode()方法繼承自基類. ? ?返回1個跟內存地址有關的十六進制字符.
也就是說那3個1:Jack的對象因為內存地址不同, 返回的hashCode()不同, ?就很可能處于HashSet容器的不同子鏈表中.
如下圖:

4.1 重寫對象的hashCode()方法.

假如我們想避免這種id name相同的重復元素, 則必須做到:
?假如對象的id 和 name一樣, 則對象的hashCode() 必須相等.
所以我們可以重寫hashCode()方法:
令其返回 ? ?id * ?name.hashCode()

值得注意的是, Student類 的 name 成員是1個String對象, 而String對象是重寫過hashCode()的, 也就是說兩個不同String對象, 只要各各字符相同, 其hashCode()就一樣.
所以 id * name.hashCode() 能保證當id 和 name 一樣的話, Student的hashCode()就一樣.
注意: 并不能保證當兩個Student對象的id 和 name不一樣, 它們的hashCode也不一樣哦.

修改后的代碼如下:
import java.util.HashSet;class Student{private int id;private String name;public Student(int id, String name){this.id = id;this.name = name;}//overwritepublic String toString(){return this.id + ":" + this.name;}//overwrite hashCode()public int hashCode(){return id * name.hashCode();}}public class Hashset1{public static void f(){HashSet hs = new HashSet();hs.add(1);hs.add(2);hs.add(1);hs.add(1);System.out.println(hs);hs.clear();hs.add(new Student(1,"Jack"));hs.add(new Student(2,"Bill"));hs.add(new Student(1,"Jack"));hs.add(new Student(1,"Jack"));System.out.println(hs);} }
修改后的輸出: [java] [1, 2][java] [2:Bill, 1:Jack, 1:Jack, 1:Jack]
貌似問題還是沒解決啊.
其實根據本文3.2.2 小節就知道原因.
雖然這個三個 1 Jack的對象被分配到HashSet同1個位置中. ?HashSet 還是把這個3個對象放在同1個鏈表中了.
因為Student對象的equals()方法 也是繼承自基類Object的. ?是比較對象的內存地址...

所以HashSet容器會認為它們3個是不同的元素放在同1個鏈表中了, ?(hashCode()相同).

如下圖:

4.2 重寫對象的equals()方法.

所以除了hashCode() 之外, ?放入HashSet容器的類還應該重寫equals()方法.
重寫的邏輯也很簡單:
只要讓id 和 name相等的兩個對象相等就ok了.

修改后的代碼如下: import java.util.HashSet;class Student{private int id;private String name;public Student(int id, String name){this.id = id;this.name = name;}//overwritepublic String toString(){return this.id + ":" + this.name;}//overwrite hashCode()public int hashCode(){return id * name.hashCode();}//overwrite equals()public boolean equals(Object o){Student s = (Student)o;return (s.id == this.id) && (s.name.equals(this.name));}}public class Hashset1{public static void f(){HashSet hs = new HashSet();hs.add(1);hs.add(2);hs.add(1);hs.add(1);System.out.println(hs);hs.clear();hs.add(new Student(1,"Jack"));hs.add(new Student(2,"Bill"));hs.add(new Student(1,"Jack"));hs.add(new Student(1,"Jack"));System.out.println(hs);} }

這時的輸出: [java] [1, 2] [java] [2:Bill, 1:Jack]

符合我們的要求了.
終上所述, 這就是為什么說:
放入HashSet的對象最好同時重寫hashCode() 和 equals()方法了.

五, 小結:

從本質上將, HashSet將大量元素散列分為若干個子LinkList來存放數據, ?大大減少了遍歷的次數.
如果程序員需要1個容器來來存放大量無序的元素時, HashSet是1個很合適的選擇.

總結

以上是生活随笔為你收集整理的Java 容器之Hashset 详解.的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。