服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - Java教程 - java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较

java 中HashMap、HashSet、TreeMap、TreeSet判断元素相同的几种方法比较

2020-07-21 12:14java教程网 Java教程

这篇文章主要介绍了从源码的角度浅析HashMap、TreeMap元素的存储和获取元素的逻辑;从Map与Set之间的关系浅析常用的Set中元素的存储和判断是否重复的逻辑,需要的朋友可以参考下

javaHashMapHashSetTreeMapTreeSet判断元素相同的几种方法比较

1.1     HashMap

       先来看一下HashMap里面是怎么存放元素的。Map里面存放的每一个元素都是key-value这样的键值对,而且都是通过put方法进行添加的,而且相同的key在Map中只会有一个与之关联的value存在。put方法在Map中的定义如下。

?
1
V put(K key, V value);

       它用来存放key-value这样的一个键值对,返回值是key在Map中存放的旧value,如果之前不存在则返回null。HashMap的put方法是这样实现的。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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的方法定义。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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的构造方法吧。

?
1
2
3
4
5
6
7
8
9
10
11
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中的实现如下。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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中的实现如下。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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方法来进行判断的。

?
1
2
3
4
5
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方法实现如下。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
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方法的主要实现逻辑也是类似的,具体实现如下。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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的源码。

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

延伸 · 阅读

精彩推荐