集合框架

一个Java对象可以在内部持有若干其他Java对象，并对外提供访问接口，把这种Java对象称为集合

集合框架都包含三大块内容：（接口、实现、算法）
（1）对外的接口
（2）接口的实现
（3）对集合运算的算法

接口：表示集合的抽象数据类型，如Collection、List、Set、Map、Iterator
实现：集合框架中接口的具体实现，最常用实现：ArrayList、LinkedList、HashMap、HashSet
算法：在一个实现了集合框架中的接口的对象上完成某种有用的计算机算法

为什么使用集合？

Java提供了数组这种数据类型，可以充当集合，那么，为什么还需要其他集合类？这是因为数组有如下限制
（1）数组初始化后大小不可变
（2）数组只能按索引顺序存取

各种不同类型的集合类来处理不同的数据
（1）可变大小的顺序链表
（2）保证无重复元素的集合

集合分类

Java集合框架两大类接口：Collection和Map，其中List和Set是Collention的子类，所以通常说有三大类接口
共同点：都是集合接口

List接口（重复、有序）

实现List接口的常用类有ArrayList和LinkedList，它们可以容纳所有类型对象，包括null，允许重复并且都保证了元素的存储顺序

List接口中定义的各种方法

contains()、indexOf()使用需要覆写equals()方法
要正确使用List的contains()、indexOf()这些方法，放入的实例必须正确覆写equals()方法，否则，放进去的实例，查找不到。之所以能正常放入String、Integer这些对象，是因为Java标准库定义的这些类已经正确实现了equals()方法

正确编写equals()方法？
equals()方法要求必须满足以下条件
（1）自反性（Reflexive）：对于非null的x来说，x.equals(x)必须返回true
（2）对称性（Symmetric）：对于非null的x和y来说，如果x.equals(y)为true，则y.equals(x)也必须为true
（3）传递性（Transitive）：对于非null的x、y和z来说，如果x.equals(y)为true，y.equals(z)也为true，那么x.equals(z)也必须为true
（4）一致性（Consistent）：对于非null的x和y来说，只要x和y状态不变，则x.equals(y)总是一致地返回true或者false
（5）对null的比较：即x.equals(null)永远返回false

private String name;public boolean equals(Object o) {if (o instanceof Person) {Person p = (Person) o;return Objects.equals(this.name, p.name) && this.age == p.age;}return false;
}

1.确定实例“相等”的逻辑，即哪些字段相等，就认为实例相等
2.用instanceof判断传入的待比较的Object是不是当前类型，如果是，继续比较，否则，返回false
3.对引用类型用Objects.equals()比较，对基本类型直接用 == 比较

（1）ArrayList

public class ArrayList
extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable{}
对数组进行了封装，实现了可变长度的数组，存储方式和数组相同，都是在内存中连续分配空间

1.ArrayList继承了AbstractList，实现了List。它是一个数组队列，提供相关的添加、删除、修改、遍历等功能
2.ArrayList实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是Java中用来被List实现，为List提供快速功能的。在ArrayList中，可以通过元素的序号快速获取元素对象，这就是随机访问
3.ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆
4.ArrayList实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化取传输

（2）LinkedList

public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable{}

LinkedList的底层数据结构是基于双向循环链表，且头结点中不存放数据。

采用链表存储方式，优点在于插入、删除元素是效率比较高，额外方法addFirst()、addLast()、removeFirst()、removeLast()等方法

这些方法使LinkedList可被作为堆栈（stack）或队列（queue）
1.LinkedList实现List接口，能对它进行队列操作
2.LinkedList实现Qeque接口，即能将LinkedList当作双端队列使用
3.LinkedList实现了Cloneable接口，即覆盖了函数clone();能被克隆
4.LinkedList实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输
5.LinkedList是非同步的

ListedList的remove()方法
LinkedList实现了List接口，而List接口继承了Collection接口。LinkedList还实现了Queue接口。虽然不是直接实现的，而是实现接口的自接口
Linked===>List—–>Collection Linked===>Queue

（1）Collection中只定义了一个remove方法：remove(Object o)
从列表中删除指定元素的第一个匹配项（如果存在）

（2）List中定义了另外一个remove方法：remove(int index)
删除此列表中指定位置的元素

（3）Queue中定义了最后一个remove方法：remove()
检索并删除此列表的头（第一个元素）

LinkedList的一些特殊方法

ArrayList和LinkedList比较

通常情况下，总是优先使用ArrayList

Set接口（不重复、无序）

