Java的容器

[toc]

面试官：讲讲如何写程序Iterator/Collection/Set/Map和他们之间的关系？

Collection和Map可谓构成Java容器的两大体系，你熟知的数据结构。ArrayList、LinkedList、HashSet、HashMap、TreeSet、TreeMap、PriorityQueue、Stack都从Collection和Map实现而来。

Collection和Set中文都可以翻译成集合。但是从Java编程角度，Collection应该被翻译成容器。Set翻译成集合。

容器（Collection）是什么？

容器（Collection）是容纳数据用的。Java的容器(Collection)可以装一组对象。既然是一组对象，那么他们就应该可以被遍历(traverse)。

可以被遍历的数据是可以被迭代的(Iterable)。可以被迭代的数据，就可以使用for循环进行迭代。像下面这样:

for(var c : collections) {
    
}

实现Iterable<T>接口

可以被迭代的数据需要实现Iterable接口，而Iterable内部需要实现一个迭代器。下面这段程序，教你实现一个产生随机字符串的迭代器。第1遍理解它的时候建议你跟着我的视频一起将这段程序一行一行的敲出来，我会给你line-by-line解答。

public class RandomStringGenerator<T> implements Iterable<T> {

    private final List<T> list;

    public RandomStringGenerator(List<T> list) {
        this.list = list;
    }

    @Override
    public Iterator<T> iterator() {

        return new Iterator<T>() {
            @Override
            public boolean hasNext() {
                return true;
            }

            @Override
            public T next() {
                return list.get((int) (list.size() * Math.random()));
            }
        };
    }


    public static void main(String[] argv) {
        var list = Arrays.asList("List", "Tree", "Array");
        var gen = new RandomStringGenerator<String>(list);

        for(var s: gen) {
            System.out.println(s);
        }
        
//        var it = gen.iterator();
//        for(int i = 0; i < 100; i++) {
//            System.out.println(it.next());
//        }
    }

}

容器(Collection)接口

容器都是可以被迭代的。ArrayList、LinkedList、TreeSet、HashSet、PriorityQueue、Stack都是容器， 都可以被迭代，都可以使用for循环，直接遍历。

当然，结合不仅仅需要被迭代。比如我们会：

• 判断一个容器是不是空的isEmpty()方法
• 想知道容器的大小size()方法
• 想知道容器中有没有某个元素contains(object)。
• 将容器转化成数组toArray()方法
• 添加元素到容器add(E e)方法
• 从容器中移除一个元素remove(object) 方法
• 判断一个容器的元素是否在这个容器当中containsAll(Collection<? extends T> c)
• 从容器中移除一个容器的元素removeAll(Collection<?> c)
• 移除不在某个容器中的元素retainAll(Collection<?> c)
• 清空这个容器clear()

以上这些函数是实现容器必须实现的。

很多实现容器的数据结构。并不是直接实现Collection，而是再抽象出中间的接口。比如ArrayList的继承如下：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializ
    
    
public interface List<E> extends Collection<E> 

上面代码中，ArrayList<E>先继承于List<E>再继承于Collection<E>。

视频中会帮你分析List<E>的源程序，你也可以自己，阅读List.java 中的内容——通过IDE追踪进去。

集合(Set)

集合(Set<E>)是一种容器(Collection<E>)。这种容器。不仅仅可以用来存一组数据。而且他可以保证这一组数据没有重复。

ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, LinkedHashSet, TreeSet，ImmutableCollections.SetN这些类。都是集合。只不过他们用来容纳数据。并且保证数据不重复的手段不一样。

实现集合最重要的是给定一个元素，集合能够快速的判断这个元素是否在集合当中。所以你看到上面的所有的类并没有通过数组或者链表。来实现集合的方法。因为在数组和链表当中，查找一个元素。需要遍历整个数组和链表。这样太慢了。

所以集合可能的3类实现是树、跳表、散列表和位运算。

