“核心技术：集合”的版本间差异

来自Wikioe
跳到导航 跳到搜索
第833行： 第833行：
== 视图与包装器 ==
== 视图与包装器 ==


'''通过使用视图（views）可以获得其他的实现了Collection 接口和Map 接口的对象。'''


以“HashMap<K,V>”为例：
<syntaxhighlight lang="java">
    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }
    final class KeySet extends AbstractSet<K> {
        public final int size()                { return size; }
        public final void clear()              { HashMap.this.clear(); }
        public final Iterator<K> iterator()    { return new KeyIterator(); }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> 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.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }
</syntaxhighlight>
“keySet()”方法返回了一个实现了“Set<K>”接口的类（“KeySet”）的对象，这个类（“KeySet”）的方法可以对原HashMap进行操作，这个集合（“KeySet”）就是视图，这个对象（“ks”）就是视图对象。


== 算法 ==
== 算法 ==

2020年10月19日 (一) 02:14的版本


Java 集合框架

将集合的接口与实现分离

与现代的数据结构类库的常见情况一样， Java 集合类库也将接口（ interface ) 与实现( implementation) 分离。


以队列为例：

队列.png

队列接口的最简形式可能类似下面这样： 

public interface Queue<E> // a simplified form of the interface in the standard library
{
   void add(E element) ;
   E remove();
   int size()；
}

而，队列通常有两种实现方式：

  1. 一种是使用循环数组；
  2. 另一种是使用链表；
队列的实现.png


Colloction 接口

在Java 类库中，集合类的基本接口是Collection 接口。这个接口有两个基本方法 

public interface Collection<b
{
   boolean add(E element);
   Iterator<E> iteratorQ;
   ...
}
  1. add 方法用于向集合中添加元素。如果添加元素确实改变了集合就返回true, 如果集合没有发生变化就返回false；
  2. iterator 方法用于返回一个实现了Iterator 接口的对象；
    可以使用这个迭代器对象依次访问集合中的元素。

迭代器

关于Iterable与Iterator的那些事


Iterator 接口包含4 个方法： 

public interface Iterator<E>
{
E next();          // 逐个访问集合中的每个元素（如果到达了集合的末尾将抛出一个NoSuchElementException）
boolean hasNext();    // 遍历时判断是否还有下一个元素
void remove();      // 
default void forEachRemaining(Consumer<? super E> action) ;   // 对迭代器的每一个元素调用action（Consumer是一个函数式接口，所以可用lambda表达式）
}


如果想要査看集合中的所有元素，就请求一个迭代器，并在hasNext 返回true 时反复地调用next 方法。例如： 

Collection<String> c = . . .;
Iterator<String> iter = c.iteratorO；
while (iter.hasNextO)
{
   String element = iter.next0；
   // do something with element
}

用“ foreach” 循环可以更加简练地表示同样的循环操作： 

for (String element : c)
{
   // do something with element
}
  • 编译器简单地将“for each” 循环翻译为带有迭代器的循环，“for each”循环可以与任何实现了Iterable 接口的对象一起工作；
    Collection 接口扩展了（而非继承）Iterable 接口。因此，对于标准类库中的任何集合都可以使用“for each” 循环。
  • 在Java SE 8 中，甚至不用写循环。可以调用forEachRemaining方法并提供 lambda 表达式（它会处理一个元素）。
    将对迭代器的每一个元素调用这个lambda 表达式，直到再没有元素为止。
    i terator.forEachRemai ni ng(el ement -> do something with element);
  • 元素被访问的顺序取决于集合类型。
    如对 ArrayList：迭代器将从索引 0 开始，每次迭代索引值加 1；
    然而，如对 HashSet 迭代：每个元素将会按照某种随机的次序出现。（能够遍历到集合中的所有元素，但却无法预知元素被访问的次序）


关于迭代器的位置

应该将Java 迭代器认为是位于两个元素之间（而非指向一个元素）。当调用next 时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。
迭代器的位置.png


  • Iterator 接口的 remove 方法将会删除上次调用next 方法时返回的元素；


