转载

HashMap、HashSet、TreeMap、TreeSet判断元素相同

HashMap 、 HashSet 、 TreeMap 、 TreeSet 判断元素相同

1.1 HashMap

1.2 HashSet

1.3 TreeMap

1.4 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) {

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 ;

else if (cmp > 0)

t = t. right ;

else

return t.setValue(value);

} while (t != null );

}

else {

if (key == null )

throw new NullPointerException();

Comparable<? super K> k = (Comparable<? super K>) key;

do {

parent = t;

cmp = k.compareTo(t. key );

if (cmp < 0)

t = t. left ;

else if (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 )

throw new 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 ;

else if (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 的源码。