这里我先简单的说一下这三种结构。树和跳表通常是二分查找结构（实现集合通常是平衡的二叉搜索树，比如红黑树）；哈希表是一个映射结构。具体这三种结构。都是进阶。架构师需要掌握的。这三种结构。我会在后续的课程中和你讨论。

ConcurrentSkipListSet跳表来实现集合。HashSet、LinkedHashSet和ImmutableCollections.SetN是用散列实现集合。TreeSet用树实现集合。EnumSet是一个抽象类和工厂，实际是RegularEnumSet，里面在用位运算实现集合。（看视频……）

集合(Set)复用容器（Collection）的接口即可，只不过所有的函数都要控制一下元素的唯一性。

顺序

使用散列函数和使用树状结构实现的集合虽然性能上相近，但是树状的集合，通常是基于二叉搜索树实现的。因此遍历的时候，树状的集合可以保证顺序。下面是例子（跟随视频看更好）

@Test
public void test_order(){
    var hashSet = new HashSet<Integer>();
    hashSet.add(3);
    hashSet.add(7);
    hashSet.add(2);
    hashSet.add(81);
    System.out.println(hashSet.stream().map(x -> x.toString()).collect(Collectors.joining(",")));

    var treeSet = new TreeSet<Integer>(){
        {
            add(3);
            add(7);
            add(2);
            add(81);
        }
    };

    System.out.println(treeSet.stream().map(x -> x.toString()).collect(Collectors.joining(",")));
}

TreeSet的继承路径：

Set <—- SortedSet <—- NavigableSet <—– TreeSet

可浏览的(Navigable)

树的实现本身是一种紧密的结构。。大小相近的。元素。在物理存储上也会相近。散列的实现是一种稀疏（sparse）的结构。因此，大小相近的人数。可能会相隔很远。

通常的树可以提供一种方法。找到这个元素的前继元素。所谓前继是比这个元素小，但是离得最近的元素。比如整数10的前继是9。后继是11。

因此TreeSet通过NavigableSet提供这种能力。

• E lower(E e) 提供小于元素e的最大元素
• E floor(E e) 提供小于等于元素e的最大元素
• E higher(E e) 提供大于元素e的最大元素
• E ceiling(E e) 提供大于等于元素e的最大元素

拥有这种实现。任何一个元素的使用都会像游标一样。可以向左移，也可以向右移，我们称之为浏览的能力。当然，之所以提供浏览的能力。是因为树的结构提供浏览的能力。开销很小，速度很快。哈希表不具有这样的能力。

Null Object

TreeSet不允许null对象，因为TreeSet中的元素需要可以比较——继承于Comparable。

性能

本质上差距不大，具体我们在视频中会详细讨论。

@Test
public void test_benchmark(){

    var random = new Random();
    LinkedList<String> words = new LinkedList<>();
    for(int i = 0; i < 1000000; i++) {

        var word = random.ints(97, 123)
                .limit(12)
                .collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append)
                .toString();

        words.add(word);
    }


    var hashSet = new HashSet<String>();
    var treeSet = new TreeSet<String>();

    var start = System.currentTimeMillis();
    for(var w : words) {
        hashSet.add(w);
    }
    for(var w : words) {
        hashSet.contains(w);
    }
    System.out.println("hashSet time:" + (System.currentTimeMillis() - start));

    start = System.currentTimeMillis();
    for(var w : words) {
        treeSet.add(w);
    }
    for(var w : words) {
        treeSet.contains(w);
    }
    System.out.println("treeSet time:" + (System.currentTimeMillis() - start));
}

映射（Map）是什么？

映射(Map)是两个集合间的对应关系。在Java中的Map将键(Key)映射到值(Value)。Map在Java中是一个接口，具体的实现有很多，比如HashMap，TreeMap ,Hashtable，SortedMap等。

为了实现映射，我们需要容器存储Key，需要容器存储value，也需要容器存储key-value。一组key-value在Java中我们称之为一个条目(Entry)。