如：

  1. 删除集合首个元素： 
    Iterator<String> it = c.iterator();
it.nextO;        // skip over the first element
it.remove();     // now remove it
  2. 删除两个相邻的元素： 
    it.remove();
it.next0；
it.remove();

// 而非
// it.remove();
// it.remove();

泛型使用方法

  • 由于Collection 与Iterator 都是泛型接口，可以编写操作任何集合类型的实用方法。
  • Java 类库提供了一个类AbstractCollection，它将基础方法size和iterator抽象化了，但是提供了例行方法。
    所以，一个具体的集合类可以扩展AbstractCollection 类了（实际上也是这样的）
    然而，这种“伴随类”并不是最好的方式，在原接口中将方法定义为“默认方法”会更好。


java.util.Collection<E>

  1. Iterator < E> iterator()
    返回一个用于访问集合中每个元素的迭代器。
  2. int size()
    返回当前存储在集合中的元素个数。
  3. boolean isEmpty()
    如果集合中没有元素， 返回true。
  4. boolean contains(Object obj)
    如果集合中包含了一个与obj 相等的对象， 返回true。
  5. boolean containsAl 1(Collection<?> other)
    如果这个集合包含other 集合中的所有元素， 返回trueo
  6. boolean add(Object element)
    将一个元素添加到集合中。如果由于这个调用改变了集合，返回true。
  7. boolean addAl1(Col1ection<? extends E> other)
    将other 集合中的所有元素添加到这个集合。如果由于这个调用改变了集合，返回true。
  8. boolean remove(Object obj)
    从这个集合中删除等于obj 的对象。如果有匹配的对象被删除， 返回true。
  9. boolean removeAl 1(Col 1ection<?> other)
    从这个集合中删除other 集合中存在的所有元素。如果由于这个调用改变了集合，返回true。
  10. default boolean removelf(Predicate<? super E> filter)8
    从这个集合删除filter 返回true 的所有元素。如果由于这个调用改变了集合，则返回true。
  11. void clear()
    从这个集合中删除所有的元素。
  12. boolean retainAl1(Collection<?> other)
    从这个集合中删除所有与other 集合中的元素不同的元素。如果由于这个调用改变了集合， 返回true。
  13. Object[]toArray()
    返回这个集合的对象数组。
  14. <T> T[]toArray(T[]arrayToFi11)
    返回这个集合的对象数组。如果arrayToFill 足够大，就将集合中的元素填入这个数组中。剩余空间填补null; 否则，分配一个新数组，其成员类型与arrayToFill的成员类型相同，其长度等于集合的大小，并填充集合元素。

java.util.Iterator<E>

  1. boolean hasNext()
    如果存在可访问的元素， 返回true。
  2. E next()
    返回将要访问的下一个对象。如果已经到达了集合的尾部， 将拋出一个NoSuchElementException。
  3. void remove( )
    删除上次访问的对象。这个方法必须紧跟在访问一个元素之后执行。如果上次访问之后，集合已经发生了变化， 这个方法将抛出一个IllegalStateException。

集合框架中的接口

集合框架的接口.png

  1. 集合有两个基本接口：Collection 和Map。
    可以用以下方法在集合中插人元素：
    boolean add(E element)
    不过，由于映射包含键/ 值对，所以要用put 方法来插人：
    V put(K key, V value)
    要从集合读取元素， 可以用迭代器访问元素。不过，从映射中读取值则要使用get 方法：
    V get (K key)

List

List 是一个有序集合（ordered collection），元素会增加到容器中的特定位置。可以采用两种方式访问元素：

  1. 迭代器访问
  2. 随机访问（random access)


  • List 接口定义了多个用于随机访问的方法：
    void add(int index, E element)
    void remove(int index)
    E get(int index)
    E set(int index, E element)

Set

