Java核心技术学习--第七天

第九章 集合Java集合框架将集合的接口与实现分离Collection接口迭代器泛型使用方法集合框架中的接口 具体的集合链表数组列表散列集树集队列与双端队列优先级队列 映射基本映射操作更新映射项映射视图弱散列映射链接散列集与映射枚举集与映射标识散列映射 视图与包装器轻量级集合包装器子范围不可修改的视图同步视图受查视图关于可选操作的说明

第九章 集合

Java集合框架

将集合的接口与实现分离

public interface Queue<E> { void add(E element); E remove(); int size(); }

队列实现方式，一种是使用循环数组，另一种是使用链表。 循环数组队列使用ArrayDeque类，链表队列使用LinkedList类。都实现了Queue接口。 循环数组是有界集合，容量有限，如果对象数量没有上限，最好使用链表。

Collection接口

public interface Collection<E> { boolean add(E element); Iterator<E> iterator(); }

迭代器

public interface Iterator<E> { E next(); boolean hasNext(); void remove(); } Iterator<String> iter = c.iterator(); while(iter.hasNext()) { String element = iter.next(); } for(String element:c) { }

for each可以跟任何实现了Iterable接口的对象一起。 将迭代器认为是位于两个元素之间。 调用next时，迭代器越过下一个元素，并返回刚刚越过那个元素的引用。 remove会删除上次调用next时返回的元素。

泛型使用方法

Collection和Iterator都是泛型接口。 java.util.Collection

Iterator iterator()int size()boolean isEmpty()boolean contains(Object obj)boolean containsAll(Collection<?> other)boolean add(Object element)boolean addAll(Collection<? extends E> other)boolean remove(Object obj)boolean removeAll(Collection<?> other)default boolean removeIf(Predicate<? super E> filter)void clear()boolean retainAll(Collection<?> other) 删除与other集合中元素不同的元素，改变了集合返回trueObject[] toArray() 返回这个集合的对象数组 T[] toArray(T[] arrayToFill)

java.util.Iterator

boolean hasNext()E next()void remove()

集合框架中的接口

集合两个基本接口：Collection和Map 映射使用put方法插入

V put(K key, Value)

读取值使用get方法

V get(K key)

Set接口等同于Collection接口，但是不允许增加重复元素。只要两个集合包含相同元素就认为相等。

具体的集合

链表

所有链表都是双向链接的。 Iterator接口没有add方法，但是ListIterator有，不返回boolean值，默认改变成功。 add方法在迭代器位置之前添加一个新对象。

java.util.List

ListIterator listIterator() 返回一个列表迭代器ListIterator listIterator(int index) 返回一个列表迭代器，以便访问列表中的元素，这个元素是第一次调用next返回的给定索引的元素void add(int i, E element) 在给定位置添加一个元素void addAll(int i, Collection<? extends E> elements)E remove(int i)E get(int i)E set(int i, E element)int indexOf(Object element)int lastIndexOf(Object element)

java.util.ListIterator

void add(E newElement)void set(E element)boolean hasPrevious()E previous()int nextIndex()int previousIndex()

java.util.LinkedList

LinkedList()LinkedList(Collection<? extends E> elements)void addFirst(E element)void addLast(E element)E getFirst()E getLast()E removeFirst()E removeLast()

数组列表

访问元素：一种是用迭代器，一种是用get和set方法随机访问每个元素，不适用链表，但是对数组很有用。 不需要同步时使用ArrayList而不是Vector。

散列集

无法控制元素出现的次序，但是可以快速查找元素。比如散列表。 散列表为每个对象计算一个整数，称为散列码。 散列表用链表数组实现，每个列表被称为桶。 查找表中对象的位置，首先计算散列码，然后与桶的总数取余，得到的结果就是保存这个元素的桶的索引。 桶被占满的情况为散列冲突。 如果散列表太慢，就需要再散列。填装因子决定何时对散列表进行再散列。

java.util.HashSet

