java 中HashMap、HashSet、TreeMap、TreeSet判斷元素相同的幾種方法比較
java 中HashMap、HashSet、TreeMap、TreeSet判斷元素相同的幾種方法比較
1.1 HashMap
先來看一下HashMap里面是怎么存放元素的。Map里面存放的每一個元素都是key-value這樣的鍵值對，而且都是通過put方法進行添加的，而且相同的key在Map中只會有一個與之關聯(lián)的value存在。put方法在Map中的定義如下。
V put(K key, V value);
它用來存放key-value這樣的一個鍵值對，返回值是key在Map中存放的舊value，如果之前不存在則返回null。HashMap的put方法是這樣實現(xiàn)的。
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這樣的組合時，如果原本已經(jīng)存在對應的key，則直接改變對應的value，并返回舊的value，而在判斷key是否存在的時候是先比較key的hashCode，再比較相等或equals的。這里可能我們還看不出來，直接從上面代碼來看是比較的對應Map.Entry的hashCode和key的hashCode，而實際上在后面我們可以看到Map.Entry的hashCode其實就是其存放key的hashCode。而如果對應的key原本不存在的話將調(diào)用addEntry將對應的key-value添加到Map中。addEntry傳遞的參數(shù)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的核心是調(diào)用createEntry來建立表示對應key-value的Map.Entry對象并進行存放，很顯然上述table是一個Map.Entry的數(shù)組。Map.Entry中用一個屬性hash保存了對應key的hashCode。還是來看一下上面調(diào)用的Map.Entry的構造方法吧。
Entry(int h, K k, V v, Entry<K,V> n) {
value = v;
next = n;
key = k;
hash = h;
}
很顯然，其內(nèi)部保存了對應key、value和key對應的hashCode。
了解了HashMap是怎樣存放元素的以后，我們再來看HashMap是怎樣存放元素的就比較簡單了。HashMap中判斷元素是否相同主要有兩個方法，一個是判斷key是否相同，一個是判斷value是否相同。其實在介紹HashMap是怎樣存放元素時我們已經(jīng)介紹了HashMap是怎樣判斷元素Key是否相同的，那就是首先得hashCode相同，其次是key相等或equals。Map中判斷key是否相同是通過containsKey()方法進行的，其在HashMap中的實現(xiàn)如下。
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中的實現(xiàn)如下。
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是否相同的邏輯。其在判斷是否包含某一元素時也是調(diào)用了所持有的HashMap的containsKey方法來進行判斷的。
public boolean contains(Object o) {
returnmap.containsKey(o);
}
有興趣的朋友可以去看一下HashSet的源碼。
1.3 TreeMap
TreeMap中存放的元素都是有序的，而且是根據(jù)key進行排序的。TreeMap在對存放的元素進行排序時有兩種方式，一種是通過自身持有的Comparator進行排序，另一種是通過實現(xiàn)了Comparable接口的key進行排序，優(yōu)先使用第一種方式，當持有的Comparator（默認為null）為null時則采用第二種方式。TreeMap好幾個構造方法，可以通過其構造方法來初始化其持有的Comparator。我們還是先來看一下TreeMap是如何保存元素的，其put方法實現(xiàn)如下。
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;
}
從上述實現(xiàn)我們可以看到，第一個元素將直接存進去。之后的元素分兩種情況進行，一種是持有的Comparator不為空的情況，一種是持有的Comparator為空的情況。Comparator不為空的時候?qū)⑼ㄟ^Comparator來確定存放元素的位置，其中有一點很重要的是當通過Comparator比較了現(xiàn)有元素的key與當前存放元素的key的結果為0時，將認為當前存放的元素key在原有Map中已經(jīng)存在，然后改變原有的key對應的value為新value，然后就直接返回了舊value。當持有的Comparator為空時將通過實現(xiàn)了Comparable接口的key的compareTo方法來決定元素存放的位置，有一點與使用Comparator類似的地方是當原有key作為Comparable與新存入的key進行比較的結果為0時將認為新存入的key在原Map中已經(jīng)存在，將直接改變對應的原key的value，而不再新存入key-value對。實際上其判斷元素是否存在的containsKey方法的主要實現(xiàn)邏輯也是類似的，具體實現(xiàn)如下。
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希望實現(xiàn)某種類似于元素equals的邏輯時要特別小心。
TreeMap的containsValue的邏輯還是判斷的對應的value是否equals，與HashMap類似，有興趣的朋友可以查看一下TreeMap的源碼。
1.4 TreeSet
TreeSet也是的Set的一種實現(xiàn)，其存放的元素是不重復的，而且是有序的，默認情況下所存放的元素必須實現(xiàn)Comparable接口，因為默認情況下將把元素當做Comparable對象進行比較。TreeSet也是可以通過Comparator來比較其中存放的元素的，這可以在構造TreeSet的時候通過傳入一個Comparator對象或一個持有Comparator對象的TreeMap來實現(xiàn)。TreeSet的實現(xiàn)與HashSet的實現(xiàn)類似，其內(nèi)部也持有了一個Map的引用，只不過它引用的不是HashMap，而是TreeMap。TreeSet中元素的新增、刪除等操作都是由其持有的TreeMap來實現(xiàn)的，所以與HashSet類似，TreeSet中判斷元素是否相同的方式與TreeMap是一致的，也是通過Comparator或Comparable來判定的，而不是傳統(tǒng)的equals方法。有興趣的朋友可以去查看一下TreeSet的源碼。
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關文章
Java中提供synchronized后為什么還要提供Lock
這篇文章主要介紹了Java中提供synchronized后為什么還要提供Lock，在Java中提供了synchronized關鍵字來保證只有一個線程能夠訪問同步代碼塊，下文更多相關資料需要的小伙伴可以參考一下2022-03-03
在鎖的使用中會導致運行效率降低，ThreadLocal的使用徹底避免對共享資源的競爭，同時又可以不影響效率。本文詳細講解了ThreadLocal，需要了解的小伙伴可以看一看這篇文章2021-08-08
緩存的重要性是不言而喻的，使用緩存，我們可以避免頻繁的與數(shù)據(jù)庫進行交互，尤其是在查詢越多、緩存命中率越高的情況下，使用緩存對性能的提高更明顯。本文將給大家詳細的介紹，對大家的學習或工作具有一定的參考借鑒價值2021-09-09
Java?ThreadPoolExecutor線程池有關介紹
這篇文章主要介紹了Java?ThreadPoolExecutor線程池有關介紹，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-09-09
SpringBoot實現(xiàn)定時任務動態(tài)管理示例
這篇文章主要為大家介紹了SpringBoot實現(xiàn)定時任務動態(tài)管理示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-06-06
詳解Java中NullPointerException的處理方法
這篇文章將帶大家來單獨看一個很常見的異常--空指針異常,這個可以說是每個Java程序員都必知的異常,所以我們不得不單獨學習一下,文中有詳細的代碼示例,需要的朋友可以參考下2023-08-08
驗證碼可以有效防止其他人對某一個特定的注冊用戶用特定的程序,破解方式進行不斷的登錄嘗試,我們其實很經(jīng)?？吹?登錄一些網(wǎng)站其實是需要驗證碼的,所以本文給大家分享了SpringBoot實現(xiàn)驗證碼的案例,需要的朋友可以參考下2024-11-11
我們知道，當寫完一個普通的 Java 類后，想讓 Spring IoC 容器在創(chuàng)建類的實例對象時使用構造方法完成實例對象的依賴注入，那么就需要在配置元數(shù)據(jù)中寫好類的 Bean 定義，包括各種標簽的屬性。所以本文我們來說說這其中的配置細節(jié),需要的朋友可以參考下2023-07-07
Spring AOP如何實現(xiàn)注解式的Mybatis多數(shù)據(jù)源切換詳解
這篇文章主要給大家介紹了關于Spring AOP如何實現(xiàn)注解式的Mybatis多數(shù)據(jù)源切換的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
forEach對于基本數(shù)據(jù)類型,是直接賦值,對于引用數(shù)據(jù)類型,是引用地址值,forEach遍歷時,是創(chuàng)建的臨時變量,引用的數(shù)據(jù)地址,本文給大家介紹Java forEach對原數(shù)組的操作過程,感興趣的朋友一起看看吧2024-02-02