Set 接口等同于Collection 接口，不过其方法的行为有更严谨的定义：集（ set ) 的add 方法不允许增加重复的元素。

  • 要适当地定义集的equals 方法：只要两个集包含同样的元素就认为是相等的，而不要求这些元素有同样的顺序。
  • hashCode 方法的定义要保证包含相同元素的两个集会得到相同的散列码。


  • SortedSet 和SortedMap接口会提供用于排序的比较器对象，这两个接口定义了可以得到集合子集视图的方法。
  • Java SE 6 引人了接口NavigableSet和NavigableMap，其中包含一些用于搜索和遍历有序集和映射的方法。

具体的集合

Java 库中的具体集合
集合类型 描述
AbstractCollection
ArrayList 一种可以动态增长和缩减的索引序列
LinkedList 一种可以在任何位置进行高效地插人和删除操作的有序序列
ArrayDeque 一种用循环数组实现的双端队列
HashSet 一种没有重复元素的无序集合
TreeSet —种有序集
EnumSet 一种包含枚举类型值的集
LinkedHashSet 一种可以记住元素插人次序的集
PriorityQueue 一种允许高效删除最小元素的集合
AbstractMap
HashMap 一种存储键/值关联的数据结构
TreeMap —种键值有序排列的映射表
EnumMap 一种键值属于枚举类型的映射表
LinkedHashMap 一种可以记住键/值项添加次序的映射表
WeakHashMap 一种其值无用武之地后可以被垃圾回收器回收的映射表
IdentityHashMap 一种用==而不是用equals比较键值的映射表

集合框架中的类.png

链表（LinkedList）

  • 链表不支持随机方法，但便于插入删除；
  • Java中的所有链表实际上都是双向链接的（双向链表）；


添加

  1. LinkedList.add：将对象添加到链表的尾部；
  2. ListIterator.add：将对象添加到当前位置；


删除

  • （Java中删除链表元素不需要考虑内部指向，调用方法即可）
  1. 在调用 next 之后 remove，会删除迭代器左侧的元素（类似键盘的“删除”）
  2. 在调用 previous 之后 remove，删除迭代器右侧的元素（类似键盘的“DEL”）


ListItetator

  • ListItetator：Iterator的子类，专门用于LinkedList的迭代；
  • 迭代器的位置，并不直接指向元素，而是在元素之间；
  • 迭代器的 add 方法只依赖于迭代器的位置，而 remove 方法依赖于迭代器的状态（调用了next还是previous）；
  • 同一个LinkedList的多个迭代器之间操作冲突的话（一个修改了集合，一个正在读），会抛出“ConcurrentModificationException”异常。
    所以：可以更具需要给容器附加多个迭代器，但只有一个可以进行修改操作；
  • 尽量使用迭代器，而不使用 LinkedList.get方法来进行读取（效率太低）

常用方法

java.util.List<E>
  • ListIterator<E> 1 istIterator ( )
    返回一个列表迭代器， 以便用来访问列表中的元素。
  • ListIterator <E> 1 istIterator( int index )
    返回一个列表迭代器， 以便用来访问列表中的元素， 这个元素是第一次调用next 返回的给定索引的元素。
  • void add( int i , E element )
    在给定位置添加一个元素。
  • void addAl 1 ( int i , Col 1ection<? extends E> elements )
    将某个集合中的所有元素添加到给定位置。
  • E remove( int i )
    删除给定位置的元素并返回这个元素。
  • E get ( int i )
    获取给定位置的元素。
  • E set ( int i , E element )
    用新元素取代给定位置的元素， 并返回原来那个元素。
  • int indexOf (Object element )
    返回与指定元素相等的元素在列表中第一次出现的位置， 如果没有这样的元素将返回-1。
  • int 1 astlndexOf(Object element)
    返回与指定元素相等的元素在列表中最后一次出现的位置， 如果没有这样的元素将返回-1。
java.util.Listlterator<E>
  • void add(E newElement)

