登录后台

页面导航

本文编写于 1290 天前,最后修改于 264 天前,其中某些信息可能已经过时。

Set 和 Map

Set 代表一种集合元素无序、集合元素不可重复的集合,Map则代表一种由多个 key-value 对组成的集合,Map 集合类似于传统的关联数组。表面上看它们之间相似性很少,但实际上 Map 和 Set 之间有莫大的关联,可以说,Map 集合是 Set 集合的扩展。

Set 和 Map 的关系

set_map_extends

再看 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 即可。

set_map_key_value

对于一个 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 对组成的关联数组。

本文内容来自以下:

  1. 《疯狂Java 突破程序员基本功的16课》第三章 常见的 Java 集合的实现细节
  2. HashMap在Java1.7与1.8中的区别