Set继承于Collection接口，是一个不允许重复元素，并且无序的集合，主要有HashSet和TreeSet两大实现类
在判断重复元素的时候，Set集合会调用hashCode()和equal()方法来实现
（1）HashSet是哈希表结构，主要利用HashMap的key来存储元素，计算插入元素的hashCode来获取元素在集合中的位置
TreeSet是红黑树结构，每一个元素都是树中的一个节点，插入的元素都会进行排序

与List接口一样，Set接口也提供了集合操作的基本方法。但与List不同的是，Set还提供了equals(Object o)和hashCode()，供其子类重写，以实现对集合中插入重复元素的处理

（1）HashSet

public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, java.io.Serializable{}

HashSet实现Set接口，底层由HashMap来实现，为哈希表结构，新增元素相当于HashMap的key，value默认为一个固定的Object。HashSet相当于一个阉割版的HashMap
当有元素插入的时候，会计算元素的hashCode值，将元素插入到哈希表对应的位置中来
它继承于AbstractSet，实现了Set, Cloneable, Serializable接口
（1）HashSet继承AbstractSet类，获得了Set接口大部分的实现，减少了实现此接口所需的工作，实际上是又继承了AbstractCollection类
（2）HashSet实现了Set接口，获取Set接口的方法，可以自定义具体实现，也可以继承AbstractSet类中的实现
（3）HashSet实现Cloneable，得到了clone()方法，能被克隆
（4）HashSet实现Serializable，支持序列化，通过序列化去传输，典型的应用就是hessian协议

特点
（1）不允许出现重复因素
（2）允许插入Null值
（3）元素无序（添加顺序和遍历顺序不一致）
（4）线程不安全，若2个线程同时操作HashSet，必须通过代码实现同步

构造方法
默认初始容量（16）和负载因子（0.75）

常用方法

（2）TreeSet

public class TreeSet<E>extends AbstractSet<E>implements NavigableSet<E>, Cloneable, java.io.Serializable{}

实现和树结构有关。与HashSet集合类似，TreeSet也是基于Map来实现，具体实现TreeMap，其底层结构为红黑树（特殊的二叉查找树）
与HashSet不同的是，TreeSet具有排序功能，分为自然排序（默认）和自定义排序两类，默认是自然排序；在程序中，可以按照任意顺序将元素插入到集合中，等到遍历时TreeSet会按照一定顺序输出（倒序或者升序）
（1）与HashSet同理，TreeSet继承AbstractSet类，获得了Set集合基础实现操作
（2）TreeSet实现NavigableSet接口，而NavigableSet又扩展了SortedSet接口。这两个接口主要定义了搜索元素的能力
例如给定某个元素，查找该集合中比给定元素大于、小于、等于的元素集合，或者比给定元素大于、小于、等于的元素个数。简单地说，实现NavigableSet接口使得TreeSet具备了元素搜索功能
（3）TreeSet实现Cloneable接口，能被克隆
（4）TreeSet实现了Serializable接口，支持序列化，可以使用hessian协议来传输；

特点
（1）对插入的元素进行排序，是一个有序的集合（主要与HashSet的区别）
（2）底层使用红黑树结构，而不是哈希表结构
（3）允许插入Null值
（4）不允许插入重复元素
（5）线程不安全

构造方法

常用方法

Map接口（键唯一，值不唯一）

键值（key-value）映射表的数据结构，能高效通过key快速查找value（元素）

常用方法

注意：Map中不存在重复的key，因为放入相同的key，只会把原有的key-value对应的value给替换掉
（1）Map是一种映射表，可以通过key快速查找value
（2）可以通过foreach遍历keySet()，也可以通过foreach遍历entrySet()，直接获取key-value
（3）最常用的一种Map实现是HashMap

（1）HashMap

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable{}

HashMap基于哈希表的Map接口的非同步实现，此实现提供所有可选的映射操作，并允许使用null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变

HashMap开发中使用频率最高的用于映射（键值对 key-value）处理的数据结构，经常把HashMap数据结构叫做散列链表

（1）HashMap是一个散列表，存储的内容是键值对(key-value)映射
（2）HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口
（3）HashMap的实现不是同步的，这意味着线程不安全。它的key、value都可以为null。此外，HashMap中的映射不是有序的（HashMap类大致相当于Hashtable，除了它是不同步的，并允许null）
（4）HashMap的实例有两个参数影响其性能：“初始容量”和“加载因子”。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行rehash操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数

通常，默认加载因子是0.75，这是在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数HashMap类的操作中，包括get和put操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少rehash操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生rehash操作

HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子

数据结构
在Java语言编程中，最基本的数据结构就两种：数组和引用，其他所有的数据结构都可以通过这两个基本的数据结构来实现，在JDK 1.7以前，HashMap就是一个链表散列的结构，但是在JDK 1.8发布后，HashMap的链表长度大于一定值过后，变编程红黑树