在当前位置前添加一个元素。

  • void set(E newElement)
    用新元素取代next 或previous 上次访问的元素。如果在next 或previous 上次调用之后列表结构被修改了， 将拋出一个IllegalStateException 异常。
  • boolean hasPrevious()
    当反向迭代列表时， 还有可供访问的元素， 返回true。
  • E previous()
    返回前对象。如果已经到达了列表的头部， 謝te出一hNoSuchElementException 异常。
  • int nextlndex()
    返回下一次调用next 方法时将返回的元素索引。
  • int previousIndex()
    返回下一次调用previous 方法时将返回的元素索引。


java.util.LinkedList<E>
  • LinkedList()
    构造一个空链表。
  • LinkedList(Col 1ection<? extends E> elements)
    构造一个链表， 并将集合中所有的元素添加到这个链表中。
  • void addFirst(E element)
  • void addLast(E element)
    将某个元素添加到列表的头部或尾部。
  • E getFirst()
  • E getLast()
    返回列表头部或尾部的元素。
  • E removeFirst()
  • E removeLast()
    删除并返回列表头部或尾部的元素。

数组列表（ArrayList）

List的数组实现，支持随机读取，不便于插入删除（需要移动元素）。

ArrayList 与 Vector

Vector 类的所有方法都是同步的，可以由两个线程安全地访问一个 Vector 对象，但也比 ArrayList 更耗时；

  • Vector 的方法中，用到了synchronized来实现同步锁；

散列集（HashSet）

利用对象的hashcode，来将对象存放在散列集的不同位置。


  • HashSet 的迭代器将依次访问所有的桶。由于元素散列分布，所以迭代器访问元素是无序的；
  • 修改元素时，如果元素的散列码变化，则其在数据结构中的位置也会变化


HashSet的实现：

  • 由其构造函数可以看出，HashSet 是由 HashMap 来实现的： 
    public HashSet() {
	map = new 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);
}

散列表

散列表，用于保存集合中对象的散列码。Java中，散列表用链表数组实现：

散列表.png

（每个列表被称为一个桶，bucket） 要想査找表中对象的位置，就要先计算它的散列码，然后与桶的总数取余，所得到的结果就是保存这个元素的桶的索引。

例如， 如果某个对象的散列码为76268, 并且有128个桶， 对象应该保存在第108号桶中（76268除以128余108)

散列冲突

插入对象时，遇到桶被占满的情况，即为散列冲突。
这时， 需要用新对象与桶中的所有对象进行比较， 査看这个对象是否已经存在。如果散列码是合理且随机分布的， 桶的数目也足够大， 需要比较的次数就会很少。

  • 在JavaSE 8 中， 桶满时会从链表变为平衡二叉树（便于查找？）。

桶数

桶数，是指用于收集具有相同散列值的桶的数目。通常，将桶数设置为预计元素个数的75% ~ 150%。

  • 标准类库使用的桶数是2 的幂， 默认值为16

再散列

如果散列表太满，就需要再散列（rehashed)：创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。


装填因子（load factor) 决定何时对散列表进行再散列。
例如， 如果装填因子为0.75 (默认值)，而表中超过75%的位置已经填人元素， 这个表就会用双倍的桶数自动地进行再散列。


  • 对于大多数应用程序来说， 装填因子为 0.75 是比较合理的；

常用方法

jjava.util.HashSet<E>
  • HashSet ( )
    构造一个空散列表。
  • HashSet (Col 1ection<? extends E> elements )
    构造一个散列集， 并将集合中的所有元素添加到这个散列集中。
  • HashSet ( int initialCapacity)
    构造一个空的具有指定容量（桶数）的散列集。
  • HashSet ( int initialCapacity , float 1oadFactor )
    构造一个具有指定容量和装填因子（一个0.0 ~ 1.0 之间的数值， 确定散列表填充的百分比， 当大于这个百分比时， 散列表进行再散列）的空散列集。
java.Iang.Object
  • int hashCode( )
    返回这个对象的散列码。散列码可以是任何整数，包括正数或负数。equals 和hashCode的定义必须兼容，即如果x.equals(y) 为true, x.hashCodeO 必须等于y.hashCodeO。

树集（TreeSet）

