java集合框架--Collection

容器（Collection）是什么？

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

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

实现Iterable接口

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

public class RandomStringGenerator implements Iterable {

    private final List list;

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

    @Override
    public Iterator iterator() {

        return new Iterator() {
            @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(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 c)
从容器中移除一个容器的元素removeAll(Collection c)
移除不在某个容器中的元素retainAll(Collection c) 清空这个容器clear()

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

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

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

集合(Set)

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

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

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

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

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

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

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

映射（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表示Java中Map的条目。每一个Map内部需要实现自己的Entry。

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

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

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

Map.Entry接口

每一种Map都必须实现自己的Map.Entry类型。

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

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

        protected Entry(int hash, K key, V value, Entry 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) 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的接口

每一种Map都必须实现自己的Map.Entry类型。

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

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

        protected Entry(int hash, K key, V value, Entry 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) 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的接口

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

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

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

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

Collection values()将值提取为容器。
Set keySet() 将Key提取为集合。
Set> 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 m)这里是批量添加。

Map的实现

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

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

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

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

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 extends HashMap.Node {
    Entry before, after;
}

完整的代码如下：

public class LRUCache implements Iterable{

    LinkedHashMap 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();
        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

Java相关栏目本月热门文章