JAVA核心技术卷I（集合）

一、集合框架

1.1 Collection 接口

List、Set、Queue都实现了该接口，因此能用该接口的一些方法：

获取迭代器

Iterator< E> iterator()

获取大小，判空

int size()
boolean isEmpty()

包含

boolean contains(Object obj)
boolean containsAll(Collection<?> c)

判断相等

boolean equals(Object other)

添加

boolean add(E element)
boolean addAll(Collection<? extends E> from)

删除

boolean remove(Object obj)
boolean removeAll(Collection<? extends E> c)
void clear()
boolean retainAll(Collection<? extends E> c)：取交集：删除c中不存在的元素

转数组

Object toArray()：不推荐！这样会造成泛型丢失
<T> T[] toArray(T[] arrayToFill)：推荐！

1.2 迭代器

Iterator 接口包含4个方法：

java

public interface Iteerator<E> {
    E next();
    boolean hasNext();
    void remove();
    default void forEachRemainning(Consumer<? supper E> action);
}

调用next，指向元素中间的位置。返回的是中间位置之前的那个元素。

for each循环，编译器简单地转换为带有迭代器的循环。

二、集合

2.1 链表

有数组、链表实现两种方式。

2.1.1 List（ArrayList实现了该接口）

获取列表迭代器

ListIterator< E> listIterator()：返回一个列表迭代器
ListIterator< E> listIterator(int index)：第一次调用这个迭代器的next会返回给定索引的元素

添加

void add(int i, E element)
void addAll(int i, Collection<? extend E> c)：指定位置插入集合中所有元素

删除

E remove(int i)：删除并返回

获取

E get(int i)

设置

E set(int i, E element)

查找

int indexOf(Object element)
int lastIndexOf(Object element)

2.1.2 ListIterator

添加

void add(E newElement)：再当前位置添加一个元素

设置

void set(E newElement)：新元素替换next或previous访问的上一个元素

反向迭代

boolean hasPrevious()：反向迭代列表
E previous()：返回前一个对象

下一次迭代的索引

int nextIndex()：返回下一次调用next方法时返回的元素的索引
int previousIndex()

2.1.3 LinkedList

构造

LinkedList()
LinkedList(Collection<? extends E> c)

添加

void addFirst(E element)
void addLast(E element)

获取

E getFirst()
E getLast()

删除并返回

E removeFirst()
E removeLast()

2.1.4 Vector

和ArrayList一样，不过是线程安全的。

2.2 散列集

JAVA中散列表用链表数组实现。每个列表被称为桶。查找表中的数据，就要先计算散列码。（Java8中，桶满的时候会虫链表转为平衡二叉树）。装填因子默认为0.75，达到75%的使用，会重新扩容。

2.2.1 HashSet

HashSet()
HashSet(Collection<? extends E> elements)
HashSet(int initaialCapacity)：阿里规范推荐16

2.2.2 TreeSet（有序,有下面所有set的方法）

构造

TreeSet()
TreeSet(Comparator<? extends E> comparator)
TreeSet(Collection<? extends E> elements)
TreeSet(SortedSet< E> s)：构造一个树集，并添加一个集合或有序集中的所有元素

2.2.3 SortedSet

Comparator<? extends E> comparator()：返回用于对元素进行排序的比较器

获取最大小元素

E first()
E last()

返回有序集中最小元素或最大元素

2.2.4 NavigableSet

> 或 <

E higher(E value)
E lower(E value)

返回大于value的最小元素或小于value的最大元素，如果没有返回null

>= 或 <=

E ceiling(E value)
E floor(E value)

返回大于等于value的最小元素或小于等于value的最大元素，如果没有返回null

删除并返回最大小元素

E pollFirst()
E pollLast()

返回并删除最大最小元素

递减遍历迭代器

Iterator< E> descendingIterator()

返回一个按照递减循序遍历的迭代器

2.3 队列和双端队列

ArrayDeque和LinkedList类实现了这个接口。（我觉得吧，还是直接用LinkedList把）

2.3.1 Queue

尾部添加

boolean add(E element)
boolean offer(E element)

如果队列满了，第一个异常，第二个返回false

返回头部并删除

E remove()
E poll()

如果队列为空，第一个异常，第二个返回null

返回头部不删除

E element()
E peek()

如果队列为空，第一个异常，第二个null

2.3.2 Deque

双端队列，就是再上面的基础上多了后缀First和Last，那还不如用链表。

2.3.3 PriorityQueue 优先队列

就是最小/大堆结构（二叉树）。

PriorityQueue()
PriorityQueue(int initalcapacity)
PriorityQueue(int initalcapacity, Compatator<? super E> c)：指定比较器（可以自定义最小值定义）
add
isEmpty
remove：返回最小值

2.4 映射

K-V对

2.4.1 Map

V get(Object key)
default V getOrDefault(Object key, V defaultValue)

根据Key获取值，如果Key不存在，返回默认值。
V put(K key, V value)

如果值已经存在返回修改前的值，不存在返回null
void putAll(Map<? extends K, ? extends V> entries)
boolean containsKey(Object key)
boolean containsValue(Object value)
default void forEach(lambda表达式)

2.4.2 HashMap

推荐默认容量16

2.4.3 TreeMap(有序)

和TreeSet差不多把

K firstKey()
K lastKey()

2.4.4 映射视图

视图中进行的操作，等同于再原映射中进程的操作。

Set<Map.Entry<K, V>> entrySet()
- Map.Entry（遍历可以直接用forEach）
  - K getKey()
  - V getValue()
  - V setValue(V newValue)
Set< K> keySet()
Collection< V> valus()

2.5 栈

扩展了Vector类，不太满意。

E push(E item)
E pop()
E peek()

三、算法

java.util.Collections

static void sort(List< T> elements)
static void shuffle(List<?> elements)
static void reverse(List<?> list)
min
max
copy
fill
addAll
replaceAll
indexOfSubList
lastIndexOfSubList
swap
ratate
frequency：返回c中与对象o相等的元素的个数
disjoint：如果两个集合没有共同元素返回true

java.util.Collection

removeIf(lambda表达式)

java.util.List

default void sort(Comparator c)

直接在对象上调用，使用比较器排序

java.util.Comparator

Comparator< T> reversed()