树集是一个有序集合(sorted collection)。元素的排序是用树结构完成的（当前使用的是红黑树）；

  • 使用树集，元素必须实现 Comparable 接口，或者构造集时必须提供一个 Comparator。
  • Java6 之后，TreeSet类实现了 NavigableSet 接口。
    这个接口增加了几个便于定位元素以及反向遍历的方法。

每次将一个元素添加到树中时，都被放置在正确的排序位置上。因此：

  1. 迭代器总是以排好序的顺序访问每个元素。
  2. 添加插入较HashSet慢，但查找更快。
  3. 如果树中包含 n 个元素，査找新元素的正确位置平均需要“log2 n”次比较。


TreeSet的实现：

  • 由其构造函数可以看出，TreeSet 是由 TreeMap 来实现的： 
    public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * The backing map.
     */
    private transient NavigableMap<E,Object> m;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }

    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }
	
	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) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

常用方法

java.util.TreeSet<E>

TreeSet()

  • TreeSet(Comparator<? super E> comparator)
    构造一个空树集。
  • TreeSet(Col 1ection<? extends E> elements)
  • TreeSet(SortedSet<E> s)
    构造一个树集， 并增加一个集合或有序集中的所有元素（对于后一种情况，要使用同样的顺序)。
java.util.SortedSet<E>
  • Comparator<? super E> comparator()
    返回用于对元素进行排序的比较器。如果元素用Comparable 接口的compareTo方法进行比较则返回null。
  • E firstO
  • E 1ast()
    返回有序集中的最小元素或最大元素。
java.util.NavigableSet<E>
  • E higher(E value)
  • E 1ower(E value)
    返回大于value 的最小元素或小于value 的最大元素，如果没有这样的元素则返回null。
  • E cei1ing(E value)
  • E floor(E value)
    返回大于等于vaiue 的最小元素或小于等于value 的最大元素， 如果没有这样的元素则返回null。
  • E pollFirst()
  • E pol1Last()
    删除并返回这个集中的最大元素或最小元素， 这个集为空时返回null。
  • Iterator<E> descend *ngIterator()
    返回一个按照递减顺序遍历集中元素的迭代器。

队列（Queue）双端队列（Deque）

在Java SE 6 中引人了Deque 接口，ArrayDeque和LinkedList类实现了Deque接口。这两个类都提供了双端队列， 而且在必要时可以增加队列的长度。 

public interface Deque<E> extends Queue<E> {

public interface Queue<E> extends Collection<E> {


  • （在第14章将会看到有限队列和有限双端队列。）
  • （看看消息中间件的实现？）

阻塞队列（BlockingQueue）

BlockingQueue<E> 接口扩展了 Queue<E>接口，用于阻塞队列的实现。

Java中的阻塞队列

常用方法

java.utii.Queue<E>
  • boolean add(E element )
  • boolean offer(E element )
    如果队列没有满，将给定的元素添加到这个双端队列的尾部并返回true。如果队列满了，第一个方法将拋出一个IllegalStateException, 而第二个方法返回false。
  • E remove( )
  • E poll ( )
    假如队列不空， 删除并返回这个队列头部的元素。如果队列是空的，第一个方法抛出NoSuchElementException, 而第二个方法返回null。
  • E elementC )
  • E peek( )
    如果队列不空，返回这个队列头部的元素， 但不删除。如果队列空，第一个方法将拋出一个NoSuchElementException, 而第二个方法返回null。
java.util.Deque<E>
  • void addFirst(E element )
  • void addLast(E element )
  • boolean offerFirst(E element )
  • boolean offerLast( E element )
    将给定的对象添加到双端队列的头部或尾部。如果队列满了，前面两个方法将拋出一个IllegalStateException，而后面两个方法返回false。
  • E removeFirst( )
  • E removeLast( )
  • E pollFirstO
  • E pollLastO
    如果队列不空，删除并返回队列头部的元素。如果队列为空，前面两个方法将拋出一个NoSuchElementException, 而后面两个方法返回null。
  • E getFirstO
  • E getLastO
  • E peekFirstO
  • E peekLast( )
    如果队列非空，返回队列头部的元素， 但不删除。如果队列空，前面两个方法将拋出一个NoSuchElementException, 而后面两个方法返回null。
java.util.ArrayDeque<E>
  • ArrayDeque( )
  • ArrayDeque( 1nt initialCapacity)
    用初始容量16 或给定的初始容量构造一个无限双端队列。

优先级队列（priority queue）

优先级队列（priority queue) 中的元素可以按照任意的顺序插人，却总是按照排序的顺序进行检索。

  • 无论何时调用remove 方法， 总会获得当前优先级队列中最小的元素。
  • 优先级队列使用堆（heap)，对树执行添加（add) 和删除（remore) 操作，让最小的元素移动到根，而不必花费时间对元素进行排序。
    堆是一个可以自我调整的二叉树；
  • 与TreeSet—样，一个优先级队列既可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供的Comparator对象。


  • 使用优先级队列的典型示例是任务调度。

