Set 和 Map
Set 代表一种集合元素无序、集合元素不可重复的集合,Map则代表一种由多个 key-value 对组成的集合,Map 集合类似于传统的关联数组。表面上看它们之间相似性很少,但实际上 Map 和 Set 之间有莫大的关联,可以说,Map 集合是 Set 集合的扩展。
Set 和 Map 的关系
再看 Set 和 Map 之间的关系之前,先来看看 Set 集合的继承体系,如上图左侧所示。
再来看 Map 集合的继承体系,如上图右侧所示。
仔细观察上图中 Map 集合的继承体系里被灰色覆盖的区域,可以发现,这些 Map 接口、实现类和 Set 集合的接口、实现类的类名完全相似,把 Map 后缀改为 Set 后缀即可。Set 集合和 Map 集合的对饮关系如下:
- Set <-\> Map
- EnumSet <-\> EnumMap
- SortedSet <-\> SortedMap
- TreeSet <-\> TreeMap
- NavigableSet <-\> NavigableMap
- HashSet <-\> HashMap
- LinkedHashSet <-\> LinkedHashMap
这些接口和类名如此相似绝不是偶然现象,肯定其必然有原因。
表名上看,这两种集合并没有太多的相似之处,但如果只考察 Map 集合的 key,不难发现,这些 Map 集合的 key 具有一个特性:所有 key 不能重复,key 质检没有顺序。也就是说,如果将 Map 集合的所有 key 集中起来,那这些 key 就组成了一个 Set 集合。所以,发现 Map 集合提供了如下方法来返回所有 key 组成的 Set 集合。
Set<K> keySet()
由此可见,Map 集合的所有 key 将具有 Set 集合的特征,只要把 Map 的所有 key 集中起来看,那它就是一个 Map,这实现了从 Map 到 Set 的转换。其实,还可以实现从 Set 到 Map 的扩展————对于 Map 而言,相当于每个元素都是 key-value 的 Set 集合。
换一种思维来理解 Map 集合,如果把 Map 集合中的 value 当成 key 的“附属物”(实际上也是,对于一个 Map 集合而言,只要给出指定的 key,Map 总是可以根据该 key 快速查询到对应的 value),那么 Map 集合在保存 key-value 对时只考虑 key 即可。
对于一个 Map 集合而言,它本质上是一个关联数组,如上图左侧所示。
对于上图左侧所示的关联数组,其实可以改为使用一个 Set 集合来保存它们,反正上面关联数组中 key-value 对质检有严格的对应关系,那么干脆将 key-value 对捆绑在一起对待,如上图右侧所示。
为了把 Set 扩展成 Map,可以考虑新增定义一个 SimpleEntry 类,该类代表一个 key-value 对;当 Set 集合的集合元素都是 SimpleEntry 对象时,该 Set 集合就能被当成 Map 使用。下面程序示范了如何将一个 Set 集合扩展成 Map 集合。
import java.io.Serializable;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Map;
class SimpleEntry<K, V> implements Map.Entry<K, V>, Serializable {
private static final long serialVersionUID = 1L;
private final K key;
private V value;
//定义如下2个构造器
public SimpleEntry(K key, V value) {
this.key = key;
this.value = value;
}
public SimpleEntry(Map.Entry<? extends K, ? extends V> entry) {
this.key = entry.getKey();
this.value = entry.getValue();
}
//获取key
@Override
public K getKey() {
return key;
}
//获取value
@Override
public V getValue() {
return value;
}
//改变该Key-value对的value值
@Override
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
//根据key计算hashCode
@Override
public int hashCode() {
return key == null ? 0 : key.hashCode();
}
//根据key比较2个SimpleEntry是否相等
@Override
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (o.getClass() == SimpleEntry.class) {
@SuppressWarnings("rawtypes")
SimpleEntry se = (SimpleEntry)o;
return se.getKey().equals(getKey());
}
return false;
}
@Override
public String toString() {
return key + "=" + value;
}
}
//继承HashSet实现一个Map
public class Set2Map<K, V> extends HashSet<SimpleEntry<K, V>> {
private static final long serialVersionUID = 1L;
//实现清空所有key-value对的方法
@Override
public void clear() {
super.clear();
}
//判断是否包含某个key
@SuppressWarnings({ "unchecked", "rawtypes" })
public boolean containsKey(K key) {
return super.contains(new SimpleEntry(key, null));
}
//判断是否包含某个value
boolean containsValue(V value) {
for (SimpleEntry<K, V> se : this) {
if (se.getValue().equals(value)) {
return true;
}
}
return false;
}
//根据指定key取出对应的value
public V get(K key) {
for (SimpleEntry<K, V> se : this) {
if (se.getKey().equals(key)) {
return se.getValue();
}
}
return null;
}
//将指定key-value对放入集合
public V put(K key, V value) {
super.add(new SimpleEntry<K, V>(key, value));
return value;
}
//将另外一个Map的key-value对放入该Map中
@SuppressWarnings({ "unchecked", "rawtypes" })
public void putAll(Map<? extends K, ? extends V> m) {
for (K key : m.keySet()) {
super.add(new SimpleEntry(key, m.get(key)));
}
}
//根据指定key删除Key-value对
public V removeEntry(K key) {
for (Iterator<SimpleEntry<K, V>> it = this.iterator();it.hasNext();) {
SimpleEntry<K, V> en = it.next();
if (en.getKey().equals(key)) {
V v = en.getValue();
it.remove();
return v;
}
}
return null;
}
//获取该Map中包含多少个key-value对
@Override
public int size() {
return super.size();
}
}
下面程序简单测试了扩展出来的“Map”集合
public class Set2MapTest {
public static void main(String[] args) {
Set2Map<String, Integer> scores = new Set2Map<String, Integer>();
//将key-value对放入集合
scores.put("语文", 89);
scores.put("数学", 83);
scores.put("英文", 80);
System.out.println(scores);
//访问Map集合里包含的key-value对
System.out.println(scores.size());
scores.removeEntry("数学");
System.out.println("删除key为\"数学\"的Entry之后:" + scores);
//根据key取出value
System.out.println("语文成绩:" + scores.get("语文"));
//判断是否包含指定key
System.out.println("是否包含\"英文\"key:" + scores.containsKey("英文"));
//判断是否包含指定value
System.out.println("是否包含82 value:" + scores.containsValue(82));
//清空集合
scores.clear();
System.out.println("执行clear()方法之后的集合:" + scores);
}
}
输出结果为:
[英文=80, 数学=83, 语文=89]
3
删除key为"数学"的Entry之后:[英文=80, 语文=89]
语文成绩:89
是否包含"英文"key:true
是否包含82 value:false
执行clear()方法之后的集合:[]
根据此处介绍的这个程序不难看出,只要对传统 Set 稍加改造,就可以将 Set 改造成 Map 集合,而且,这个 Map 集合在功能上几乎可以与系统提供的 Map 类媲美。
HashMap 和 HashSet
前面将一个 Set 集合扩展成了 Map 集合,由于这个 Set 采用了 HashSet 作为实现类,HashSet 会使用 Hash 算法来保存每个 SimpleEntry 元素,因此扩展出来的 Map 本质上是一个 HashMap。
实际上,HashSet 和 HashMap 之间有很多相似之处。对于 HashSet 而言,系统采用 Hash 算法决定集合元素的储存位置,这样可以保证快速存、取集合元素;对于 HashMap 而言,系统将 value 当成 key 的附属,系统根据 Hash 算法来决定 key 的储存位置,这样可以保证快速存、取集合 key,而 value 总是紧随 key 储存。
在介绍集合存储之前需要指出一点:虽然集合号称储存的是 Java 对象,但实际上并不会真正将 Java 对象放入 Set 集合中,而只是在 Set 集合中保留这些对象的引用而已。也就是说,Java 集合实际上是多个引用变量所组成的集合,这样引用变量将指向实际的 Java 对象。
就像引用类型的数组一样,当把 Java 对象放入数组之时,并不是真正把 Java 对象放入数组中,而只是把对象的引用放入数组中,每个数组元素都是一个引用变量。
对于每个 Java 集合来说,其实它只是多个引用变量的集合,下面的程序可以证明这一点。
import java.util.ArrayList;
import java.util.List;
class Apple {
double weight;
public Apple(double weight) {
this.weight = weight;
}
}
public class ListTest {
public static void main(String[] args) {
//创建2个Apple对象
Apple t1 = new Apple(2.2);
Apple t2 = new Apple(1.8);
List<Apple> list = new ArrayList<Apple>(4);
//将2个Apple对象放入List集合中
list.add(t1);
list.add(t2);
//判断从集合里取出的引用变量和原有引用变量是否指向同一个元素
System.out.println(list.get(0) == t1);
System.out.println(list.get(1) == t2);
}
}
ArrayList 底层是基于数组实现的,也就是说 ArrayList 底层封装的是数组,每次创建 ArrayList 时传入的 int 参数就是它所包装的数组的长度;如果创建 ArrayList 时没有传入 int 参数,那么 ArrayList 的初始长度为 10,也就是底层所封装的数组的长度为 10。
实际上,此时 t1 和 list 集合的第 1 个元素都指向同一个 Java 对象,t2 和 list 的第 2 个元素也指向同一个 Java 对象,因此上面的程序将会输出 2 个 true。
下面将详细介绍 HashSet、HashMap 对集合元素的储存方式。当程序视图将多个 key-value 放入 HashMap 中时,示例代码片段如下:
HashMap<String, Double> map = new HashMap<String, Double>();
map.put("语文", 80.0);
map.put("数学", 89.0);
map.put("英语", 78.2);
对于 HashMap 而言,它的储存方式要比 ArrayList 复杂一些,采用一种所谓的“Hash 算法”来决定每个元素的储存位置。
当程序执行 map.put("语文", 80.0);
时,系统将调用“语文”的 hashCode() 方法得到其 hashCode 值————每个 Java 对象都有 hashCode() 方法,都可以通过该方法获得它的 hashCode() 值。而得到这个对象的 hashCode 值之后,系统会根据该 hashCode 值来决定该元素的储存位置。
HashMap 类 put(K key, V value)
方法的源代码如下(JDK8):
public V put(K key, V value) {
//根据key计算Hash值,并调用putVal方法
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断Node数组table是否为空,如果为空创建一个新的Node数组
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果hash值对应的索引在Node数组中的Node为null,则在该索引对应的Node数组中创建一个新的Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//如果索引对应的Node数组中的Node不为null
else {
Node<K,V> e; K k;
//判断需要添加的Node是否和原来的Node一致,并且key不会null
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//判断Node是否是一个TreeNode,TreeNode是继承于LinkedHashMap.Entry<K,V>,用于标记一个有序的Node
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//找到指定key与需要放入的key相等的Node
for (int binCount = 0; ; ++binCount) {
//索引处的Node的下一个Node为null
if ((e = p.next) == null) {
//创建一个新的Node关联到Node的next属性上,形成一个Node链
p.next = newNode(hash, key, value, null);
//当bin计算器达到TreeNode的最低要求8时候,就将当前的Node数组转换为TreeNode,以提高操作效率
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//判断是否该Node和需要添加的Node一样
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//判断已经找到key匹配的Node
if (e != null) { // existing mapping for key
V oldValue = e.value;
//判断Node数组的值已经被修改过或者该Node之前的value为null,就修改该Node的value为传入的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//操作计数符
++modCount;
//如果Map中的key-value对超过了Node数组的极限,就对Node数组进行扩容,默认是在 resize() 方法中,将原来的数组扩大一倍
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
在这里,JDK1.7 和 JDK1.8 有一些区别,在 JDK1.7 中,使用一个Entry数组来存储数据,用key的hashcode取模来决定key会被放到数组里的位置,如果hashcode相同,或者hashcode取模后的结果相同(hash collision),那么这些key会被定位到Entry数组的同一个格子里,这些key会形成一个链表。在hashcode特别差的情况下,比方说所有key的hashcode都相同,这个链表可能会很长,那么put/get操作都可能需要遍历这个链表,也就是说时间复杂度在最差情况下会退化到 O(n)。
在 JDK1.8 中,使用一个Node数组来存储数据,但这个Node可能是链表结构,也可能是红黑树结构。如果插入的key的hashcode相同,那么这些key也会被定位到Node数组的同一个格子里。如果同一个格子里的key不超过8个,使用链表结构存储。如果超过了8个,那么会调用treeifyBin函数,将链表转换为红黑树。那么即使hashcode完全相同,由于红黑树的特点,查找某个特定元素,也只需要 O(log n) 的开销,也就是说put/get的操作的时间复杂度最差只有 O(log n)。听起来挺不错,但是真正想要利用JDK1.8的好处,有一个限制:key 的对象,必须正确的实现了 Compare 接口,如果没有实现Compare接口,或者实现得不正确,那JDK1.8的HashMap其实还是慢于JDK1.7 的。
上面的程序中用到了一个重要的内部接口 Map.Entry, 每个 Map.Entry 其实就是一个 key-value 对。从上面程序中可以看出:当系统决定储存 HashMap 中的 key-value 对时,完全没有考虑 Entry 中的 value,而仅仅只是根据 key 来计算并决定每个 Entry 的储存位置。这也说明了前面的结论;完全可以把 Map 集合中的 value 当成 key 的附属,当系统决定了 key 的储存位置之后,value 随之保存在那里即可。
从上面 put 方法的源代码可以看出,当程序视图将一个 Key-value 对放入 HashMap 中时,首先根据该 key 的 hashCode() 返回值觉得该 Entry 的储存位置:如果两个 Entry 的 key 的 hashCode() 返回值相同,那它们的储存位置相同;如果这两个 Entry 的 key 通过 equals 比较返回 true,新添加的 Entry 的 value 将覆盖集合中原有 Entry 的 value,但 key 不会覆盖;如果这两个 Entry 的 key 通过 equals 比较返回 false,新添加的 Entry 将与集合中原有的 Entry 形成 Entry 链,而且新添加的 Entry 位于 Entry 链的头部————具体请看 addEntry() 方法的说明(addEntry 方法在 JDK1.7 及以下版本)。
当向 HashMap 中添加 key-value 对,由其 key 的 hashCode() 返回值决定该 key-value 对(JDK1.7 中是 Entry 对象,JDK1.8 中是 Node 对象或者 红黑树对象)的储存位置。当两个 key-value 对象的 key 的 hashCode() 返回值相同时,将由 key 通过 eqauls() 比较值决定覆盖行为(返回 true),还是产生链式结构(返回 false)
程序中使用的 table 其实就是一个普通数组,每个数组都有一个固定的长度,这个数组的长度就是 HashMap 的容量。HashMap 包含了如下几个构造器:
- HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个 HashMap。
- HashMap(Map<? extends K, ? extends V> m):以给定的 Map 对象进行初始化。
当创建一个 HashMap 时,系统会自动创建一个 table 数组来保存 HashMap 中的 Enrty(JDK1.8之前)或 Node(JDK1.8及以后)。下面是 HashMap 中一个构造器的代码:
//以指定的初始化容量、负载因子创建HashMap
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能为负数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//如果负载因子大于最大容量,让初始容量等于最大容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//负载因子必须是大于0的数值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//设置容量极限,如果initialCapacity等于2的n次幂,极限容量就等于initialCapacity,如果不等于,容量极限就等于大于initialCapacity的最小的2的n次幂
this.threshold = tableSizeFor(initialCapacity);
}
上面的代码中,需要计算出数组的容量 threshold,这个值是 2的n次幂,如果 initialCapacity 不为 2的n次幂,那么就让 threshold 等于大于 initialCapacity 的最小的 2的n次幂。例如:initialCapacity 为 1,threshold 就为 1;initialCapacity 为 2,threshold 就为 2;initialCapacity 为 10,threshold 就为16。
在 JDK1.8 中,除了在使用 HashMap(Map<? extends K, ? extends V> m)
构造器时,根据给定的 Map 对象的容量大小对 table 数组进行了初始化。在另外三种构造器中并没有在构造器中对 table 数组进行初始化,采用了懒加载的模式进行初始化,在调用了 put(K key, V value)
之后,会检测 table 数组是否初始化。
从上面的代码中可以看出,创建 HashMap 时指定的 initialCapacity 并不等于 HashMap 的实际容量。通常来说,HashMap 的实际容量总比 initialCapacity 大一些,除非指定的 initialCapacity 参数值恰好是 2的n次方。在 JDK1.8 之前的版本中,应该在创建 HashMap 时将 initialCapacity 参数值指定的为 2的n次方,这样可以减少系统的计算开销;但在 JDK1.8 中采用了 tableSizeFor(int cap)
方法来寻找这个 2的n次方,该方法不会循环计算,所以对系统开销影响不明显。
对于 HashMap 及其子类而言,它们采用 Hash 算法来决定集合中元素的储存位置。当系统开始初始化 HashMap 时,系统会创建一个固定长度的数组。这个数组里可以储存元素的位置被成为“桶(bucket)”,每个 bucket 都有其指定索引,系统可以根据其索引快速访问该 bucket 里储存的元素。
无论何时,HashMap 的每个“桶”只储存一个元素。但是由于 Entry 或者 Node 的设计中包含了一个引用变量用于指引下一个 Entry 或者 Node,甚至 TreeNode 是基于红黑树设计,包含了四个引用变量。因此可能出现:HashMap 的 bucket 中只有一个元素,但这个元素指向了另外一个元素,从而形成了链式结构。
当 HashMap 的每个 bocket 里储存的元素只是单个元素时,即没有产生链式结构,此时 HashMap 具有最好的性能。当程序通过 key 取出对象的 value 时,系统只要先计算该 key 的 hashCode() 返回值,再根据该 hashCode 返回值找出该 key 在 table 数组中的索引,然后取出该索引处的元素,最后返回该 key 对应的 value。HashMap类的 get(K key)
方法代码如下(JDK1.8):
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//判断table数组不为null且table数组的长度不为0且table的第一个元素不为null
if ((tab = table) != null && (n = tab.length) > 0 &&
//直接根据key的hash值取出该hash值指定的元素
(first = tab[(n - 1) & hash]) != null) {
//首先检查第一个元素,如果第一个元素的hash值与给定的hash值相同,且该key的引用相同或key的值相同(调用equals方法)
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//判断该元素是否引用下一个元素
if ((e = first.next) != null) {
//如果元素是红黑树TreeNode,就调用红黑树的搜索方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//搜索该元素的下一个元素
do {
//如果该元素的hash值与给定的hash值相同,且该key的引用相同或key的值相同(调用equals方法)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
从上面的代码中可以看出,如果 HashMap 的每个 bucket 里只有一个元素,HashMap 可以根据索引快速取出该 bucket 里的元素。在发生“Hash冲突”的情况下,单个 bucket 里储存的不是一个元素,而是一个链式结构,系统只能必须按顺序遍历每个元素,直到找到想搜索的元素为止。如果恰好要搜索的元素位于该连接结构的末端,那必须循环到最后才能找到该元素。在 JDK1.8 中如果链式结构中的元素超过了8个,就会自动将 Node 转换为 TreeNode(红黑树),由于红黑树的搜索效果比较高,但必须正确实现Compare接口。
归纳起来简单地说,HashMap 在底层将 key-value 当成一个整体进行处理,这个整体就是一个 Entry、Node或者TreeNode 对象。HashMap 底层采用一个数组来保存所有的 key-value 对,当需要储存一个元素时,会根据 Hash 算法来决定其储存位置;当需要取出一个元素时,也会根据 Hash 算法找到起储存位置,直接取出该元素。由此可见,HashMap 之所以能快速存、取它所包含的元素,完全类似于现实生活中的:不同的东西要放在不同的位置,需要时才能快速找到它。
当创建 HashMap 时,又一个默认的负载因子(load factor),其默认值为 0.75.这是时间和空间成本是的一种折衷:增大负载因子可以减少 Hash 表所占用的内存空间,但会增加查询数据的时间开销,而查询是最频繁的操作(HashMap 的 get() 与 put() 方法都要用到查询);减少负载因子会提高数据查询的性能,但它会降低 Hash 表所占用的内存空间。
掌握了上面的知识之后,可以在创建 HashMap 时根据实际需要适当地调整 load factor 的值。如果程序比较关心空间开销,内存比较紧张,可以适当地增加负载因子;如果程序比较关心时间开销,内存比较宽裕,则可以适当较少负载因子。通常情况下,程序员无需改变负载因子的值。
如果开始就知道 HashMap 会保存多个 key-value 对,可以在创建时就使用较大的初始化容量,如果 HashMap 中元素数量一直不会超过极限容量(capacity * load factor),HashMap 就无需调用 resize() 方法重新分配 table 数组,从而保证较好的性能。当然,开始就将初始容量设置太高可能会浪费空间(系统需要创建一个长度为 capacity 的元素数组),因此创建 HashMap 时初始化容量设置也需要小心对待。
对于 HashSet 而言,它是基于 HashMap 实现的。HashSet 底层采用 HashMap 来保存所有元素,因此 HashSet 的实现比较简单,查看 HashSet 的源代码,可以看到如下所示:
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
//使用HashMap的key保存HashSet中的所有元素
private transient HashMap<E,Object> map;
//定义一个虚拟的Object对象作为HashMap的value
private static final Object PRESENT = new Object();
//初始化HashSet,底层会初始化一个HashMap
public HashSet() {
map = new HashMap<>();
}
//以指定的initialCapacity、loadFactor、已存在的集合创建HashSet
//就是以相应参数创建HashMap
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
//调用map的keyset来返回所有的key
public Iterator<E> iterator() {
return map.keySet().iterator();
}
//调用HashMap的size()方法返回元素数量,得到该Set里元素的个数
public int size() {
return map.size();
}
//调用HashMap的isEmpty()判断该HashSet是否也为空
//当HashMap为空时,对应的HashSet也为空
public boolean isEmpty() {
return map.isEmpty();
}
//调用HashMap的containsKey判断是否包含指定key
//HashSet的所有元素就是通过HashMap的Key来保存的
public boolean contains(Object o) {
return map.containsKey(o);
}
//将指定元素放入HashSet中,也就是将该元素作为key放入HashMap
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//调用HashMap的remove方法删除指定的元素,也就删除了HashSet中对应的元素
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
//调用Map的clear方法清空所有元素,也就清空了HashSet中所有元素
public void clear() {
map.clear();
}
//...
//省略部分代码
}
从上面源程序可以看出,HashSet 的实现其实非常简单,它只是封装了一个 HashMap 对象来储存所有的集合元素。所有放入 HashSet 中的集合元素实际上由 HashMap 的 key 来保存,而 HashMap 的 value 则储存了一个PRESENT,它是一个静态的 Object 对象。
HashSet 的绝大部分方法都是通过调用 HashMap 的方法来实现的,因此 HashSet 和 HashMap 两个集合在实现上本质上是相同的。
由于 HashSet 的 add() 方法添加集合元素时实际上转变为调用 HashMap 的 put() 方法来添加 key-value 对,当放入 HashMap 的元素中 key 与集合中原有元素的 key 相同(hashCode() 返回值相等,通过 equals 比较也返回 true)时,新添加的元素的 value 将覆盖原来元素的 value,但 key 不会有任何改变。因此,如果向 HashSet 中添加一个已经存在的元素,新添加的集合元素(底层由 HashMap 的 key 保存)不会覆盖已有的集合元素。
class Name {
private String first;
private String last;
public Name(String first, String last) {
this.first = first;
this.last = last;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Name.class) {
Name n = (Name)o;
return n.first.equals(first) && n.last.equals(last);
}
return false;
}
}
public class HashSetTest {
public static void main(String[] args) {
Set<Name> s = new HashSet<>();
s.add(new Name("abc", "123"));
System.out.println(s.contains(new Name("abc", "123")));
}
}
运行上面的程序将看到程序输出 false,这是因为 HashSet 判断两个对象相等的标准除了要求通过 equals() 方法比较返回 true 之外,还要求两个对象的 hashCode() 返回值相等。而上面程序没有重写 Name 类的 hashCode() 方法,两个 Name 对象的 hashCode() 返回值并不相同,因此 HashSet 会把它们当成 2 个对象对象,程序返回 false。
由此可见,当试图把某个类的对象当成 HashMap 的key,或者视图将这个类的对象放入 HashSet 中保存时,重写该类的 equals(Object obj) 方法和 hashCode() 方法很重要,而且这两个方法的返回值必须保持一致。当该类的两个 hashCode() 返回值相同时,它们通过 equals() 方法比较也应该返回 true。通常来说,所有参与计算 hashCode() 返回值的关键属性,都应该用于作为 equals() 比较的标准。
class Name {
private String first;
private String last;
public Name(String first, String last) {
this.first = first;
this.last = last;
}
public boolean equals(Object o) {
if (this == o) {
return true;
}
if (o.getClass() == Name.class) {
Name n = (Name)o;
return n.first.equals(first);
}
return false;
}
public int hashCode() {
return first.hashCode();
}
public String toString() {
return "Name[first=" + first + ", last=" + last + "]";
}
}
public class HashSetTest {
public static void main(String[] args) {
Set<Name> set = new HashSet<>();
set.add(new Name("abc", "123"));
set.add(new Name("abc", "456"));
System.out.println(set);
}
}
上面程序提供了一个 Name 类,该 Name 类重写了 equals() 和 hashCode() 2 个方法。这 2 个方法都是根据 Name 类的 first 实例变量来判断的,当 2 个 Name 对象的 fist 实例相等时,这 2 个 Name 对象的 hashCOde() 返回值也相同,通过 equals() 比较也会返回 true。
程序主方法先将第一个 Name 对象添加到 HashSet 中,该 Name 对象的 first 实例变量值为 "abc"。接着程序再次视图将一个 first 为 "abc" 的 Name 对象添加到 HashSet 中。很明显,此时没法将新的 Name 对象添加到该 HashSet 中,因为此处视图添加的 Name 对象的 first 也是 "abc",HashSet 会判断此处新增的 Name 对象与原有的 Name 对象相同,因此无法添加进入。运行代码可以看到,该集合只包含一个 Name 对象,就是第一个、即 last Field 值为 "123" 的 Name 对象。
TreeMap 和 TreeSet
类似于前面介绍的 HashMap 和 HashSet 之间的关系,HashSet 底层依赖于 HashMap 实现,TreeSet 底层则采用一个 NavigableMap 来保存 TreeSet 集合的元素。但实际上,由于 NavigableMap 只是一个接口,因此底层依然是使用 TreeMap 来包含 Set 集合中的所有元素。
下面是 TreeSet 类的部分源代码
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
//使用 NavigableMap的key来保存Set集合的元素
private transient NavigableMap<E,Object> m;
//使用一个PRESENT作为Map集合的所有value
private static final Object PRESENT = new Object();
//包访问权限的构造器,以指定NavigableMap对象创建Set集合
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
public TreeSet() {
//以自然排序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
//使用该TreeMap的key来保存Set集合的元素
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
//以定制排序方式创建一个新的TreeMap,根据该TreeSet创建一个TreeSet
//使用该TreeMap的key来保存Set集合的元素
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
//调用无参的构造器创建一个TreeSet,底层以TreeMap保存集合元素
this();
//向TreeSet中添加Collection集合c里的所有元素
addAll(c);
}
public TreeSet(SortedSet<E> s) {
//调用指定排序方式的构造器创建一个TreeSet,底层以TreeMap保存集合元素
this(s.comparator());
//向TreeSet中添加Collection集合c里的所有元素
addAll(s);
}
//TreeSet的其他方法都只是直接调用TreeMap的方法来提供实现
//...
//省略部分代码
public boolean addAll(Collection<? extends E> c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
//把c集合强制转换为SortedSet集合
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
//把m结合强制转换为TreeMap集合
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
//如果cc和mc两个Comparator相等
if (cc==mc || (cc != null && cc.equals(mc))) {
//把Collection中所有元素添加成TreeMap集合的key
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
//直接调用父类的addAll()方法来实现
return super.addAll(c);
}
//...
//省略部分代码
}
对于 TreeMap 而言,它采用一种被称为“红黑树”的排序二叉树来保存Map中的每个 Entry————每个 Entry 都被当成“红黑树”的一个节点对待。示例如下:
public class TreeMapTest {
public static void main(String[] args) {
TreeMap<String, Double> map = new TreeMap<>();
map.put("ccc", 89.0);
map.put("aaa", 80.0);
map.put("zzz", 80.0);
map.put("bbb", 89.0);
System.out.println(map);
}
}
当程序执行 map.put("ccc", 89.0);
时,系统将直接把 "ccc"-89.0
这个 Entry 放入 Map 中,这个 Entry 就是该红黑树的根节点。接着程序执行 map.put("aaa", 80.0);
时,会将 "aaa"-80.0
作为新节点添加到已有的红黑数中。
以后每向 TreeMap 中放入一个 Key-value 对,系统都需要将该 Entry 当成一个新节点,添加到已有红黑树中,通过这种方式就可保证 TreeMap 中所有的 key 总是由小到大地排列。例如,输出上面的程序,将看到如下结果(所有 key 由小到大地排列):{aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0}
可以形象地归纳 HashMap、HashSet 与 TreeMap 、TreeSet 两类集合。HashMap、HashSet 的储存集合元素的方式类似于“妈妈放东西”,不同的东西放在不同的位置,需要时就可以快速的找到它们;TreeMap、TreeSet 的储存集合元素的方式类似于“体育课站队”,第一个人(相当于元素)自成一个对,以后每添加一个人都要先找到这个人应该插入的位置(队伍头端的所有人比新插入的人矮,队伍尾端所有人比新插入的人高),然后在该位置插入即可。这样可以保证该队伍总是由矮到高地排列————当然,二叉排序树的算法比“体育课站队”排序方式高效多了。
对于 TreeMap 而言,由于它底层采用一颗“红黑树”来保存集合中的 Entry,这意味着 TreeMap 添加元素、取出元素的性能都比 HashMap 低。当从 TreeMap 中取出元素时,需要通过循环才能找到合适的 Entry,也比较耗性能。但 TreeMap、TreeSet 相比 HashMap、HashSet 的优势在于总是根据指定排序规则保持有序状态。
红黑树是一种自平衡二叉查找树,树中每个节点的值,都大于或等于在它的左子树中的所有节点的值,并且小于或等于在它的右子树中的所有节点的值,这确保红黑树运行时可以快速地在书中查找和定位所需节点。
对于 TreeMap 集合而言,其关键就是 put(K key, V value),该方法实现了将 Entry 放入 TreeMap 的 Entry 链,并保证该 Entry 链总是处于有序状态。下面是该方法的源代码。
public V put(K key, V value) {
//先以t保存链表的root节点
Entry<K,V> t = root;
//如果t==null,表名是一个空链表,即该TreeMap里没有任何Entry
if (t == null) {
//检查是否正确是否排序方法,而可以作为null检测
compare(key, key); // type (and possibly null) check
//将新的key-value创建一个Entry,并将该Entry作为root
root = new Entry<>(key, value, null);
size = 1;
//记录修改次数为1
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//如果比较器cpr不为null,即表名采用定制排序
if (cpr != null) {
do {
//使用parent上次循环后的t所引用的Entry
parent = t;
//拿新插入的key和t的key进行比较
cmp = cpr.compare(key, t.key);
//如果新插入的key小于t的key,t等于t的左边节点
if (cmp < 0)
t = t.left;
//如果新插入的key大于t的key,t等于t的右边节点
else if (cmp > 0)
t = t.right;
//如果两个key相等,新value覆盖原有的value,并返回原有的value
else
return t.setValue(value);
} while (t != null);
}
else {
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
//使用parent上次循环后的t所引用的Entry
parent = t;
//拿新插入的key和t的key进行比较
cmp = k.compareTo(t.key);
//如果新插入的key小于t的key,t等于t的左边节点
if (cmp < 0)
t = t.left;
//如果新插入的key大于t的key,t等于t的右边节点
else if (cmp > 0)
t = t.right;
//如果两个key相等,新value覆盖原有的value,并返回原有的value
else
return t.setValue(value);
} while (t != null);
}
//将新插入的节点作为parent节点的子节点
Entry<K,V> e = new Entry<>(key, value, parent);
//如果新插入key小于parent的key,则e作为parent的左子节点
if (cmp < 0)
parent.left = e;
//如果新插入key大于parent的key,则e作为parent的右子节点
else
parent.right = e;
//修复红黑树
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
上面的代码就是实现“排序二叉树”的关键算法。每当程序希望添加新节点时,总是从树的根节点开始比较,即将根节点当成当前节点。如果新增节点大于当前节点且当前节点的右子节点存在,则以右子节点作为当前节点;如果新增节点小于当前节点且当前节点的左子节点存在,则以左子节点作为当前节点;如果新增节点等于当前节点,则用新增节点覆盖当前节点,并结束循环————直到找到某个节点的左、右节点不存在,将新节点添加为该节点的子节点。如果新节点比该节点大,则添加右子节点;如果新街点比该节点小,则添加其为左子节点。
由于大学课程总是强调“算法 + 数据结构 = 程序”的等式,所以导致很多变成爱好者对算法、数据结构十分重视。当然笔者并不是说算法、数据结构不重要,但可能并没有大家想象的那么紧急。这个等式是很早以前提出的,那时候还没有很多高级语言可以使用,很多事情都必须由程序员自己来做,比如实现一个关联数组的结构等,因此对算法、数据结构的要求很高。今天有很多高级语言、基础库可以使用,因此对算法、数据结构的要求并没有那么高。
public V get(Object key) {
//根据指定的key取出对应的Entry
Entry<K,V> p = getEntry(key);
//返回该Entry所包含的value
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
//如果comparator不为null,表名程序采用定制排序
if (comparator != null)
//调用getEntryUsingComparator方法取出对应的key
return getEntryUsingComparator(key);
//如果key形参的值为null,抛出NullPointerException异常
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
//将key强制类型转换为Comparable实例
Comparable<? super K> k = (Comparable<? super K>) key;
//从树的根节点开始
Entry<K,V> p = root;
while (p != null) {
//拿key与当前节点的key进行比较
int cmp = k.compareTo(p.key);
//如果key小雨当前节点的key,向“左子树”搜索
if (cmp < 0)
p = p.left;
//如果key大于当前节点的key,向“右子树”搜索
else if (cmp > 0)
p = p.right;
//如果既不大于也不小于,就是找到了目标Entry
else
return p;
}
return null;
}
上面的 getEntry(Object obj)
方法也是充分利用排序二叉树的特征来搜索目标Entry。程序依然从二叉树的根节点开始,如果被搜索节点大于当前节点,程序向“右子树”搜索;如果被搜索节点小于当前节点,程序向“左子树”搜索;如果相等,那就是招到了指定节点。
当 TreeMap 里的 comparator != null
,即表名该 TreeMap 采用了定制排序。在采用定制排序的方式下,TreeMap 采用 getEntryUsingComparator(key)
方法来根据 key 获取 Entry。下面是该方法的代码:
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
K k = (K) key;
//获取该TreeMap的comparator
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//从根节点开始
Entry<K,V> p = root;
while (p != null) {
//拿key与当前节点的key进行比较
int cmp = cpr.compare(k, p.key);
//如果Key小于当前节点的key,向“左子树”搜索
if (cmp < 0)
p = p.left;
//如果Key大于当前节点的key,向“右子树”搜索
else if (cmp > 0)
p = p.right;
//如果既不大于也不小于,就是找到了目标Entry
else
return p;
}
}
return null;
}
其实 getEntry、getEntryUsingComparator 这 2 个方法的实现思路完全类似,只是前者对自然排序的 TreeMap 获取有效,后者对定制排序的 TreeMap 有效。
通过上面的源代码分析不难看出,TreeMap 这个工具类的实现其实很简单。或者说,从内部结构来看,TreeMap 本质上就是一颗“红黑树”,而 TreeMap 的每个 Entry 就是该红黑树的一个节点。
Map 和 List
前面介绍了 Map 和 Set 的相似之处,当把 Map 中的 key-value 对当成单独的集合元素来对待时,Map 和 Set 也就统一起来了。接下来依然把 Map 的 key-value 分开来对待,从另外一个角度来看,就可以把 Map 和 List 统一起来。
Map 的 values() 方法
Map 集合是一个关联数组,它包含两组值:一组是所有 key 组成的集合,因为 Map 集合的 key 不允许重复,而且 Map 不会保存 key 加入的顺序,因此这些 key 可以组成一个 Set 集合;另外一组是 value 组成的集合,因为 Map 集合的 value 完全可以重复,而且 Map 可以根据 key 来获取对应的 value,所以这些 value 可以组成一个 List 集合。
实际上,Map 的 values 方法并未返回一个 List 集合,示例如下:
public class MapValueTest {
public static void main(String[] args) {
HashMap<String, Double> scores = new HashMap<>();
scores.put("语文", 89.0);
scores.put("数学", 83.0);
scores.put("英文", 80.0);
//输出scores集合的values()方法返回值
System.out.println(scores.values());
System.out.println(scores.values().getClass());
TreeMap<String, Double> health = new TreeMap<>();
health.put("身高", 173.0);
health.put("体重", 71.2);
//输出health集合的values()方法返回值
System.out.println(health.values());
System.out.println(health.values().getClass());
}
}
输出结果:
[80.0, 83.0, 89.0]
class java.util.HashMap$Values
[71.2, 173.0]
class java.util.TreeMap$Values
从上面的结果可以看出,HashMap 和 TreeMap 2 个集合的 values() 方法返回值确实是包含 Map 中所有 value 的集合,但它们并不是 List 对象,而分别是 HashMap$Values 和 TreeMap$Values 对象。
先来看 HashMap 的 values() 方法的源代码:
public Collection<V> values() {
//获取values实例变量
Collection<V> vs = values;
//如果vs=null,将返回new Values()对象
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
再来看 TreeMap 的 values() 方法的源代码:
public Collection<V> values() {
Collection<V> vs = values;
if (vs == null) {
vs = new Values();
values = vs;
}
return vs;
}
由此可见,HashMap 和 TreeMap 这 2 个Map 类的 values() 方法的实现完全相同。当程序第一个调用这个 2 个 Map 对象的 values 方法时,它们会创建一个新的 Values 对象,并将该 Values 对象赋给 values 实例变量;当程序下次调用 values() 方法时,将直接以 values 实例变量作为返回值。
由此可见,对于 HashMap 和 TreeMap 而言,它们 values() 方法返回值的区别主要体现在各自 Values 内部类的实现上。
下面来看 HashMap 的Values 内部类的源代码:
final class Values extends AbstractCollection<V> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
public final Iterator<V> iterator() { return new ValueIterator(); }
public final boolean contains(Object o) { return containsValue(o); }
public final Spliterator<V> spliterator() {
return new ValueSpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}
注意上面这个 Values 集合类,它虽然继承了 AbstractCollection 抽象类,但不不是一个 Collection 集合。因为它并未实现 add(Object e)
方法,而且 AbstractCollection 抽象类也没有实现 add(Object e)
方法,也就是说,这个 Values 集合对象并没有真正盛装任何 Java 对象。
ValueIterator 类的实现非常简单,它是通过调用 HashMap 的 nextEntry()(JDK1.8以前)或者 nextNode()(JDK1.8) 方法来实现的。下面是该类的源代码。
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
经过上面观察可以发现,HashMap 的 values() 方法表面上返回了一个 Values 集合对象,但这个集合对象并不能添加元素。它的主要功能是用于遍历 HashMap 里的所有 value,而遍历集合的所有 value 则主要依赖于 HashIterator 的 nextEntry()(JDK1.8以前)或者 nextNode()(JDK1.8) 方法来实现。对于 HashMap 而言,每个 Entry 或 Node 都持有一个引用变量指向下一个 Entry 或 Node,因此 HashMap 实现 nextEntry() 方法非常简单。
下面是 HashIterator 的 nextNode() 方法的源代码:
final Node<K,V> nextNode() {
Node<K,V>[] t;
//获取下一个元素
Node<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
if ((next = (current = e).next) == null && (t = table) != null) {
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
与 HashMap 类似的是,TreeMap 的 values() 方法同样返回了一个 Values 对象。此处的 Values 是 TreeMap 的私有内部类,该内部类的代码如下:
class Values extends AbstractCollection<V> {
public Iterator<V> iterator() {
//已TreeMap中最小的节点创建一个ValueIterator对象
return new ValueIterator(getFirstEntry());
}
public int size() {
//调用外部类的size()实例方法的返回值作为返回值
return TreeMap.this.size();
}
public boolean contains(Object o) {
//调用外部类的containsValue(o)实例方法的返回值作为返回值
return TreeMap.this.containsValue(o);
}
public boolean remove(Object o) {
//从TreeMap中最小的节点开始搜索,不断搜索下一个节点
for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) {
//如果找到指定节点
if (valEquals(e.getValue(), o)) {
//执行删除
deleteEntry(e);
return true;
}
}
return false;
}
public void clear() {
//调用外部类的clear()方法来清空该集合
TreeMap.this.clear();
}
public Spliterator<V> spliterator() {
return new ValueSpliterator<K,V>(TreeMap.this, null, null, 0, -1, 0);
}
}
上面 Values 类与 HashMap 中 Values 类的区别不是太大,其中 size()、contains(Object o) 和 clear() 等方法也依赖于外部类 HashMap 的方法来提供实现。不过由于 TreeMap 是通过 “红黑树” 来实现的,因此上面程序中还用到了 TreeMap 提供的以下两个简单的工具类方法。
- getFirstEntry:获取 TreeMap 底层“红黑树”中最左边的“叶子节点”,也就是“红黑树”中最小的节点,即 TreeMap 中第一个节点。
- successor(Entry<K, V> t):获取 TreeMap 中指定 Entry(t) 的下一个节点,也就是“红黑树”中大于 t 节点的最小节点。
getFirstEntry() 方法实现的比较简单:程序不断搜索“左子树”,直到找到最左边的“叶子节点”。该方法的实现代码如下:
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
//不断搜索左子节点,直到p成为最左子树的叶子节点
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
successor(Entry<K, V> t) 方法实现的稍稍复杂一点,该方法实现了搜索“红黑树”中大于指定节点的最小节点,其代码如下:
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
//如果其右子树存在,搜索右子树中最小的节点(也就是右子树中最左的叶子节点)
else if (t.right != null) {
//先获取其右子节点
Entry<K,V> p = t.right;
//不断搜索左子节点,知道找到最左的叶子节点
while (p.left != null)
p = p.left;
return p;
//如果右子树不存在
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
//只要父节点存在,且ch是父节点的右节点,表明ch大于其父节点,循环一直继续,直到父节点为null,或者ch变成父节点的子节点————此时父节点大于被搜索节点
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
通过 TreeMap 提供的这个 successor(Entry<K, V> t) 静态方法,可以非常方便地、由小到大遍历 TreeMap 底层的“二叉树”。实际上,完全可以通过这个静态方法来由小到大地遍历 TreeMap 的所有元素。但 TreeMap 为了保持 Map 用法上的一致性,依然通过 Values 的 iterator() 方法来遍历 Map 中所有 value。Values 的 iterator() 方法则由 ValueIterator 提供实现,ValueIterator 类的代码非常简单,如下所示:
final class ValueIterator extends PrivateEntryIterator<V> {
ValueIterator(Entry<K,V> first) {
super(first);
}
public V next() {
//调用其父类的nextEntry()方法获取下一个Entry,再返回该Entry的value
return nextEntry().value;
}
}
对于 ValueIterator 而言,它只是简单地调用了其抽象父类 PrivateEntryIterator 的方法来实现 next() 方法。该抽象父类的代码如下:
abstract class PrivateEntryIterator<T> implements Iterator<T> {
Entry<K,V> next;
Entry<K,V> lastReturned;
int expectedModCount;
PrivateEntryIterator(Entry<K,V> first) {
expectedModCount = modCount;
lastReturned = null;
next = first;
}
public final boolean hasNext() {
return next != null;
}
final Entry<K,V> nextEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//获取e的下一个节点
next = successor(e);
lastReturned = e;
return e;
}
final Entry<K,V> prevEntry() {
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//获取e的上一个节点
next = predecessor(e);
lastReturned = e;
return e;
}
public void remove() {
if (lastReturned == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
// deleted entries are replaced by their successors
if (lastReturned.left != null && lastReturned.right != null)
next = lastReturned;
//删除指定节点
deleteEntry(lastReturned);
expectedModCount = modCount;
lastReturned = null;
}
}
上面 PrivateEntryIterator 类中有以下两个重要方法。
- nextEntry():获取当前节点的下一个节点。
- prevEntry():获取当前节点的上一个节点。
这两个方法的实现其实很简单,它们只是对 successor(Entry<K, V> t)、predecessor(Entry<K, V> t) 两个方法的包装。PrivateEntryIterator 采用 next 记录了当前正在处理的节点,然后将 next 作为参数传给 successor(Entry<K, V> t)、predecessor(Entry<K, V> t) 两个方法即可实现 nextEntry()、prevEntry() 两个方法。
归纳起来可以发现:不管是 HashMap 还是TreeMap,它们的 values() 方法都可返回其所有 value 组成的 Collection 集合————按照通常理解,这个 Collection 集合应该是一个 List 集合,因为 Map 的多个 value 允许重复。
但实际上,HashMap、TreeMap 的 values() 方法的实现要更巧妙。这两个 Map 对象 values() 方法返回的是一个不存储元素的 Collection 集合,当程序遍历 Collection 集合时,实际上就是遍历 Map 对象的 value。
HashMap 和 TreeMap的 values() 方法并未把 Map 中的 value 重新组合成一个包含元素的集合对象,这样就可以降低系统内存开销。
Map 和 List 的关系
从底层实现来看,Set 和 Map 很相似;如果从用法的角度来看,Map 和 List 也有很大的相似之处:
- Map 接口提供了 get(K key) 方法允许 Map 对象根据 key 来取得 value;
- List 接口提供了 get(int index) 方法允许 List 对象根据元素索引来取得 value。
对于 List 接口而言,它仅按照元素的加入顺序保存了系统的 Java 对象。不过,可以换一种眼光来看待 List 集合,将索引当作 Map 的 key。当换一种方式来看待 List 集合之后可以发现:List 集合也包含 2 组值,其中一组是虚拟的 int 类型的索引,另一种是 List 集合元素。从这个意义上来看,可以说 List 相当于所有的 key 都是 int 类型的 Map。
Map 和 List 底层实现上并没有太大的相似之处,只是在用法上存在一些相似之处:既可以说 List 相当于所有 key 都是 int 类型的 Map,也可以说 Map 相当于索引是任意类型的 List。
下面介绍一个 JavaScript 中对象的用法。JavaScript 的对象有点类似于 Java 的 Map 结构,也是由多个 key-value 对组成,只是习惯上把 JavaScript 对象的 key-value 称为属性名、属性值。对于 JavaScript 对象而言,除了可使用属性语法来访问属性值之外,完全可以用数组语法来访问它的属性值。
JavaScript 没有提供 List 之类的集合,也没有提供 Map 集合,如果需要在 JavaScript 变成中使用 List 集合,使用 JavaScript 数组就可以了。也就是说,JavaScript 的数组既可以代替 Java 的数组,也可以代替 Java 的 List 集合。如果需要在 JavaScript 中使用 Map 集合,使用 JavaScript 的对象就可以了,JavaScript 的对象就是多个 key-value 对组成的关联数组。
本文内容来自以下:
- 《疯狂Java 突破程序员基本功的16课》第三章 常见的 Java 集合的实现细节
- HashMap在Java1.7与1.8中的区别