Java集合----HashSet的實(shí)現(xiàn)原理

賈朋亮博客 2015-05-13

展開(kāi)全文

1. HashSet概述

HashSet實(shí)現(xiàn)Set接口，由哈希表（實(shí)際上是一個(gè)HashMap實(shí)例）支持,。它不保證set 的迭代順序,；特別是它不保證該順序恒久不變,。此類(lèi)允許使用null元素,。

2. HashSet的實(shí)現(xiàn)

     如果不等，則添加到該數(shù)組索引對(duì)應(yīng)的鏈表中,。

------------------------------------------------------------------------------------------

     Set的實(shí)現(xiàn)類(lèi)的集合對(duì)象中不能夠有重復(fù)元素,，HashSet也一樣他是使用了一種標(biāo)識(shí)來(lái)確定元素的不重復(fù)，HashSet用一種算法來(lái)保證 HashSet中的元素是不重復(fù)的,，   HashSet采用哈希算法,，底層用數(shù)組存儲(chǔ)數(shù)據(jù)。默認(rèn)初始化容量16,，加載因子0.75

     Object類(lèi)中的hashCode()的方法是所有子類(lèi)都會(huì)繼承這個(gè)方法,，這個(gè)方法會(huì)用Hash算法算出一個(gè)Hash（哈希）碼值返回，HashSet 會(huì)用Hash碼值去和數(shù)組長(zhǎng)度取模,，模（這個(gè)模就是對(duì)象要存放在數(shù)組中的位置）相同時(shí)才會(huì)判斷數(shù)組中的元素和要加入的對(duì)象的內(nèi)容是否相同,，如果不同才會(huì)添加進(jìn)去。

     Hash算法是一種散列算法,。

Set hs=new HashSet();

hs.add(o);
     |
         o.hashCode();
     |
o%當(dāng)前總?cè)萘?nbsp; (0--15)
     |
     |                 不發(fā)生沖突
        是否發(fā)生沖突-----------------直接存放
     |
     | 發(fā)生沖突
     |                  假（不相等）
        o1.equals(o2)-------------------找一個(gè)空位添加
     |
     | 是（相等）
         不添加

       覆蓋hashCode()方法的原則：
       1,、一定要讓那些我們認(rèn)為相同的對(duì)象返回相同的hashCode值
       2、盡量讓那些我們認(rèn)為不同的對(duì)象返回不同的hashCode值,，否則,，就會(huì)增加沖突的概率。
       3,、盡量的讓hashCode值散列開(kāi)（兩值用異或運(yùn)算可使結(jié)果的范圍更廣）

HashSet 的實(shí)現(xiàn)比較簡(jiǎn)單,，相關(guān)HashSet的操作，基本上都是直接調(diào)用底層HashMap的相關(guān)方法來(lái)完成,，我們應(yīng)該為保存到HashSet中的對(duì)象覆蓋 hashCode()和equals(),，因?yàn)樵賹?duì)象加入到HashSet中時(shí)，會(huì)首先調(diào)用hashCode方法計(jì)算出對(duì)象的hash值,，接著根據(jù)此 hash值調(diào)用HashMap中的hash方法，得到的值& (length-1)得到該對(duì)象在hashMap的transient Entry[] table中的保存位置的索引,，接著找到數(shù)組中該索引位置保存的對(duì)象,，并調(diào)用equals方法比較這兩個(gè)對(duì)象是否相等，如果相等則不添加,，注意：所以要存入HashSet的集合對(duì)象中的自定義類(lèi)必須覆蓋hashCode(),equals()兩個(gè)方法,，才能保證集合中元素不重復(fù),。在覆蓋equals()和 hashCode()方法時(shí)，要使相同對(duì)象的hashCode()方法返回相同值,，覆蓋equals()方法再判斷其內(nèi)容,。為了保證效率，所以在覆蓋hashCode()方法時(shí),，也要盡量使不同對(duì)象盡量返回不同的Hash碼值,。

如果數(shù)組中的元素和要加入的對(duì)象的hashCode()返回了相同的Hash值（相同對(duì)象）,才會(huì)用equals()方法來(lái)判斷兩個(gè)對(duì)象的內(nèi)容是否相同。

------------------------------------------------------------------------------------------

HashSet的源代碼如下：

[java] view plain copy