常用方法

java.util.PriorityQueue
  • PriorityQueue()
  • PriorityQueue(int initialCapacity)
    构造一个用于存放Comparable 对象的优先级队列。
  • Pr1orityQueue(int initialCapacity, Comparator ? super E> c)
    构造一个优先级队列， 并用指定的比较器对元素进行排序。

映射

基本映射操作

Java 类库为映射提供了两个通用的实现：HashMap 和TreeMap。这两个类都实现了Map 接口。

  1. 散列映射对键进行散列，
  2. 树映射用键的整体顺序对元素进行排序， 并将其组织成搜索树。
  • 散列或比较函数只能作用于键。与键关联的值不能进行散列或比较。

常用方法

java.util.Map<K, V>
  • V get(Object key)
    获取与键对应的值；返回与键对应的对象，如果在映射中没有这个对象则返回null。键可以为null。
  • default V getOrDefault(Object key, V defaultValue)
    获得与键关联的值； 返回与键关联的对象， 或者如果未在映射中找到这个键， 则返回defaultValue。
  • V put(K key, V value)
    将键与对应的值关系插入到映射中。如果这个键已经存在， 新的对象将取代与这个键对应的旧对象。这个方法将返回键对应的旧值。如果这个键以前没有出现过则返回null。键可以为null， 但值不能为null。
  • void putAl 1(Map<? extends K , ? extends V> entries)
    将给定映射中的所有条目添加到这个映射中。
  • boolean containsKey(Object key)
    如果在映射中已经有这个键， 返回true。
  • boolean containsValue(Object value)
    如果映射中已经有这个值， 返回true。
  • default void forEach(BiConsumer<? super K ,? super V> action)8
    对这个映射中的所有键/ 值对应用这个动作。
java.utii.HashMap<K,V>
  • HashMap()
  • HashMap(int initialCapacity)
  • HashMap(int initialCapacity, float 1oadFactor)
    用给定的容量和装填因子构造一个空散列映射（装填因子是一个0.0 〜1.0 之间的数值。这个数值决定散列表填充的百分比。一旦到了这个比例，就要将其再散列到更大的表中）。默认的装填因子是0.75。
java.util.TreeMap<K,V>
  • TreeMap()
    为实现Comparable 接口的键构造一个空的树映射。
  • TreeMap(Comparator<? super K> c)
    构造一个树映射， 并使用一个指定的比较器对键进行排序。
  • TreeMap(Map<? extends K, ? extends V> entries)
    构造一个树映射， 并将某个映射中的所有条目添加到树映射中。
  • TreeMap(SortedMap<? extends K, ? extends V> entries)
    构造一个树映射， 将某个有序映射中的所有条目添加到树映射中， 并使用与给定的有序映射相同的比较器。
java.util.SortedMap<K, V>
  • Comparator< ? super K> comparator()
    返回对键进行排序的比较器。如果键是用Comparable 接口的compareTo 方法进行比较的，返回null。
  • K firstKeyO
  • K 1astKey()
    返回映射中最小元素和最大元素。

