java 中HashMap、HashSet、TreeMap、TreeSet判斷元素相同的幾種方法比較

java 中HashMap、HashSet、TreeMap、TreeSet判斷元素相同的幾種方法比較

1.1 HashMap

先來看一下HashMap裡面是怎麼存放元素的。 Map裡面存放的每一個元素都是key-value這樣的鍵值對，而且都是通過put方法進行添加的，而且相同的key在Map中只會有一個與之關聯的value存在。 put方法在Map中的定義如下。

 V put(K key, V value);

它用來存放key-value這樣的一個鍵值對，返回值是key在Map中存放的舊value，如果之前不存在則返回null。 HashMap的put方法是這樣實現的。

 public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } modCount++; addEntry(hash, key, value, i); return null; }

從上我們可以看到在添加對應的key-value這樣的組合時，如果原本已經存在對應的key，則直接改變對應的value，並返回舊的value，而在判斷key是否存在的時候是先比較key的hashCode，再比較相等或equals的。這裡可能我們還看不出來，直接從上面代碼來看是比較的對應Map.Entry的hashCode和key的hashCode，而實際上在後面我們可以看到Map.Entry的hashCode其實就是其存放key的hashCode。而如果對應的key原本不存在的話將調用addEntry將對應的key-value添加到Map中。 addEntry傳遞的參數hash就是對應key的hashCode。接著我們來看一下addEntry的方法定義。

 void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } createEntry(hash, key, value, bucketIndex); } void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++; }

addEntry的核心是調用createEntry來建立表示對應key-value的Map.Entry對象並進行存放，很顯然上述table是一個Map.Entry的數組。 Map.Entry中用一個屬性hash保存了對應key的hashCode。還是來看一下上面調用的Map.Entry的構造方法吧。

 Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; }

很顯然，其內部保存了對應key、value和key對應的hashCode。

了解了HashMap是怎樣存放元素的以後，我們再來看HashMap是怎樣存放元素的就比較簡單了。 HashMap中判斷元素是否相同主要有兩個方法，一個是判斷key是否相同，一個是判斷value是否相同。其實在介紹HashMap是怎樣存放元素時我們已經介紹了HashMap是怎樣判斷元素Key是否相同的，那就是首先得hashCode相同，其次是key相等或equals。 Map中判斷key是否相同是通過containsKey()方法進行的，其在HashMap中的實現如下。

 public boolean containsKey(Object key) { return getEntry(key) != null; } final Entry<K,V> getEntry(Object key) { int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } return null; }

很明顯，它就是先判斷key的hashCode是否相同，再判斷key是否相等或equals的。

Map中用來判斷value是否相同是通過containsValue方法來判斷的，其在HashMap中的實現如下。

 public boolean containsValue(Object value) { if (value == null) return containsNullValue(); Entry[] tab = table; for (int i = 0; i < tab.length ; i++) for (Entry e = tab[i] ; e != null ; e = e.next) if (value.equals(e.value)) return true; return false; }

很顯然，對於非null形式的value是通過value的equals來進行判斷的，而null形式的只要相等即可，即保存的元素中有value為null即可。

1.2 HashSet

知道了HashMap是如何存放元素和判斷元素是否相同的方式以後，我們再來看HashSet是如何判斷元素是否相同就比較簡單了。

HashSet中的元素其實是通過HashMap來保存的，在每個HashSet對像中都持有一個對應的HashMap對象的引用，在對HashSet進行元素的添加、刪除等操作時都是通過其持有的HashMap來進行的。在保存元素時其會將對應的元素作為持有的HashMap的key來進行保存，對應的value是一個常量Object，所以其在保存的時候判斷元素是否相同所使用的是HashMap判斷key是否相同的邏輯。其在判斷是否包含某一元素時也是調用了所持有的HashMap的containsKey方法來進行判斷的。

 public boolean contains(Object o) { returnmap.containsKey(o); }

有興趣的朋友可以去看一下HashSet的源碼。

1.3 TreeMap

TreeMap中存放的元素都是有序的，而且是根據key進行排序的。 TreeMap在對存放的元素進行排序時有兩種方式，一種是通過自身持有的Comparator進行排序，另一種是通過實現了Comparable接口的key進行排序，優先使用第一種方式，當持有的Comparator（默認為null）為null時則採用第二種方式。 TreeMap好幾個構造方法，可以通過其構造方法來初始化其持有的Comparator。我們還是先來看一下TreeMap是如何保存元素的，其put方法實現如下。

 public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { compare(key, key); // type (and possibly null) check root = new Entry<>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; if (cpr != null) { do { parent = t; cmp = cpr.compare(key, t.key); if (cmp < 0) t = t.left; elseif (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } else { if (key == null) thrownew NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; elseif (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } Entry<K,V> e = new Entry<>(key, value, parent); if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e); size++; modCount++; return null; }

從上述實現我們可以看到，第一個元素將直接存進去。之後的元素分兩種情況進行，一種是持有的Comparator不為空的情況，一種是持有的Comparator為空的情況。 Comparator不為空的時候將通過Comparator來確定存放元素的位置，其中有一點很重要的是當通過Comparator比較了現有元素的key與當前存放元素的key的結果為0時，將認為當前存放的元素key在原有Map中已經存在，然後改變原有的key對應的value為新value，然後就直接返回了舊value。當持有的Comparator為空時將通過實現了Comparable接口的key的compareTo方法來決定元素存放的位置，有一點與使用Comparator類似的地方是當原有key作為Comparable與新存入的key進行比較的結果為0時將認為新存入的key在原Map中已經存在，將直接改變對應的原key的value，而不再新存入key-value對。實際上其判斷元素是否存在的containsKey方法的主要實現邏輯也是類似的，具體實現如下。

 public boolean containsKey(Object key) { return getEntry(key) != null; } final Entry<K,V> getEntry(Object key) { // Offload comparator-based version for sake of performance if (comparator != null) return getEntryUsingComparator(key); if (key == null) thrownew NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0) p = p.left; elseif (cmp > 0) p = p.right; else return p; } return null; }

因為TreeMap判斷元素是否存在的邏輯是通過判斷Comparator或Comparable進行比較後的結果是否為0，所以我們在使用TreeMap希望實現某種類似於元素equals的邏輯時要特別小心。

TreeMap的containsValue的邏輯還是判斷的對應的value是否equals，與HashMap類似，有興趣的朋友可以查看一下TreeMap的源碼。

1.4 TreeSet

TreeSet也是的Set的一種實現，其存放的元素是不重複的，而且是有序的，默認情況下所存放的元素必須實現Comparable接口，因為默認情況下將把元素當做Comparable對象進行比較。 TreeSet也是可以通過Comparator來比較其中存放的元素的，這可以在構造TreeSet的時候通過傳入一個Comparator對像或一個持有Comparator對象的TreeMap來實現。 TreeSet的實現與HashSet的實現類似，其內部也持有了一個Map的引用，只不過它引用的不是HashMap，而是TreeMap。 TreeSet中元素的新增、刪除等操作都是由其持有的TreeMap來實現的，所以與HashSet類似，TreeSet中判斷元素是否相同的方式與TreeMap是一致的，也是通過Comparator或Comparable來判定的，而不是傳統的equals方法。有興趣的朋友可以去查看一下TreeSet的源碼。

感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！