Set 中的元素為什么不允許重復

?????? 版權所有，轉載請聲明出處 zhyiwww@163.com

?

為了弄清楚這個問題 , 我又看了一遍 Collection 部分 , 并且看了些其中的源碼 , 覺得對其中的實現又明白了一點 , 現在說出來和大家共享 .

我們先看一下 Set 類的關系圖：

現在我們就從 Set 說起。

Set 接口為我們提供了一個 add() 方法，以讓我們添加元素。所以我們看一下在其實現類 HashSet 中是如何實現的呢？

我們看 HashSet 中的 add() 方法實現；

??? public boolean add( E o ) {

?????? ?????? return? map.put(o, PRESENT)==null;

}

你可能回問怎么回出來 map 了呢？

Map 又是一個什么變量呢？

我們來看 map 是在在哪定義的。原來，在 HashSet 中定義了這樣的兩個變量：

??? private transient HashMap<E,Object> map;

??? private static final Object PRESENT = new Object();

我們再看一下上面的 add() 方法。

map.put(o, PRESENT)==null

實際執行的是 map 的方法，并且我們添加的對象是 map 中的 key,value 是執行的同一個對象 PRESENT.

因為map中的key是不允許重復的，所以set中的元素不能重復。

?

下面我們再看一下， map 又是如何保證其 key 不重復的呢？

?

現在我們看一下 map 中的 put() 方法的實現：

HashMap 實現了 map ，在 HashMap 中是這樣實現的：

??? public V put(K key, V value) {

????? K k = maskNull(key);

??????? int hash = hash(k);

??????? int i = indexFor(hash, table.length);

??????? for (Entry<K,V> e = table[i]; e != null; e = e.next) {

??????????? if (e.hash == hash && eq(k, e.key)) {

??????????????? V oldValue = e.value;

??????????????? e.value = value;

??????????????? e.recordAccess(this);

??????????????? return oldValue;

??????????? }

??????? }

?

??????? modCount++;

??????? addEntry(hash, k, value, i);

??????? return null;

??? }

我們我們按照方法的執行一步一步的來看一下，其實現的過程。

K k = maskNull(key);

這一步是要判斷當前的要添加的對象的 key 是否為空，如果為空的話，那么就生成一個新的對象作為其 key 。實現如下：

??? static final Object NULL_KEY = new Object();

???? * Returns internal representation for key. Use NULL_KEY if key is null.

??? static <T> T maskNull(T key) {

??????? return key == null ? (T)NULL_KEY : key;

??? }

之后

int hash = hash(k);

我們看一下 hash() 方法的實現：

??? static int hash(Object x) {

??????? int h = x.hashCode();

??????? h += ~(h << 9);

??????? h ^=? (h >>> 14);

??????? h +=? (h << 4);

??????? h ^=? (h >>> 10);

??????? return h;

??? }

這一步其實是要得到當前要添加對象的 hashcode, 方法中，首先通過 int h = x.hashCode() 取得了當前的要添加對象的 hashcode, 然后

??????? h += ~(h << 9);

??????? h ^=? (h >>> 14);

??????? h +=? (h << 4);

??????? h ^=? (h >>> 10);

生成一個新的 hashcode.

接著執行的是

（從此處開始，我理解的比較膚淺，請看到此出的朋友多多指點）

int i = indexFor(hash, table.length);

這個方法是要 Returns index for hash code h.

??? static int indexFor(int h, int length) {

??????? return h & (length-1);

??? }

????? 下面就要根據 hashmap 中的元素逐個的比較，看是否相同，如果不同就回添加一個新的元素。是通過循環判斷來實現的。

??????? for (Entry<K,V> e = table[i]; e != null; e = e.next) {

??????????? if (e.hash == hash && eq(k, e.key)) {

??????????????? V oldValue = e.value;

??????????????? e.value = value;

??????????????? e.recordAccess(this);

這句我的理解是：在內存中的可以訪問元素又多了一個。也就是說，添加之后，可以通過hashmap來訪問此元素了。

???????? ???????return oldValue;

??????????? }

??????? }

通過循環判斷是否有完全相同的對象，包括 hashcode 和 value 值。如果已經存在就返回其值，如果不存在就執行一下操作。

??????? modCount++;

??????? addEntry(hash, k, value, i);

??????? return null;

對象不存在，首先修改 hashmap 的修改次數，即 modCount 加 1. 然后將對象添加到數組中。

??? void addEntry(int hash, K key, V value, int bucketIndex) {

????? Entry<K,V> e = table[bucketIndex];

??????? table[bucketIndex] = new Entry<K,V>(hash, key, value, e);

??????? if (size++ >= threshold)

??????????? resize(2 * table.length);

}

仍然是數組，我們來看一下 , 在 hashmap 中用來存放對象的數組的定義：

?? ?transient Entry[] table;

至此，我想大家也許應該明白了，為什么在 set 中是不允許存放重復值的。

通過才的分析，我們可以看到， map 的一些特征：

1.?????? 在 map 中也是不能存放完全相同的元素的

2.?????? 如果你存入的對象的 key 值已經存在的話，那么新的 value 將會取代老的 value 值，但是并不會添加新的元素進去。

我們可以通過一個測試程序來證明這一點：

? public void mapTest() {

??? Map m = new HashMap();

??? /**

???? * we? can? put? the? int? 1 and the? value? 1? into? the? map

???? * but? we? cannot? get? the? 1 as? int? from the map

???? * why ?

???? * we? only? get? the? 1? as? integer? from? the map,

???? * so? we? only? get the object? from the map,if we? put the? value? into

???? * the map,we? will get one? instance of? the wrapper? of? that

???? */

??? m.put(1, 1);

??? //int i = m.get(1);

??? Integer i = (Integer) m.get(1);

??? System.out.println(i);

?

??? m.put(1, 1);

??? m.put(1, 1);

??? System.out.println("map?? :??? " + m);

??? System.out.println("map? size??? :?? " + m.size());

??? m.put(1, 2);

??? System.out.println("map?? :??? " + m);

??? System.out.println("map? size??? :?? " + m.size());

? }

運行的結果是：

map?? :??? {1=1}

map? size??? :?? 1

map?? :??? {1=2}

map? size?? ?:?? 1

希望此文能大家有所幫助。

|----------------------------------------------------------------------------------------|
                           版權聲明  版權所有 @zhyiwww
            引用請注明來源 http://www.tkk7.com/zhyiwww   
|----------------------------------------------------------------------------------------|