更新映射项

以“使用一个映射统计一个单词在文件中出现的频度”为例：

  1. 看到一个单词（word) 时，将计数器增1， 如下所示： 
    counts.put(word, counts.get(word)+ 1);
    这是可以的， 不过有一种情况除外： 就是第一次看到word 时。在这种情况下，get 会返回null , 因此会出现一个NullPointerException 异常。
    作为一个简单的补救， 可以使用getOrDefault 方法：
    counts,put(word, counts.getOrDefault(word, 0)+ 1);
  2. 另一种方法是首先调用putlfAbsent 方法。只有当键原先存在时才会放入一个值。 
    counts.putlfAbsent(word, 0);
counts.put(word, counts.get(word)+ 1); // Now we know that get will succeed
  3. 不过还可以使用 merge 方法简化这个常见的操作。如果键原先不存在，下面的调用： 
    counts.merge(word, 1, Integer::sum);
    将把word 与1 关联，否则使用Integer::sum 函数组合原值和1 (也就是将原值与1 求和)。

映射视图（键集、键/值对集）

集合框架不认为映射本身是一个集合。（其他数据结构框架认为映射是一个 键/值 对集合，或者是由键索引的值集合）。不过，可以得到映射的视图（ View )——这是实现了Collection 接口或某个子接口的对象。

三种视图如下：

视图 命令 示例
键集 Set<K> keySet() 
Set<String> keys = map.keySet();
for (String key : keys)
{
   // do something with key
}
值集合 Collection<V> values()
  • （不是一个集，因为可以重复）
键/值对集 Set<Map.Entry<K, V>> entrySet() 
for (Map.Entry<String, Employee〉entry : staff.entrySet())
{
   String k = entry.getKeyO；
   Employee v = entry.getValueO;
   // do something with k, v
}
  • 条目集的元素是实现Map.Entry 接口的类的对象。
  • 如果在“键集”视图上调用迭代器的remove方法，会从映射中删除这个键和与它关联的值；如果试图调用add 方法， 它会抛出一个UnsupportedOperationException。
  • 原先“键/值对集”是访问所有映射条目的最高效的方法。如今，只需要使用forEach方法（使用lambda表达式）：
counts.forEach((k， v) -> {
      // do something with k, v
   })；

常用方法

java.util.Map<K, V>
  • Set<Map.Entry<K, V>> entrySet()
    返回Map.Entry 对象（映射中的键/ 值对）的一个集视图。可以从这个集中删除元素，它们将从映射中删除，但是不能增加任何元素。
  • Set<K> keySetO
    返回映射中所有键的一个集视图。可以从这个集中删除元素，键和相关联的值将从映射中删除， 但是不能增加任何元素。
  • Col 1ection<V> values()
    返回映射中所有值的一个集合视图。可以从这个集合中删除元素， 所删除的值及相应的键将从映射中删除， 不过不能增加任何元素。
java.util.Map.Entry<K, V>
  • K getKey()
  • V getValueC)
    返回这一条目的键或值。
  • V setVa1 ue(V newValue)
    将相关映射中的值改为新值， 并返回原来的值。

弱散列映射

【？？？】

链接散列集与映射（LinkedHashSet 与 LinkedHashMap）

LinkedHashSet 和 LinkedHashMap 类用来记住插人元素项的顺序。这样就可以避免在散列表中的项从表面上看是随机排列的。当条目插入到表中时，就会并人到双向链表中。
  • LinkedHashSet 由 LinkedHashMap 实现；
  • LinkedHashMap在HashMap的基础上，采用双向链表（doubly-linked list）的形式将所有entry连接起来，这样是为保证元素的迭代顺序跟插入顺序相同。

LinkedHashMap.png

特点：

  • 散列表（HashMap）用于元素的存储结构；
  • 双向链（List）表用于维护元素的迭代顺序，用于元素遍历（可以是插入顺序，也可以是访问顺序）；


关于“迭代顺序”：“插入顺序”“访问顺序”

