## 概述
### 集合与数组
1. 集合和数组都是对多个数据进行存储操作的结构，即 **Java 容器**，此时的存储是指内存层面的存储，不涉及持久化的存储
2. 数组一旦初始化，长度就确定了，而且存储的数据类型也确定了，数组提供的操作方法太少，增删插等操作不方便，效率不高，对于无序、不可重复的要求不能满足
### 集合的特点
1. 用于存储对象的容器，动态存储
2. 集合的长度是可变的
3. 集合中不可以存储基本数据类型值
集合定义在 java.util 包下，可以分为两个体系
* Collection：单列集合，用于存储对象
* List 接口：元素有序、可重复的合
* ArrayList
* LinkedList
* Vector
* Set 接口：元素无序、不可重复的集合
* HashSet
* LinkedHashSet
* TreeSet
* Map：双列集合，用于存储具有映射关系的 **key-value（键值对）** 的对象
* HashMap
* LinkedHashMap
* TreeMap
* Hashtable
* Properties
## Collection 接口
集合容器因为内部的数据结构不同，有多种具体容器，不断向上抽象，就形成了集合框架，框架的顶层是 Collection 接口
### 常见方法
1. 添加
```java
boolean add(Object obj);
// 添加元素
boolean addAll(Collection coll);
// 将coll中的元素添加至调用addAll()的集合中
```
2. 删除
```java
boolean remove(Object obj);
// 删除obj元素
boolean removeAll(Collection coll);
// 将两个集合中相同的元素从当前集合中删除
boolean retainAll(Collection coll);
// 取交集：将两个集合中相同的元素从当前集合中保留，删除不同元素
void clear();
// 清空集合
```
3. 判断
```java
boolean contains(Object obj);
// 判断集合中是否存在 obj 元素，注意，对于重写了 equals() 方法的类，比如String，底层是使用equals方法去比较 obj 对象的内容，如果没有写，则比较地址也就是 Object 类的对象，所以一般要求向集合中添加的类都要重写 equals() 方法
boolean containsAll(Collection coll);
// 判断集合中是否包含coll中的所有元素
boolean isEmpty();
// 判断集合是否为空
boolean equals(Collection coll);
// 判断集合元素是否全部相同（不同的Collection实现类可能考虑或不考虑有序）
```
4. 获取
```java
int size();
// 返回集合中元素的个数
Iterator iterator();
// 取出元素的方式：迭代器，返回迭代器对象，因为每个容器的数据结构不同，所以该迭代器对象是在具体容器内部实现的，具体实现方法对于使用容器者不重要
```
5. 其他
```java
int hashcode();
// 返回集合的哈希值
Object[] toArray();
// 将集合转成数组
```
注意：数组转换为集合需要 Arrays 类的静态方法 asList(T t)
```java
String str[] = new String[]{"hello","","world"}
List list = Arrays.asList(str);
System.out.println(list);
ArrayList list1 = Arrays.asList(new Integer[]{123,456});
System.out.println(list1);
LinkedList list2 = Arrays.asList(new int[]{123,456});
System.out.println(list2);
```
## 遍历集合
### Iterator 迭代器接口
Iterator 接口的对象即**迭代器**，用于遍历 Collection 容器（不用于 Map 遍历）中的元素，而不暴露容器的内部细节,注意集合对象每次调用 iterator() 都会得到一个**全新**的迭代器对象
**方法**
* hasNext()
* 判断当前指针位置的下一位置是否存在元素
* 如果不用此方法控制遍历，可能出现 NoSuchElementException
* next()
1. 指针下移
2. 返回指针下移之后所指位置上的元素
* remove()
在遍历的时候删除集合中的元素，此方法不同于集合直接调用remove()，如果还未调用 next()方法，或在上次调用 next()方法后已经调用了 remove()方法，再调用 remove() 方法的时候会出现 IllegalStateException
**遍历的正确方方式**
```java
Iterator it = coll.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
```
**错误1**
```java
Iterator it = coll.iterator();
// 调用 next() 就会让指针后移
while(it.next()!=null) {
System.out.println(it.next());
}
```
**错误2**
```java
Iterator it = coll.iterator();
// 调用集合的 iterator() 就会返回一个全新的迭代器
while(coll.iterator().hasNext()) {
System.out.println(coll.iterator().next());
}
```
**使用迭代器删除集合中的对象**
```java
Iterator iterator = coll.iterator;
while(iterator.hasNext()) {
Object obj = iterator.next();
if(targetObj.equals(obj)) {
iterator .remove();
}
}
```
### JDK5.0 新增 foreach 循环
```java
Collection coll = new ArrayList();
coll.add(123);
coll.add("hello world");
coll.add(false);
// 集合元素的类型 局部变量 : 集合对象
for(Object obj : coll) {
System.out.println(obj);
}
int[] arr = new int[]{1,2,3,4,5};
// 数组元素的类型 局部变量 : 数组对象
for(int i : arr) {
Syetem.out.println(i);
}
```
注：增强 for 循环在底层也是调用迭代器
## Collection 子接口：List
List 中的元素**有序**、**可重复**，每个元素都有其对应的顺序**索引**，可以根据索引存取，可以用来代替数组
List 接口的实现类主要是：ArrayList，LinkedList，Vector
* ArrayList 是 List 的主要实现类，线程不安全，效率高，底层使用数组存储数据
* LinkedList 底层使用双向链表，如果频繁插入和删除操作，效率高于 ArrayList
* Vector 作为 List 接口的古老实现类，线程安全，效率低，底层使用数组存储数据
### ArrayList
**jdk7**
* 使用数组存储数据
* 空参构造器 ArrayList()
初始化一个长度为 10 的 Object 数组
* 添加数据 add(E e)
如果此次添加数据导致底层的 elementData 数组容量不够，则扩容，默认情况下，扩容为 newCapacity = oldCapacity + (oldCapacity >> 1)，即原来容量的 1.5 倍，然后将原数组中的数据复制到新的数组中
* 建议使用有参构造器，先指定一个容量，减少扩容次数
ArrayList list = new ArrayList(int initialCapacity)
**jdk8**
* 空参构造器
底层数组初始化为{}，没有创建长度为 10 的数组，相当于懒汉式，延迟了对象创建，节省内存
* add()
第一次调用 add() 的时候，底层才创建了长度为10的数组，并将数据添加进数组，后续的添加和扩容与jdk7一样
### LinkedList
* LinkedList 内部将元素封装到 Node 对象中，且声明了 Node 类型的 first 和 last 属性，默认值为 null，分别指向链表头尾
* add() 创建 Node 对象
```java
private static class Node {
E item;
Node next;
Node prev;
Node(Node prev,E element,Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
```
### Vector
Vector 扩容方式：默认扩容为之前的2倍
### List 接口中常用方法
相比 Collection 中的常用方法，多了关于索引的方法
```java
void add(int index,Object ele)
// 在 index 索引位置插入元素
boolean addAll(int index,Collection eles)
// 从index索引位置开始将eles中所有元素添加进来
Object get (int index)
// 获取指定 index 索引位置的元素
Object set(int index,Object ele)
// 修改指定index位置的元素为ele
int indexOf(Object obj)
// 返回 obj 在集合中首次出现的索引，若不存在，返回 -1
int lastIndexOf(Object obj)
// 返回 obj 在集合中末次出现的索引，若不存在，返回 -1
Object remove(int Index)
// 移除指定 index 位置的元素，并返回该元素，注意 Collection 中的remove(Object obj)是按照对象删除
List subList(int fromIndex,int toIndex)
// 返回从 fromIndex 到 toIndex 位置的子集，左闭右开
```
### 对比 ArrayList 和 LinkedList
||ArrayList|LinkedList|
|---|---|---|
|底层实现|数组|链表|
|获取指定元素|速度很快|需要从头开始查找元素|
|添加元素到末尾|速度很快|速度很快|
|在指定位置添加/删除|需要移动元素|不需要移动元素|
|内存占用|小|较大|
## Collection 子接口：Set
1. 无序性
以 HashSet 为例，底层使用数组加链表实现，但是存储的数据在底层数组中并非按照数组的索引的顺序添加，而是根据**哈希值**确定，遍历的顺序不同于添加元素的顺序，但是每次的遍历顺序是相同的，**不等于随机性**
2. 不可重复性
向 Set 中添加的对象不可以重复，即保证添加的元素按照 equals() 判断时，不可返回true
3. Set 没有提供额外的方法
### HashSet
* 作为 Set 接口的主要实现类，线程不安全，可以存储 null 值
* 底层实现是数组加链表
* **添加元素的过程**
向 HashSet 中添加元素 A，首先调用元素 **A 所在类**的 hashCode() 方法，计算元素 A 的 hash 值，然后此 hash 值通过某种算法计算出元素在 HashSet 底层数组中的存放位置（索引），判断数组如果此位置上没有其他元素，则添加成功，如果有其他元素 B（或以链表形式存在多个元素），则比较元素 A、B 的 hash 值，若不同，则添加成功，若哈希值相同，再调用 A 所在类的 equals() 方法，equals() 返回 true 则添加失败，若返回false，则添加成功，并以链表形式进行存储
* 对于自定义类，如果没有重写 hashcode() 方法，则调用 Object 的 hashcode()，类似于随机数，就算两个对象的内容一样，哈希值也不同，那么放入底层数组的时候位置就大概率不同，所以也不会去调用 equals() 方法比较内容，调用 equals() 只会出现在：重写了 hashcode() 方法且哈希值相同且数组索引相同的情况下。如果 equals() 也返回 true，再使用链表追加
* 要求：向set中添加的数据，其所在的类一定要重写 equals() 方法和 hashCode() 方法，且相同的对象一定要具有相等的哈希值，也就是说对象中用于 equals() 比较的 Field 也一定要用于计算哈希值
* 注意，如果指定索引位置上已经以链表形式储存元素
* jdk7 中，元素 A 放入数组中，指向原来的元素
* jdk8 中，原来的元素放入数组中，指向 A
### LinkedHashSet
* 作为 HashSet 的子类，遍历其内部数据时，可以按照添加的顺序遍历
* 其底层也是使用数组加链表存储数据，但同时也维护了**两个引用**，记录此数据的前后数据元素，对于频繁遍历，能提高效率
### TreeSet
* 底层使用红黑树，要求存入的数据必须是**同一个类的对象**，对象不可重复
* 可以按照添加对象的指定属性进行排序：自然排序（实现 Comparable 接口）或定制排序（实现 Comparator 接口）
* TreeSet 存储的元素必须实现了 Comparable 接口，或者创建 TreeSet 对象时传入一个 Comparator 接口的实现类对象
## Map 接口
* Map 接口存储双列数据，即 key-value（键值对）的数据
* Map 中的 key 是**无序不可重复**的，使用 Set 存储 key，key 所在的类必须重写 equals() 和 hashCode()
* Map 中的 value **无序可重复**，使用 Collection 存储，value 所在的类要重写 equals()方法
* 一个 key-value（键值对）构成一个 Entry 对象，Entry 对象是**无序不可重复**的，使用 Set 存储
### HashMap
* HashMap 是 Map 的主要实现类，线程不安全，效率高，可以存储值为 null 的 key 和 value
* 底层实现：jdk7及之前使用**数组 + 链表**，jdk8 使用**数组 + 链表 + 红黑树**
**jdk7**
* HashMap map = new HashMap();
实例化一个 HashMap，底层创建了一个长度为 16 的数组 Entry[] table
* map.put(k,v);
首先调用 k 所在类的 hashCode() 方法计算 k 的哈希值，此哈希值再通过某种算法计算得到在 Entry[] 数组中的存放位置（索引）
* 如果此位置上的数据为空，则 k-v 添加成功
* 如果此位置上的数据不为空，也就是说此位置上存在一个或多个（链表形式）数据，则比较 k 和已存在的数据（一个或多个）的哈希值
* 如果 k 的哈希值与已存在的数据的哈希值都不同，则 k-v 添加成功（以链表形式）
* 如果 k 的哈希值和已经存在的某个数据的哈希值相同，继续比较
* 调用 k 所在类的 equals()方法，如果 equals()返回 false，k-v添加成功
* 如果 equals()返回 true：使用 v 替换之前的键值对中的 value（即修改已有的数据）
* 在不断地添加过程中，涉及到扩容问题，当超出临界值且要存放的位置非空时，进行扩容，默认扩容方式：扩容位原来的2倍，并将元素复制到新的 Map
**jdk8**
* new HashMap() 没有创建一个长度为 16 的数组
* 底层为 Node[] 数组而不是 Entry[]
* 首次调用 put() 方法时才创建长度为 16 的数组
* 当数组某个索引位置的元素以链表形式存在的数据个数 >8，且数组长度 >64 时，该索引位置上所有数据改为使用红黑树存储
```java
static class Node implements Map.Entry {
final int hash;
final K key;
V value;
Node next;
}
```
**底层典型属性**
* DEFAULT_INITIAL_CAPACITY：HashMap的默认容量，16
* DEFAULT_LOAD_FACTOR：HashMap的默认加载因子，0.75
* threshold：扩容的临界值，= 容量*加载因子：16 * 0.75 => 12
* TREEIFY_THRESHOLD：Bucket 中链表长度大于该默认值 8，转化为红黑树
* MIN_TREEIFY_CAPACITY：Bucket 中的 Node 被树化时最小的数组容量，64
### LinkedHashMap
* LinkedHashMap 继承于HashMap，其底层使用的结构与 HashMap 相同，
* LinkedHashMap 内部提供了 Entry，替换 HashMap 中的 Node
* 底层的 Entry 类加了一对指针指向前后元素，可以按照添加元素的顺序实现遍历，对于频繁的遍历操作，效率高于HashMap
```java
static class Entry extends HashMap.Node {
Entry before,after;
Entry(int hash,K key,V value,Node next) {
super(hash,key,value,next)
}
}
```
### TreeMap
TreeMap 底层使用**红黑树**，向 TreeMap 中添加 key-value，要求 key 必须是用同一个类创建的对象，因为要按照 key 进行排序，实现自然排序（Comparable）或定制排序（Comparator）
### Hashtable
Hashtable 是 Map 的古老实现类，线程安全，效率低，不能存储值为 null 的 key 和 value
### Properties
* 作为 Hashtable 的子类，常用于处理配置文件
* 配置文件中的 key 和 value 都是 字符串，所以 Properties 中的 key 和 value 都是 String
* 存取数据时，建议使用 setProperty(String key,String value) 方法和 getProperty(String key)
```java
Properties pros = new Properties();
// 加载对应的文件流，这里简写，实际应用时，需要捕捉异常和关闭资源
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);
```
### 常用方法
```java
Object put(Object key,Object value)
// 将指定 key-value 添加到（或修改）当前 Map 对象中
void putAll(Map m)
// 将 m 中的所有 key-value 存储到当前 Map 对象中
Object remove(Object key)
// 移除指定 key 的key-value 对，并返回 value，如果当前 Map 中没有指定的 key，返回null
void clear()
// 清空当前 Map 对象中的数据，注意不是 map=null 操作，当前 Map 对象依然存在
Object get(Object key)
// 获取指定 key 对应的 value
boolean containsKey(Object key)
// 是否包含指定的key
boolean containsValue(Object value)
// 是否包含指定的value
int size()
// 返回当前 Map 对象的 key-value 对的个数
boolean isEmpty()
// 判断当前 Map 对象是否为空
boolean equals(Object obj)
// 判断当前 Map 对象和参数对象 obj 是否相同
/* 遍历Map ，先获取 key-value 对应的集合，之后可以用迭代器去遍历*/
Set keySet()
// 返回所有key构成的Set集合
Collection values()
// 返回所有 value 构成的 Collection 集合
Set entrySet()
// 返回所有 key-value 对构成的 Set 集合
```
## Collections 工具类
Collections 是操作 Collection、Map 的工具类
**常用方法**
```java
void reverse(List list)
// 反转 List 中的元素的顺序
void shuffle(List list)
// 对List中的元素进行随机排序
void sort(List)
// 根据自然顺序升序排序，List 中的元素必须实现了 Comparable 接口
void sort(List list, Comparator c)
// 根据指定 Comparator 产生的顺序对 List 集合元素进行排序
void swap(List list,int i,int j)
// 将指定索引位置的两个元素交换
void copy(List dest,List src)
// 将 src 中的内容复制到 dest 中
boolean replaceAll(List list,Object oldVal,Object newVal)
// 使用新值替换 List 对象的所有旧值
Object max(Collection coll)
// 根据自然顺序，返回最大元素，元素必须实现了 Comparable 接口
Object max(Collection coll ,Comparator comp)
// 根据指定的比较器引发的顺序，返回给定集合的最大元素
Object min(Collection Coll)
// 根据自然顺序，返回最小元素，元素必须实现了 Comparable 接口
Object min(Collection Coll,Comparator comp)
// 根据指定的比较器引发的顺序，返回给定集合的最小元素
int frequency(Collection c,Object o)
// 返回集合中元素 o 出现的次数
```
**不可变集合**
Collections 还提供了一组方法把可变集合封装成不可变集合
```java
List unmodifiableList(List list)
Set unmodifiableSet(Set set)
Map unmodifiableMap(Map map)
```
**注意**：继续对原始的可变集合进行增删是可以的，并且，会直接影响到封装后的不可变集合。因此，如果希望把一个可变集合封装成不可变不可变，那么，返回不可变集合后，最好立刻置空可变集合的引用
**线程安全集合**
ArrayList 和 HashMap 都是线程不安全的，Collections还提供了一组方法，可以把线程不安全的集合变为线程安全的集合
```java
List synchronizedList(List list)
Set synchronizedSet(Set set)
Map synchronizedMap(Map map)
```
**注意**：Java 5 引入了更高效的并发集合类，所以上述这几个同步方法已经没有什么用了
Java基础 | 集合框架