Map是不是Entry的容器？

Map最核心的功能，是根据Key查找值。因此一个Map中。不能拥有重复的Key。

当然从某种角度来看，我们可以把Map看做存储条目的容器。接口Map.Entry<K,V>表示Java中Map的条目。每一个Map内部需要实现自己的Entry。

但是这样看是片面的。因为Map的核心能力，不是提供容器而是提供快速的数据查找能力。那本质是映射，根据不同的Map实现，可能会把Entry存储到某个容器当中。也可能将Key和Value存储到两个不同的容器当中。

每个Map要求实现Set<Map.Entry<K, V>> entrySet()接口，可见Entry在Map中是以集合的形式存在（不能重复）。但是我们同样不能说Map是存储Entry的集合(Set)，这是因为，Map并没有要求一定要将Entry存储下来，可以在entrySet中动态计算Entry的集合。

所以Map不是集合，也不是容器，它是映射。Map中需要容器，需要数据结构，但是具体如何去存储、如何去查询Map并没有约束。

Map.Entry<K,V>接口

每一种Map都必须实现自己的Map.Entry<K, V>类型。

下面是，Hashtable中的一段程序，Hashtable通过内部类实现了自己的Map.Entry<K, V>。下面是具体的程序，更多的讲解我会在视频中给出。

private static class Entry<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Entry<K,V> next;

    protected Entry(int hash, K key, V value, Entry<K,V> next) {
        this.hash = hash;
        this.key =  key;
        this.value = value;
        this.next = next;
    }

    @SuppressWarnings("unchecked")
    protected Object clone() {
        return new Entry<>(hash, key, value,
                           (next==null ? null : (Entry<K,V>) next.clone()));
    }

    // Map.Entry Ops

    public K getKey() {
        return key;
    }

    public V getValue() {
        return value;
    }

    public V setValue(V value) {
        if (value == null)
            throw new NullPointerException();

        V oldValue = this.value;
        this.value = value;
        return oldValue;
    }

    public boolean equals(Object o) {
        if (!(o instanceof Map.Entry))
            return false;
        Map.Entry<?,?> e = (Map.Entry<?,?>)o;

        return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
            (value==null ? e.getValue()==null : value.equals(e.getValue()));
    }

Map<K,V>的接口

Map的接口中K代表Key的类型，V代表值的类型。

Map和容器非常的像，需要实现一些集合中也存在的接口函数。比如说：

• int size()
• boolean isEmpty()
• void clear()

另外，Map中提供了三种提取容器的方法：

• Collection<V> values()将值提取为容器。
• Set<K> keySet() 将Key提取为集合。
• Set<Map.Entry<K, V>> entrySet() 将Entry提取为集合。

上面三种方法体现的是映射的三要素。KeySet是原集合，values是目标集合,Entry是关联关系。

最后我们来看一下Map几个最重要的用途。

• boolean containsKey(Object key)查找map中有没有某个键。
• boolean containsValue(Object value)查找map中有没有某个value。
• V get(Object key)根据某一个键拿到value。
• V put(K key, V value) 写入一组Key到value的映射关系。
• V remove(Object key)相当于get和删除的结合体，拿到值删除关系。

还有批量操作:

• void putAll(Map<? extends K, ? extends V> m)这里是批量添加。

Map的实现

Map的诸多实现中有：ConcurrentHashMap, ConcurrentSkipListMap, EnumMap, HashMap, Hashtable, LinkedHashMap, Properties, TreeMap,

和集合类似Map最常的种实现如下：

• ConcurrentHashMap，HashMap、Hashtable、LinkedHashMap是基于哈希表的实现
• TreeMap是基于树的实现
• ConcurrentSkipListMap是基于跳表的实现
• EnumMap是基于位运算的实现

和集合类似，哈希表的实现是一种稀疏的结构。树的实现是一种紧密的结构。树的实现中间继承路径中会实现NavigableMap<K,V>，从而实现浏览的能力。