如上所述，迭代（遍历） LinkedHashMap 元素的时候，会按照链接顺序（即：迭代顺序）进行。
而迭代顺序：

  1. 可以是“插入顺序”：按插入顺序维护链表；
  2. 也可以是“访问顺序”：按访问顺序维护链表（即链表头元素是“最近最少使用”）；


而这取决于其“accessOrder”值域：

  1. 构造对象时，确定 accessOrder： 
    	public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

    public LinkedHashMap(int initialCapacity) {
        super(initialCapacity);
        accessOrder = false;
    }

    public LinkedHashMap() {
        super();
        accessOrder = false;
    }

    public LinkedHashMap(Map<? extends K, ? extends V> m) {
        super();
        accessOrder = false;
        putMapEntries(m, false);
    }

    public LinkedHashMap(int initialCapacity,
                         float loadFactor,
                         boolean accessOrder) {
        super(initialCapacity, loadFactor);
        this.accessOrder = accessOrder;
    }
  2. 调用相关方法时，用accessOrder值判断，是否将被访问的元素放到链表末尾； 
    	public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }
	...
	void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

枚举集与映射（EnumSet 与 EnumMap）

EnumSet

EmimSet 是一个枚举类型元素集的高效实现。由于枚举类型只有有限个实例，所以EnumSet 内部用位序列实现。如果对应的值在集中，则相应的位被置为1。
  • EnumSet 类没有公共的构造器。可以使用静态工厂方法构造这个集： 
    enum Weekday { MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY, SUNDAY };
EnumSet<Weekday> always = EnumSet.allOf(Weekday.class);
EnumSet<Weekday> never = EnumSet.noneOf(Weekday.class);
EnumSet<Weekday> workday = EnumSet.range(Weekday.MONDAY, Weekday.FRIDAY);
EnumSet<Weekday> mwf = EnumSet.of(Weekday.MONDAY, Weekday.WEDNESDAY, Weekday.FRIDAY);
  • 可以使用Set 接口的常用方法来修改EnumSet。

EnumMap

EnumMap 是一个键类型为枚举类型的映射。它可以直接且高效地用一个值数组实现。

  • 在使用时， 需要在构造器中指定键类型： 
    EnumMap<Weekday, Employee〉personlnCharge = new EnumMap<>(Weekday.class);
  • 所有的枚举类型都扩展于泛型Enum 类。
    例如，Weekday 扩展于 Enum<Weekday〉。

标识散列映射（IdentityHashMap）

   类 IdentityHashMap 有特殊的作用。在这个类中， 键的散列值不是用hashCode 函数计算的， 而是用System.identityHashCode 方法计算的。这是Object.hashCode 方法根据对象的内存地址来计算散列码时所使用的方式。而且， 在对两个对象进行比较时，IdentityHashMap 类使用==, 而不使用equals。
   也就是说，不同的键对象，即使内容相同，也被视为是不同的对象。在实现对象遍历算法（如对象串行化）时，这个类非常有用，可以用来跟踪每个对象的遍历状况。

特点：

  1. 使用“System.identityHashCode”方法计算其 hashcode（即，使用对象内存地址计算 hashcode）；
  2. 使用“==”来比较对象；

即，每个对象 hashcode （几乎）唯一，（几乎）不会出现冲突。


用法？？？

视图与包装器

通过使用视图（views）可以获得其他的实现了Collection 接口和Map 接口的对象。

以“HashMap<K,V>”为例： 

    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

    final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {
            return removeNode(hash(key), key, null, false, true) != null;
        }
        public final Spliterator<K> spliterator() {
            return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> 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.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

“keySet()”方法返回了一个实现了“Set<K>”接口的类（“KeySet”）的对象，这个类（“KeySet”）的方法可以对原HashMap进行操作，这个集合（“KeySet”）就是视图，这个对象（“ks”）就是视图对象。

算法

遗留的集合

取自“http://wiki.eijux.com/index.php?title=核心技术：集合&oldid=1241”