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 简要介绍
主要介绍了从源码的角度浅析HashMap、TreeMap元素的存储和获取元素的逻辑;从Map与Set之间的关系浅析常用的Set中元素的存储和判断是否重复的逻辑,需要的朋友可以参考下
java中HashMap,LinkedHashMap,TreeMap,HashTable的区别
1) 掌握Java集合框架的概念以及几种具体实现:ArrayList, LinkedList, HashSet, TreeSet, PriorityQueue; 2) 掌握Java集合框架的映射的概念以及映射的两种基本实现:HashMap,TreeMap; 3)掌握枚举类型以及枚举集...
这篇集合总结一共包括十二节,介绍了一些接口和实现类的底层源码以及基本的增加、删除元素等的操作(包括List、Map、Set接口、ArrayList、Vector、LinkedList、HashSet、TreeSet、HashMap、TreeMap等实现类)。...
对基础的掌握尤其重要,其中List,Set,Map的作用以及使用的场景和分类描述,其中Arraylist 与 LinkedList 区别,HashSet与TreeSet与LinkedHashSet对⽐,LinkedHashMap和HashMap,TreeMap对⽐,HashMap 和 Hashtable...
Java和python的数据结构说明这是有关Java基本数据结构用法的注释,其中包括:数组列表(LinkedList,Arraylist)堆栈队列双端队列PriorityQueue HashMap HashSet TreeMap TreeSet String Lambda表达式,用于比较器...
Containers, Sets, Lists, Stacks, Maps, Trees, HashSet, TreeSet, ArrayList, SinglyLinkedList, DoublyLinkedList, LinkedListStack, ArrayStack, HashMap, TreeMap, RedBlackTree, BinaryHeap, Comparator, ...
GoDS(Go数据结构) Go中各种数据结构和算法的实现。 数据结构 货柜 所有数据结构都通过以下方法实现容器接口: type Container interface { Empty () bool Size () int Clear () Values () [] interface {} ...
本资源包含java集合(hashset treeset hashmap和treemap)的使用实例
HashSet 和 TreeSet 有什么区别? HashMap 和 TreeMap 有什么区别? 什么是迭代器?如何使用它来遍历集合? 什么是 fail-fast 机制? 如何使用 Collections 类对集合进行排序? 什么是 Comparable 和 Comparator ...
Java标准库中提供了多种实现Collection接口的类,如ArrayList、LinkedList(List的实现)、HashSet、TreeSet(Set的实现)、PriorityQueue等。 Map: Map用于存储键值对(Key-Value Pair)的数据,它的实现类有...
了解了Set接口及主要实现类(HashSet、TreeSet),了解了解List接口及主要实现类(ArrayList、LinkedList、Vector),掌握ArrayList的使用及其与Vector的区别,了解了Map接口及主要实现类(HashMap、TreeMap、...
HashMap HashSet TreeMap TreeSet StringBulider 线程安全集合: Vector HashTable Properties 集合线程安全与解决方案 ArrayList线程安全问题 package com.raicho.mianshi.mycollection; import ...
2.HashSet,TreeSet -- CopyONWriteArraySet,ConcurrentSkipListSet 3.hashMap , treeMap -- ConcurrentHashMap,ConcurentSkipListMap(key有序,支持更高并发) ## Concurrent同步工具类 countDownLatch ...
收藏 这个存储库用于我的集合实现。 只是为了训练。 ArrayQueue LinkedDequeue LinkedStack HashMap TreeMap HashSet TreeSet
Collections 源码 java Java Java的ArrayList、LinkedList、HashMap、TreeMap、LinkedHashMap、HashSet、TreeSet相关源码分析,及相关问题和应用总结。
OneSlide OneSlide是一种学习格式,其中一张幻灯片涵盖了一个技术主题。 js:未定义vs空 js:原始类型转换 js:参考和实例 js:迭代:内循环/外循环 算法:CAP定理 ... Java:设置:HashSet与TreeSet
4)了解Map接口及主要实现类(HashMap、TreeMap、HashTable) 二、实验内容及步骤 1、编写程序练习将以下5个Person类的对象放在一个HashSet中。 姓名:张三 身份证号:178880001 姓名:王五 身份证号:178880002 ...
java源码整理包:list,map,ArrayList,HashMap,HashSet,Hashtable,TreeMap,TreeSet,Vector等源码包分享