HashSet()HashSet(Collection<？ extends E> elements)HashSet(int initialCapacity)HashSet(int initialCapacity, float loadFactor)

java.lang.Object

int hashCode()

树集

树集是一个有序集合。使用的红黑树结构。 将一个元素添加到树中比添加到散列表中慢。 使用树集，必须能够比较元素，元素必须实现Comparable接口，或者构造集时提供Comparator。

java.util.TreeSet

TreeSet()TreeSet(Comparator<? super E> comparator)TreeSet(Collection<? extends E> elements)TreeSet(SortedSet s)

java.util.SortedSet

Comparator<? super E> comparator()E first()E last()

java.util.NavigableSet

E higher(E value)E lower(E value)E ceiling(E value)E floor(E value)E pollFirst()E pollLast()Iterator descendingIterator()

队列与双端队列

双端队列：有两个端头的队列。

java.util.Queue

boolean add(E element) 队列满了抛出异常boolean offer(E element) 队列满了返回falseE remove() 队列空的抛出异常E poll() 队列空的返回nullE element() 返回头部元素但不删除，队列空则抛出异常E peek() 返回头部元素但不删除，队列空则返回null

java.util.Deque

void addFirst(E element)void addLast(E element)void offerFirst(E element)void offerLast(E element)E removeFirst()E removeLast()E pollFirst()E pollLast()E getFirst()E getLast()E peekFirst()E peekLast()

java.util.ArrayDeque

ArrayDeque()ArrayDeque(int initialCapacity)

优先级队列

可以按任意顺序插入，但是按排序的顺序进行检索。 优先级队列使用了堆。 堆是一个可以自我调整的二叉树，让最小的元素移动到根，而不必花时间对元素进行排序。 可以保存实现了Comparable接口的类对象，也可以保存在构造器中提供的Comparator对象。 java.util.PriorityQueue

PriorityQueue()PriorityQueue(int initialCapacity)PriorityQueue(int initialCapacity, Comparator<? super E> c)

映射

基本映射操作

映射两个通用的实现：HashMap和TreeMap 散列映射对键进行散列，树映射用键的整体顺序对元素进行排序，并组织成搜索树。 散列或比较函数只能作用于键。 迭代处理映射的键和值，最容易的方法是使用forEach方法。

scores.forEach((k, v) -> ....)

java.util.Map

V get(Object key)default V getOrDefault(Object key, V defaultVaule)V put(K key, V value)void putAll(Map<？ extends K, ? extends V> entries)boolean containsKey(Object key)boolean containsVaule(Object value)

java.util.HashMap

HashMap()HashMap(int initialCapacity)HashMap(int initialCapacity, float loadFactor)

java.util.TreeMap<K, V>

TreeMap()TreeMap(Comparator<? super K> c)TreeMap(Map<? extends K, ? extends V> entries)

java.util.SortedMap<K, V>

Comparator<? super K> comparator()K firstKey()K lastKey()

更新映射项

映射视图

三种视图：键集、值集和键值对集

Set<K> keySet() Collection<V> values() Set<Map.Entry<K, V>> entrySet()

java.util.Map.Entry<K,V>

K getKey()V getValue()V setValue(V newValue)

弱散列映射

垃圾回收器回收弱引用引用的对象， 将弱引用放入队列。

链接散列集与映射

LinkedHashSet和LinkedHashMap用来记住插入元素项的顺序。 每次调用get或put，受到影响的条目将从当前位置删除，并放到条目链表尾部。 链接散列映射用访问顺序而不是插入顺序，对映射条目进行迭代。 访问顺序对于实现高速缓存的“最近最少使用”原则十分重要。

枚举集与映射

键类型为枚举类型。

标识散列映射

键的散列值不使用hashCode函数计算，两个对象比较时使用==。

视图与包装器

轻量级集合包装器

子范围

第一个索引包含在内，第二个索引不包含在内。

不可修改的视图

同步视图

受查视图

关于可选操作的说明