HashMap vs Hashtable

上面诸多实现当中HashMap和Hashtable实现非常相近。这里有2个显著的区别：

• Hashtable中的所有对用户的方法都用synchronized关键字上了锁（因此线程安全）。如果你学到了本课程后续的并发编程环节。你会知道这并不是一种好的实现方案。HashMap没有做任何控制。
• HashMap允许null key/null value； Hashtable不允许null key/null value

举例：LinkedHashMap实现LRU

所谓Linked，就是按照写入顺序在Map之外再形成一个链表。LinkedHashMap的Entry本身还是一个链表节点：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
}

这是一个双向链表，所以每个节点知道它的前一个和后一个是什么。比如说我们可以用LinkedHashMap去实现一个LRU缓存。LRU(Least Recently Used)是一种缓存置换算法。当缓存空间不足的时候，新进入的缓存条目会尝试替换掉最长时间没有被使用的条目。

LinkedHashMap同时具有哈希表和链表的特征。哈希表可以帮助利用Key存储缓存条目，链表帮助实现LRU算法。

上面例子中，如果添加一个新条目D：D->C->B->离开方向

如果再刷新条目C（再次写入，或使用）：C->D->B->离开方向

完整的代码如下：

public class LRUCache<K, V> implements Iterable<K>{

    LinkedHashMap<K, V> cache =new LinkedHashMap<>();

    public void cache(K key, V value) {
        if(cache.containsKey(key)) {
            cache.remove(key);
        }
        if(cache.size() >= 3) {
           var it = cache.keySet().iterator();
           var first = it.next();
           cache.remove(first);
        }
        cache.put(key, value);
    }
    @Override
    public Iterator iterator() {

        var it = cache.entrySet().iterator();
        return new Iterator() {
            @Override
            public boolean hasNext() {
                return it.hasNext();
            }

            @Override
            public Object next() {
                var entry = it.next();
                return entry.getKey();
            }
        };
    }


    public static void main(String[] argv) {
        var lru = new LRUCache<String, Integer>();
        lru.cache("A", 1);
        lru.cache("B", 2);
        lru.cache("C", 3);
        lru.cache("D", 4);


        lru.cache("C", 10);
        System.out.println(
                "leave <-"+
                StreamSupport.stream(lru.spliterator(), false)
                        .map(x -> x.toString())
                .collect(Collectors.joining("<-"))
        );

    }
}

总结

这节课涉及到了很多Java的数据结构。但是归根结底，其实只有两类。一类就是存储数据的容器（Collection<T>)。一类就是将数据映射到另一种数据的Map<K, V>。Map中依然要用到容器，用到Iterable。但Map的本质不是容器，而是映射。

这些数据结构。我觉得大家可以从两方面去掌握。一方面就是什么东西是什么。比如说HashMap是Hash实现的Map，TreeSet是Tree实现的Set。看似非常简单。实则非常有深意。如果我在面试求职者的过程当中，求职者能告诉我。TreeSet是Tree实现的Set，Set是结合，元素不允许重复。那对于我而言，我是听到了一个非常棒的答案。我并不希望求职者将文档再复述一遍，因为从这样的话中我看到了他简单准确的理解。如果有求职者告诉我，Map不是容器，是映射，将集合映射到集合，我就会有一种强烈录用的冲动。理解到本质都是容易的，希望你记住这句话。量子力学那么复杂可能是人类还没有真的理解。

另一个需要掌握的维度就是数据结构和算法本身。TreeSet是二叉搜索树中的红黑树，HashMap是哈希表，ConcurrentSkipListMap是跳表，EnumSet是位运算。关于数据结构维度的知识。我在本次课程当中，我会先帮你梳理到对标阿里资深工程师的水平。重点会放到哈希表和树上，更复杂的一些知识。还是需要你自己再进一步的积累。