Java中采用的便是链地址法，便是每个数组元素上都是一个链表。当数据被hash后，得到数组下标，将数据放在对应数组下标的链表上
其中每个元素都用node节点表示
Node是HashMap的一个静态内部类，用来储存数据和保持链表结构的。它的本质就是一个映射（键值对）

当然，会产生两个key值产生同一个位置，（最主要的便是因为index的产生原理，当然也有可能是产生了一样的hash值）这种情况叫哈希碰撞。当然hash算法计算结果越分散均匀，发生hash碰撞的机率就越小，map的存储效率就越高

static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = next;}public final K getKey() { return key; }public final V getValue() { return value; }public final String toString() { return key + "=" + value; }public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}public final boolean equals(Object o) {if (o == this)return true;if (o instanceof Map.Entry) {Map.Entry<?,?> e = (Map.Entry<?,?>)o;if (Objects.equals(key, e.getKey()) &&Objects.equals(value, e.getValue()))return true;}}}
}

特点
HashMap根据键的hashcode值存储数据，大多数情况可以直接定位到它的值，因而具有很快的访问速度，但遍历顺序是不确定的
想要使得遍历的顺序就是插入的顺序，可以使用LinkedHashMap，LinkedHashMap是HashMap的一个子类，保存了记录的插入顺序，在用Iterator遍历LinkedHashMap时，先得到的记录肯定是先插入的，也可以在构造时带参数，按照访问次序排序

线程不安全的HashMap
因为多线程环境下，使用Hashmap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不能使用HashMap
（1）HashMap最多只允许一条记录的键为null，允许多条记录的值为null
（2）HashMap非线程安全，如果需要满足线程安全，可以使用Collections的synchronizedMap()使HashMap具有线程安全能力，或者使用ConcurrentHashMap

ConcurrentHashMap锁分段技术
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因，是因为所有访问HashTable的线程都必须竞争同一把锁，那假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率
ConcurrentHashMap锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问

构造方法
|

常用方法

（2）Hashtable

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, java.io.Serializable {}

实现了一个哈希表，它将键映射到值。任何非null对象都可以用作键值或值
为了从散列表成功存储和检索对象，用作键的对象必须实现hashCode()和equals()

Hashtable一个实例有两个影响其性能的参数：初始容量和负载因子
容量是哈希表中的桶数，初始容量只是创建哈希表时的容量。请注意，哈希表是打开的：在“哈希冲突”的情况下，单个存储桶存储多个条目，必须依次搜索
负载因子是在容量自动增加之前允许哈希表得到满足的度量。初始容量和负载因子参数仅仅是实现的暗示。关于何时以及是否调用rehash方法的具体细节是依赖于实现的

通常，默认负载因子（0.75）提供了时间和空间成本之间的良好折衷。更高的值会减少空间开销，但会增加查询条目的时间成本（这反映在大多数Hashtable操作中，包括get和put ）

初始容量控制了浪费空间与需要rehash操作之间的折中，这是耗时的。没有rehash如果初始容量大于项Hashtable将其负载因子包含除以最大数量永远不会发生的操作。然而，设置初始容量太高可能会浪费空间

如果将多个条目制作为Hashtable，则以足够大的容量创建它可能会使条目更有效地插入，以使其根据需要执行自动重新排序以增长表

效率低下的Hashtable容器
Hashtable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法时，其他线程访问HashTable的同步方法时，可能会进入阻塞或轮询状态。如线程1使用put进行添加元素，线程2不但不能使用put()添加元素，并且也不能使用get()来获取元素，所以竞争越激烈效率越低

构造方法

常用方法

遍历集合

迭代器（Iterator）

Iterator负责定义访问和遍历元素的接口

所谓interface，就是比抽象类还要抽象的纯抽象接口，因为它连字段都不能有。因为接口定义的所有方法默认都是public abstract的，所以这两个修饰符不需要写出来
Collection接口的iterator()方法返回一个Iterator,然后通过Iterator接口的两个方法即可方便地实现遍历

HashMap map = new HashMap<String,String>();
map.put(dog1);
map.put(dog2);
map.put(dog3);
Set keys = map.keySet();//获得迭代器
Iterator it = keys.iterator();
while(it.hasNext()){String key=(String) it.next();//获得键名Dog dogs = (Dog) map.get(key);//通过键获取值dogs.print();
}

foreach遍历

for(元素类型t  元素变量x ：数组或集合对象){引用了x的Java语句
}

泛型集合

LinkedList<String> list = new LinkedList<String>();
HashMap<int,String> hash = new HashMap<int,String>();

<>为限制值的类型