Java（集合）

这是目录

• java集合框架
• • Collection
  • 迭代器
  • 集合框架中的接口
• 具体的集合
• • List
  • • linkedList
    • ArrayList
    • ArrayList 与 linkedList 比较
  • 散列集
  • • HashSet
    • TreeSet
  • 队列与双端队列
  • • 优先队列
  • 映射
  • • map
    • HashMap
    • TreeMap

java集合框架

在Java集合类库中也将接口与实现分离。Collection接口，在Java类库中，集合类的基本接口是Collection接口。

Collection

Collection接口中的所有方法：

Iterator iterator();		// 返回一个用于访问集合中各个元素的迭代器
int size();					// 返回当前存储在集合中的元素个数
boolean isEmpty();			// 集合中没有元素，返回true
boolean contains(Object o);	// 如果集合中包含一个与o相等的对象，返回true
boolean add(E e);			// 将一个元素添加到集合，成功返回true
boolean addAll(Collection c);	// 将c集合所有的元素添加到这个集合，成功返回true
boolean remove(Object o);	// 从集合中删除 o，成功则返回true
boolean removeAll(Collection c);			// 从集合中删除所有c集合中的元素，成功返回true
boolean removeIf(Predicate filter);	// 从集合中删除filter返回true的所有元素。
void clear();				// 删除所有元素
boolean retainAll(Collection c);		// 删除与c集合中元素不同的元素，成功返回true
Object[] toArray();			// 返回集合中的对象的数组。
 T[] toArray(T[] a);		// 返回这个集合中的对象的数组。

迭代器

iterator接口包含 4个方法。

