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的源码。
(注:本文是基于JDK1.7所写)
(注:原创文章,转载请注明出处。原文地址:http://elim.iteye.com/blog/2247174)
相关推荐
综上所述,选择`TreeMap`、`TreeSet`、`HashSet`还是`HashMap`,主要取决于具体的应用需求,比如是否需要保持元素的排序,是否允许重复元素,以及对插入、删除和查找操作速度的要求。正确理解并使用这些集合类,可以...
因此,HashSet判断元素是否重复的方式与HashMap类似:首先计算元素的哈希值,然后通过equals()方法检查是否存在相同的元素。 **TreeMap** TreeMap是一个有序的键值对存储结构,它根据键的自然顺序或者自定义比较器...
HashSet是基于HashMap实现的,它不保证元素的顺序,允许有null值,但不允许有重复元素。HashSet内部通过哈希函数来定位元素,因此它的插入、删除和查找操作通常具有较高的效率,平均时间复杂度为O(1)。但是由于哈希...
首先,`HashSet`是基于`HashMap`实现的,它不保证元素的顺序,插入顺序和迭代顺序可能不同。它允许存储null值,但不允许存储重复元素。`HashSet`的核心优点在于其快速的插入、删除和查找操作,时间复杂度通常为O(1)...
HashSet和TreeSet都是Java集合框架中的Set接口实现,用于存储不重复的元素。但是,它们在使用方法和实现机理上有很大的区别。 首先,从使用方法上讲,HashSet和TreeSet都可以用于存储不重复的元素,但是它们在元素...
### Java中HashMap, LinkedHashMap, TreeMap,HashTable的区别 在Java编程语言中,`Map`接口是集合框架中的一个重要组成部分,用于存储键值对。本文将详细分析四种常用的`Map`实现类:`HashMap`, `LinkedHashMap`, ...
本资源聚焦于Java集合中的四个关键类:HashSet、TreeSet、HashMap和TreeMap,它们分别代表了不同类型的集合容器。 1. **HashSet**:HashSet是一个不允许重复元素的无序集合。它基于哈希表实现,插入和查找操作的...
Java和python的数据结构说明这是有关Java基本数据结构用法的注释,其中包括:数组列表(LinkedList,Arraylist)堆栈队列双端队列PriorityQueue HashMap HashSet TreeMap TreeSet String Lambda表达式,用于比较器...
3. HashSet:基于HashMap实现的,底层采用HashMap来保存元素。 4. LinkedHashSet:继承于HashSet,并且其内部是通过LinkedHashMap实现的。 5. TreeSet:红黑树(自平衡的排序二叉树)。 6. HashMap:JDK1.8之前由...
- `contains(Object o)`:判断集合是否包含指定元素,通过调用HashMap的`containsKey()`方法实现。 4. 删除元素: - `remove(Object o)`:删除指定元素,调用HashMap的`remove()`方法,返回值表示操作是否成功。 ...
Set接口(如HashSet、TreeSet)则确保元素唯一性,不保证顺序,适用于去重或存储不需排序的独特元素;而Map接口(如HashMap、TreeMap)用于存储键值对,键是唯一的,可以快速查找对应的值。 关于“HashSet保证数据...
Containers, Sets, Lists, Stacks, Maps, Trees, HashSet, TreeSet, ArrayList, SinglyLinkedList, DoublyLinkedList, LinkedListStack, ArrayStack, HashMap, TreeMap, RedBlackTree, BinaryHeap, Comparator, ...
chapter7可能会详细讲解这些接口和类的特性和用法,比如ArrayList与LinkedList的区别,HashSet和TreeSet的元素排序规则,以及HashMap和TreeMap如何存储键值对。 再者,Java的IO流系统提供了读写数据的能力,分为...
GoDS(Go数据结构) Go中各种数据结构和算法的实现。 数据结构 货柜 所有数据结构都通过以下方法实现容器接口: type Container interface { Empty () bool Size () int Clear () Values () [] interface {} ...
2. **HashSet与TreeSet的区别**:HashSet内部使用HashMap存储元素,不保证元素顺序,允许null值;TreeSet使用TreeMap,按照元素自然排序或自定义比较器排序,不允许null值。 3. **HashMap与TreeMap的区别**:...
本篇PPT教程针对初级学者,将介绍一些核心的Java类,如Date、Calendar、Math以及BigInteger,还会涉及常用的容器类,包括ArrayList、LinkedList、HashSet、HashMap、TreeSet和TreeMap。 首先,我们来看Date类。Date...
HashSet依赖于HashMap,其内部使用哈希表存储元素,不保证元素的顺序,但插入和查找速度快。TreeSet则维护了元素的排序,它基于红黑树数据结构,提供了有序的遍历。 Map接口用于存储键值对,HashMap、TreeMap和...
HashSet 和 TreeSet 有什么区别? HashMap 和 TreeMap 有什么区别? 什么是迭代器?如何使用它来遍历集合? 什么是 fail-fast 机制? 如何使用 Collections 类对集合进行排序? 什么是 Comparable 和 Comparator ...
HashSet的底层源码(JDK 1.7和1.8)揭示了其依赖于HashMap实现,元素的存储和查找基于对象的哈希值。 LinkedHashSet与HashSet相似,但保留了插入顺序,通过维护一个双向链表来实现。 TreeSet则实现了SortedSet接口...
常见的 Set 实现类有 HashSet 和 TreeSet。 * Map 是一个无序集合,集合中包含一个键对象和一个值对象,键对象不允许重复,值对象可以重复。常见的 Map 实现类有 HashMap 和 TreeMap。 2. Collection 和 Iterator ...