HashMap、HashSet、TreeMap、TreeSet判断元素是否存在的逻辑

一时失言乱红尘 2022-06-13 00:39 210阅读 0赞

###     ###

## 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) \{

**return**map.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的源码。

（注：本文是基于JDK1.7所写）

（注：原创文章，转载请注明出处。原文地址：[http://elim.iteye.com/blog/2247174][http_elim.iteye.com_blog_2247174]）

[http_elim.iteye.com_blog_2247174]: http://elim.iteye.com/blog/2247174

发表评论取消回复

表情：

评论列表（有 0 条评论，210人围观）

还没有评论，来说两句吧...

相关阅读

相关 jquery判断dom元素是否存在

需求，在js文件中通过id属性，判断对应的html界面中的一个元素是否存在 if($("id").length >0){ //元素存在，则length=1

拼搏现实的明天。/ 2023年03月02日 13:19/ 0 赞/ 14 阅读

相关 Java判断集合中是否存在某个元素的方法

List集合使用`boolean contains(Object o)`方法实际上，调用contains(Object obj)方法时，会遍历List中的每一个元

╰+攻爆jí腚メ/ 2023年02月13日 14:52/ 0 赞/ 3 阅读

相关判断html元素是否存在

假如我们要判断页面上是否存在Id为 wrap的元素是否存在，因为无轮这个元素是否存在，$("\wrap")的返回值都是object 那我们就不能通过 null ，undef

快来打我*/ 2022年09月25日 02:30/ 0 赞/ 258 阅读

相关 JQuery判断HTML元素是否存在

js的方法： if(document.getElementById('example')) \{ // do something \}

朱雀/ 2022年08月09日 06:22/ 0 赞/ 226 阅读

相关 jquery判断页面中是否存在某元素

script> if($('div').length>0) { alert('页面中存在div元素'); } else {

你的名字/ 2022年07月15日 14:23/ 0 赞/ 253 阅读

相关 HashMap、HashSet、TreeMap、TreeSet判断元素是否存在的逻辑

1.1 HashMap 先来看一下HashMap里面是怎么存放元素的。Map里面存放的每一个元素都是key-value这样的键值

一时失言乱红尘/ 2022年06月13日 00:39/ 0 赞/ 211 阅读

相关判断list中是否存在重复元素

判断list中是否有重复的元素可以使用hashset， hashset可以自动去除重复的元素； List<Integer> list = new ArrayList

青旅半醒/ 2022年05月26日 04:45/ 0 赞/ 709 阅读

相关判断一个数组是否存在空的元素

来源： [https://stackoverflow.com/questions/37046882/the-cyclomatic-complexity-of-this-meth

超、凢脫俗/ 2022年02月01日 10:37/ 0 赞/ 306 阅读

相关 appium+python 判断元素是否存在

原文链接：[https://testerhome.com/topics/7091][https_testerhome.com_topics_7091] 方法一： d

电玩女神/ 2022年01月31日 02:04/ 0 赞/ 476 阅读

相关 python3 判断列表是否存在某元素

成员运算符 <table> <thead> <tr> <th>运算符</th> <th>描述</th> </tr> </thead>

傷城~/ 2021年07月28日 19:30/ 0 赞/ 534 阅读