public interface Iterator {
    boolean hasNext();
    E next();
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    default void forEachRemaining(Consumer action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

通过反复调用next方法，可以逐个访问集合中的每个元素。如果到达了集合的末尾，next方法将抛出一个 NoSuchElementException。因此，需要在调用next之前，调用hasNext方法。如果迭代器对象还有多个可以访问的元素，方法就返回true。
for each 循环可以处理任何实现 Iterable接口的对象。Collection接口扩展了 Iterable 接口，因此，对于标准类库中的任何集合都可以使用 for each 循环。

访问元素的顺序取决于集合类型。如果迭代处理一个ArrayList，迭代器将会从索引0开始，每次迭代，索引值加1。如果访问HashSet中的元素，会按照一种随机的顺序获取元素。
Java迭代器中，查找一个元素的唯一方法是调用 next，而在执行查找操作的同时，迭代器的位置就会随之向前移动。可以认为Java迭代器位于两个元素之间。当调用next时，迭代器就越过下一个元素，并返回刚刚越过的那个元素的引用。

Iterator 接口的 remove 方法将会删除上次调用 next 方法时返回的元素。
next方法和remove方法调用之间存在依赖性，如果调用remove之前没有调用 next，将是不合法的。

集合框架中的接口

集合中有两个基本接口：Collection和Map。
List是一个有序集合。元素会增加到容器中的特定位置。可以采用两种方法访问元素：使用迭代器访问，或使用一个整数索引来访问。后面这种称为随机访问，可以按任意顺序访问元素。使用迭代器访问时必须顺序地访问元素。

List接口定义了多个用于随机访问的方法：

void add(int index,E element)
void remove(int index)
E get(int index)
E set(int index,E element)

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

具体的集合

List

list接口中的方法

// 返回一个列表迭代器，用来访问列表中的元素。
ListIterator listIterator();	
//返回一个列表迭代器，用来访问列表中的元素，第一次调用迭代器的next会返回给定索引的元素
ListIterator listIterator(int index); 
// 在给定位置添加一个元素
void add(int index, E element);
// 将一个集合中的所有元素添加到给定位置
boolean addAll(int i,Collection c);
// 删除并返回给定位置的元素
E remove(int index);
// 获取给定位置的元素
E get(int i)
// 用一个新元素替换给定位置的元素，并返回原来那个元素
E set(int i,E element)
// 返回与指定元素相等的元素在列表中第一次出现的位置，如果没有这样的元素将返回-1
int indexOf(Object element)
// 返回与指定元素相等的元素在列表中最后一次出现的位置，如果没有这样的元素将返回 -1
int lastIndexOf(Object element)

ListIterator 迭代器中的方法

// 在当前位置前添加一个元素。
void add(E newElement)
// 用新元素替换next或previous访问的上一个元素。
void set(E newElement)
// 当反向迭代列表时，如果还有可以访问的元素，返回true。
boolean hasPrevious()
// 返回前一个对象
E previous()
// 返回下一次调用next方法时将返回的元素的索引
int nextindex()
// 返回下一次调用previous方法时将返回的元素的索引
int previousIndex()

linkedList

linkedList 的底层使用的是双向链表。
使用链表适合减少在增加删除元素时的开销，不适合随机访问，没有索引。
如果只有少量的元素可以使用 ArrayList。
在使用 linkedList类，不建议使用 get和set方法，根据索引访问和设置数据。

// 构造一个空链表
linkedList()
// 构造一个链表，并将集合中所有的元素添加到这个链表中
linkedList(Collection elements)
// 将某个元素添加到列表的头部或尾部
void addFirst(E element)
void addLast(E element)
// 返回列表头部或尾部的元素
E getFirst()
E getLast()
// 删除并返回列表头部或尾部的元素
E removeFirst()
E removeLast()

ArrayList

ArrayList底层使用的数组。类实现了List接口。ArrayList封装了一个动态再分配的对象数组。

ArrayList 与 linkedList 比较

ArrayList底层使用的是数组，linkedList底层用的是双向链表
增删数据
ArrayList适合列表尾部增删数据，时间复杂度0(1),但是在指定位置i增删数据，时间复杂度为O(n-i)
linkedList在指定位置i增删是O(n)，因为要移动指针。
随机访问
ArrayList支持随机访问，linkedList不支持
空间
ArrayList空间花费在列表结尾预留一定的容量空间
linkedList空间花费在每一个元素多消耗一个存放前驱和后继的空间

ArrayList扩容原理
无参构造创建ArrayList时，初始化赋值一个空数组
向ArrayList中添加第一个元素时，容量扩充为10
元素大于增长速度后，每次扩容后会变为原来的1.5倍左右(oldCapacity+
(oldCapacity>>1)，然后使用Arrays.copyof进行复制

散列集

链表和数组允许指定元素的次序，如果想要查看某个指定的元素，但又不记得它的位置，就需要访问所有元素，直到找到为止。
散列表可以为每个对象计算一个整数，称为散列码，散列码是由对象的实例字段得出的一个整数。有不同数据的对象将产生不同的散列码。

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

对对象计算散列码，散列码对桶的个数取余，如果桶中没有其他元素，直接插入桶中，如果桶中已经被填充，则需要将新对象与桶中的所有对象进行比较，查看这个对象是否已经存在。

再散列：由于散列表中元素太多，就需要对散列表进行再散列，需要创建一个桶数更多的表，并将所有元素插入到这个新表中，然后丢弃原来的表。
装填因子(load factor)：确定何时对散列表进行再散列。对大多数程序，装填因子为0.75是合理的。表中已经填满了75%以上的桶。

HashSet

HashSet是基于散列表的集。可以用add方法添加元素。contains方法用来快速查找某个元素是否已经在集合中。
散列集迭代器将依次访问所有的桶。由于散列将元素分散在表中，所有会以一种看起来随机的顺序访问元素。只有不关心集合中元素的顺序才应该使用 HashSet。

// 构造一个空散列集
HashSet()
// 构造一个散列集，并将集合中的所有元素添加到这个散列集中。
HashSet(Collection elements)
// 构造一个空的具有指定容量(桶数)的散列集
HashSet(int initialCapacity)
// 构造一个有指定容量和装填因子（0.0~1.0之间的一个数）的空散列集
HashSet(int initialCapacity,float loadFactor)

TreeSet

TreeSet类与散列集类似，不过，它比散列集有所改进。树集是一个有序集合。可以以任意顺序将元素插入到集合中。对集合进行遍历时，值将自动的按照排序后的顺序呈现。
TreeSet底层的实现数据结构是红黑树。
排序是用一个树数据结构完成的（红黑树）。每次将一个元素添加到数中时，都会将其放置在正确的排序位置上。迭代器总是以有序的顺序访问每个元素。
将一个元素添加到树中要比添加到散列表中慢。
如果不需要数据是有序的，可以使用 HashSet，如果需要数据是有序的，则使用TreeSet。

// 构造一个空树集
TreeSet()
// 构造一个空树集，并定制排序规则
TreeSet(Comparator comparator)
// 构造一个树集，并增加一个集合或有序集中的所有元素
TreeSet(Collection elements)
TreeSet(SortedSet s)

队列与双端队列

队列允许高效地在尾部添加元素，并在头部删除元素。双端队列允许在头部和尾部都高效地添加或删除元素。不支持在队列中间删除元素。
在Java6中引入了Deque接口，ArrayDeque和linkedList类实现了这个接口。这两个类都可以提供双端队列，其大小可以根据需要扩展。
Queue接口中地方法

// 添加一个元素到队列队尾，成功返回true，失败抛出异常
boolean add(E element)	
// 添加一个元素到队列队尾，成功返回true，失败返回false
boolean offer(E element)
// 如果队列不为空，删除并返回这个队列队头地元素，为空抛出异常
E remove()
// 如果队列不为空，删除并返回这个队列队头地元素，为空返回null
E poll()
// 如果队列不为空，返回这个队列队头地元素，但不删除，如果为空，抛出异常
E element()
// 如果队列不为空，返回这个队列队头地元素，但不删除，如果为空，返回null
E peek()

ArrayDeque类中方法

// 用初始容量16或给定地初始容量构造一个无限定双端队列
ArrayDeque()
ArrayDeque(int initialCapacity)

优先队列

优先队列（priority queue）中地元素可以按照任意地顺序插入，但会按照有序地顺序进行检索。无论何时调用remove方法，总会获得当前优先队列中最小地元素，并不需要对它们进行排序。

队列使用了一个精巧且高效的数据结构，称为堆（heap）。堆是一个可以自组织的二叉树，添加和删除操作可以让最小的元素移动到根，而不必花费时间对元素进行排序。
PriorityQueue

PriorityQueue()
PriorityQueue(int initialCapacity)
PriorityQueue(int initialCapacity,Comparator c)

映射

集是一个集合，允许你快速查找现有的元素，但是，要查找一个元素，需要有所查找的那个元素的准确副本。通常，我们知道某些关键信息，希望查找与之关联的元素。映射（map）数据结构就是为此设计的。map用来存放键/值对。如果提供了键，就能查找到值。
java类库中为映射提供了两个通用的实现：HashMap和TreeMap。这两个类都实现了Map接口。
散列映射对键进行散列，树映射根据键的顺序将元素组织为一个搜索树。散列或比较函数只应用于键。与键关联的值不进行散列或比较。
散列映射比树映射要快一点，如果不需要按照有序的顺序访问键，最好还是选择散列映射。
每当往映射中添加一个对象时，必须同时提供一个键。这里键是一个字符串。值就是要存储的对象。
要想检索一个值，必须使用键。如果映射中没有存储键对应的信息，get将返回null
键必须是唯一的。不能对同一个键存放两个值，如果对同一个键调用两次put方法，第二个值就会取代第一个值。

map

// 获取与键关联的值，返回与键关联的对象，或者如果映射中没有这个对象，则返回null
V get(Object key)
// 获得与键关联的值，返回与键关联的对象，如果未找到这个键，则返回 defaultValue
default V getOrDefault(Object key,V defaultValue)
// 将关联的一对键和值放到映射中。如果键已经存在，则新的值，取代旧值
V put(K key,V value)
// 将给定映射中的所有映射条目添加到这个映射中。
void putAll(Map entries)
// 如果映射中已经有这个键，返回true
boolean containsKey(Object key)
// 如果映射中已经有这个值，则返回true
boolean containsValue(Object value)
// 对这个映射中所有的键/值对应用这个动作
default void forEach(BiConsumer action)

HashMap

HashMap()
HashMap(int initialCapacity)
// 用给定的容量和装填因子构造一个空散列映射
HashMap(int initialCapacity, float loadFactor)

HashMap底层实现
原理，内部数据结构（拉链法）
数组和链表的结合（1.8后加入红黑树，O(n)->O(logn))
内部是容量(Capacity)的Entry数组(默认16个，扩容后一定是2的幂次)，
数组存放元素的位置称为桶(bucket)。
每个桶都有索引，系统可以根据索引快速找到bucket中的元素。
每个bucket中存储一个元素（Entry对象），但每一个Entry对象可以带一
个引用变量指向下一个元素形成Entry链

put方法过程
对key求哈希值然后计算下标，如果没有哈希碰撞就直接插入，如果碰撞
了以链表的形式链接到后面。
如果链表长度超过8，就转换为红黑树。
小于等于6转化为链表
如果节点已经存在就替换旧值。
如果元素总个数大于threshold（容量*加载因子0.75）就resize扩容。
扩容还发生在当链表长度大于8但是此时数组容量小于64（说明一个位置冲突，扩容后让节点分布更均匀一些）
HashMap的哈希函数怎么实现
实现
（h=key.hashCode()）^(h>>>16) 高16位不变，低16位bit和高16位bit做异或运算获得hash值，然后（n-1)&hash获得下标。
原因

1. 由于和（length-1）运算，length 绝大多数情况小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列。
2. 所以这样高16位是用不到的，为了让高16也参与运算,让他的hashCode()和自己的高16位^运算。所以(h >>> 16)得到他的高16位与hashCode()进行^运算。

为什么&位必须是奇数（length-1）

1. 长度是2的幂次，length-1的所有二进制都是1，这种情况下，等于hash后几位的值，相当于取余但是比%快。table[i=(n-1)&hash];
2. 为什么用^而不用&和|因为&和|都会使得结果偏向0或者1 ,并不是均匀的概念,所以用^

如何解决hash冲突
定义：hashcode一样但是key不一样，这就会导致冲突（如果key也一样就是覆盖了）
HashMap解决的方法是链式地址法，将所有哈希地址相同的记录放在一个桶的链表中。

处理冲突方法

1. 开放地址法 线性探测法（增加d）平方探针法 伪随机法 (如果冲突，随机生成一个数，在原来值的基础上加上随机数，直至不发生哈希冲突)
2. 链地址法 再次哈希（函数不同）建立公共的溢出区

hashmap线程并发安全
安全问题（两个方面）
多个线程同时put,当put的key一样造成一个线程put的数据被覆盖多个线程同时检测到元素个数超过数组大小*loadFactor,同时对Node数组进行扩容，都重新计算元素位置和复制数据，最终只有一个线程扩容后的数据会复制成功，其他线程丢失,并且put的数据也丢失。
红黑树的五大特征（几何操作时间均为O(logn)）

1. 节点要么红，要么黑
2. 根节点和叶子节点为黑色
3. 红色节点的左右孩子都是黑色（从根节点到叶子节点不会出现连续两个红色节点）
4. 从任意节点到每个叶子节点的所有路径，包含相同数目的黑色节点。
5. 从根到最远的叶子节点的路径不超过从根到最近叶子节点路径的两倍

HashMap,linkedHashMap,TreeMap底层区别
linkedHashMap
拥有HashMap所有特性，但多维护了一个双向链表。
保存了记录的插入顺序，在用Iterator遍历linkedHashMap时，先得
到的记录肯定是先插入的。
内存比HashMap大，性能差一些。 但是考虑元素插入的顺序选择它
TreeMap
底层是红黑树，在需要有序map集合时使用
对key的排序

HashMap扩容（resize）的优化
1.7
resize 方法，这个方法会在初始化和扩展容量的时候使用。扩展容量时，容量会扩充为原来的 2 倍，所有元素重新计算哈希值，位置发生变化，比较耗性能，如果事先知道 Map 的 size，可以在一开始就创建大小适用的Map以减去 resize 的开销。
1.8
优化1：桶中的链表不像1.7重新计算hash, hash值对应新增bit是0,索引不变，是1变成"原索引+oldCap";
优化2：引用红黑树,仍采用原索引+oldCap的方式重新重构链表。

TreeMap

TreeMap的底层实现，是一个红黑树的数据结构。
红黑树参考 一篇文章看懂红黑树原理，有实现代码，可以运行

集合结束