public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
// 底層使用HashMap來(lái)保存HashSet中所有元素,。
private transient HashMap<E,Object> map;
// 定義一個(gè)虛擬的Object對(duì)象作為HashMap的value,，將此對(duì)象定義為static final。
private static final Object PRESENT = new Object();
/**
* 默認(rèn)的無(wú)參構(gòu)造器,，構(gòu)造一個(gè)空的HashSet,。
*
* 實(shí)際底層會(huì)初始化一個(gè)空的HashMap，并使用默認(rèn)初始容量為16和加載因子0.75,。
*/
public HashSet() {
map = new HashMap<E,Object>();
}
/**
* 構(gòu)造一個(gè)包含指定collection中的元素的新set,。
*
* 實(shí)際底層使用默認(rèn)的加載因子0.75和足以包含指定
* collection中所有元素的初始容量來(lái)創(chuàng)建一個(gè)HashMap。
* @param c 其中的元素將存放在此set中的collection,。
*/
public HashSet(Collection<? extends E> c) {
map = new HashMap<E,Object>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
/**
* 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)空的HashSet,。
*
* 實(shí)際底層以相應(yīng)的參數(shù)構(gòu)造一個(gè)空的HashMap。
* @param initialCapacity 初始容量,。
* @param loadFactor 加載因子,。
*/
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 以指定的initialCapacity構(gòu)造一個(gè)空的HashSet。
*
* 實(shí)際底層以相應(yīng)的參數(shù)及加載因子loadFactor為0.75構(gòu)造一個(gè)空的HashMap,。
* @param initialCapacity 初始容量,。
*/
public HashSet(int initialCapacity) {
map = new HashMap<E,Object>(initialCapacity);
}
/**
* 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)新的空鏈接哈希集合。
* 此構(gòu)造函數(shù)為包訪問(wèn)權(quán)限,，不對(duì)外公開(kāi),，實(shí)際只是是對(duì)LinkedHashSet的支持。
*
* 實(shí)際底層會(huì)以指定的參數(shù)構(gòu)造一個(gè)空LinkedHashMap實(shí)例來(lái)實(shí)現(xiàn),。
* @param initialCapacity 初始容量,。
* @param loadFactor 加載因子。
* @param dummy 標(biāo)記,。
*/
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor);
}
/**
* 返回對(duì)此set中元素進(jìn)行迭代的迭代器,。返回元素的順序并不是特定的。
*
* 底層實(shí)際調(diào)用底層HashMap的keySet來(lái)返回所有的key,。
* 可見(jiàn)HashSet中的元素,，只是存放在了底層HashMap的key上，
* value使用一個(gè)static final的Object對(duì)象標(biāo)識(shí),。
* @return 對(duì)此set中元素進(jìn)行迭代的Iterator,。
*/
public Iterator<E> iterator() {
return map.keySet().iterator();
}
/**
* 返回此set中的元素的數(shù)量（set的容量）,。
*
* 底層實(shí)際調(diào)用HashMap的size()方法返回Entry的數(shù)量，就得到該Set中元素的個(gè)數(shù),。
* @return 此set中的元素的數(shù)量（set的容量）,。
*/
public int size() {
return map.size();
}
/**
* 如果此set不包含任何元素，則返回true,。
*
* 底層實(shí)際調(diào)用HashMap的isEmpty()判斷該HashSet是否為空,。
* @return 如果此set不包含任何元素，則返回true,。
*/
public boolean isEmpty() {
return map.isEmpty();
}
/**
* 如果此set包含指定元素,，則返回true。
* 更確切地講,，當(dāng)且僅當(dāng)此set包含一個(gè)滿(mǎn)足(o==null ? e==null : o.equals(e))
* 的e元素時(shí),，返回true。
*
* 底層實(shí)際調(diào)用HashMap的containsKey判斷是否包含指定key,。
* @param o 在此set中的存在已得到測(cè)試的元素,。
* @return 如果此set包含指定元素，則返回true,。
*/
public boolean contains(Object o) {
return map.containsKey(o);
}
/**
* 如果此set中尚未包含指定元素,，則添加指定元素。
* 更確切地講,，如果此 set 沒(méi)有包含滿(mǎn)足(e==null ? e2==null : e.equals(e2))
* 的元素e2,，則向此set 添加指定的元素e。
* 如果此set已包含該元素,，則該調(diào)用不更改set并返回false,。
*
* 底層實(shí)際將將該元素作為key放入HashMap。
* 由于HashMap的put()方法添加key-value對(duì)時(shí),，當(dāng)新放入HashMap的Entry中key
* 與集合中原有Entry的key相同（hashCode()返回值相等,，通過(guò)equals比較也返回true），
* 新添加的Entry的value會(huì)將覆蓋原來(lái)Entry的value,，但key不會(huì)有任何改變,，
* 因此如果向HashSet中添加一個(gè)已經(jīng)存在的元素時(shí)，新添加的集合元素將不會(huì)被放入HashMap中,，
* 原來(lái)的元素也不會(huì)有任何改變,，這也就滿(mǎn)足了Set中元素不重復(fù)的特性。
* @param e 將添加到此set中的元素,。
* @return 如果此set尚未包含指定元素,，則返回true。
*/
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
/**
* 如果指定元素存在于此set中,，則將其移除,。
* 更確切地講，如果此set包含一個(gè)滿(mǎn)足(o==null ? e==null : o.equals(e))的元素e,，
* 則將其移除,。如果此set已包含該元素，則返回true
* （或者：如果此set因調(diào)用而發(fā)生更改,，則返回true）,。（一旦調(diào)用返回，則此set不再包含該元素）,。
*
* 底層實(shí)際調(diào)用HashMap的remove方法刪除指定Entry,。
* @param o 如果存在于此set中則需要將其移除的對(duì)象。
* @return 如果set包含指定元素,，則返回true,。
*/
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
/**
* 從此set中移除所有元素。此調(diào)用返回后,，該set將為空,。
*
* 底層實(shí)際調(diào)用HashMap的clear方法清空Entry中所有元素。
*/
public void clear() {
map.clear();
}
/**
* 返回此HashSet實(shí)例的淺表副本：并沒(méi)有復(fù)制這些元素本身,。
*
* 底層實(shí)際調(diào)用HashMap的clone()方法,，獲取HashMap的淺表副本，并設(shè)置到HashSet中,。
*/
public Object clone() {
try {
HashSet<E> newSet = (HashSet<E>) super.clone();
newSet.map = (HashMap<E, Object>) map.clone();
return newSet;
} catch (CloneNotSupportedException e) {
throw new InternalError();
}
}
}

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,，所有內(nèi)容均由用戶(hù)發(fā)布，不代表本站觀點(diǎn),。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購(gòu)買(mǎi)等信息，謹(jǐn)防詐騙,。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請(qǐng)點(diǎn)擊一鍵舉報(bào)。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：賈朋亮博客 > 《基礎(chǔ)知識(shí)及算法》

舉報(bào)/認(rèn)領(lǐng)