概述
集合与数组
- 集合和数组都是对多个数据进行存储操作的结构，即 Java 容器，此时的存储是指内存层面的存储，不涉及持久化的存储
- 数组一旦初始化，长度就确定了，而且存储的数据类型也确定了，数组提供的操作方法太少，增删插等操作不方便，效率不高，对于无序、不可重复的要求不能满足
集合的特点
- 用于存储对象的容器，动态存储
- 集合的长度是可变的
- 集合中不可以存储基本数据类型值
集合定义在 java.util 包下，可以分为两个体系
- Collection：单列集合，用于存储对象
- List 接口：元素有序、可重复的合
- ArrayList
- LinkedList
- Vector
- Set 接口：元素无序、不可重复的集合
- HashSet
- LinkedHashSet
- TreeSet
- HashSet
- List 接口：元素有序、可重复的合
- Map：双列集合，用于存储具有映射关系的 key-value（键值对） 的对象
- HashMap
- LinkedHashMap
- TreeMap
- Hashtable
- Properties
- HashMap
Collection 接口
集合容器因为内部的数据结构不同，有多种具体容器，不断向上抽象，就形成了集合框架，框架的顶层是 Collection 接口
常见方法
- 添加
boolean add(Object obj);
// 添加元素
boolean addAll(Collection coll);
// 将coll中的元素添加至调用addAll()的集合中
- 删除
boolean remove(Object obj);
// 删除obj元素
boolean removeAll(Collection coll);
// 将两个集合中相同的元素从当前集合中删除
boolean retainAll(Collection coll);
// 取交集：将两个集合中相同的元素从当前集合中保留，删除不同元素
void clear();
// 清空集合
- 判断
boolean contains(Object obj);
// 判断集合中是否存在 obj 元素，注意，对于重写了 equals() 方法的类，比如String，底层是使用equals方法去比较 obj 对象的内容，如果没有写，则比较地址也就是 Object 类的对象，所以一般要求向集合中添加的类都要重写 equals() 方法
boolean containsAll(Collection coll);
// 判断集合中是否包含coll中的所有元素
boolean isEmpty();
// 判断集合是否为空
boolean equals(Collection coll);
// 判断集合元素是否全部相同（不同的Collection实现类可能考虑或不考虑有序）
- 获取
int size();
// 返回集合中元素的个数
Iterator iterator();
// 取出元素的方式：迭代器，返回迭代器对象，因为每个容器的数据结构不同，所以该迭代器对象是在具体容器内部实现的，具体实现方法对于使用容器者不重要
- 其他
int hashcode();
// 返回集合的哈希值
Object[] toArray();
// 将集合转成数组
注意：数组转换为集合需要 Arrays 类的静态方法 asList(T t)
String str[] = new String[]{"hello","","world"}
List<String> 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()
- 指针下移
- 返回指针下移之后所指位置上的元素
- remove()
在遍历的时候删除集合中的元素，此方法不同于集合直接调用remove()，如果还未调用 next()方法，或在上次调用 next()方法后已经调用了 remove()方法，再调用 remove() 方法的时候会出现 IllegalStateException
遍历的正确方方式
Iterator it = coll.iterator();
while(it.hasNext()) {
System.out.println(it.next());
}
错误1
Iterator it = coll.iterator();
// 调用 next() 就会让指针后移
while(it.next()!=null) {
System.out.println(it.next());
}
错误2
Iterator it = coll.iterator();
// 调用集合的 iterator() 就会返回一个全新的迭代器
while(coll.iterator().hasNext()) {
System.out.println(coll.iterator().next());
}
使用迭代器删除集合中的对象
Iterator iterator = coll.iterator;
while(iterator.hasNext()) {
Object obj = iterator.next();
if(targetObj.equals(obj)) {
iterator .remove();
}
}
JDK5.0 新增 foreach 循环
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 对象
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev,E element,Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
Vector
Vector 扩容方式：默认扩容为之前的2倍
List 接口中常用方法
相比 Collection 中的常用方法，多了关于索引的方法
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
- 无序性
以 HashSet 为例，底层使用数组加链表实现，但是存储的数据在底层数组中并非按照数组的索引的顺序添加，而是根据哈希值确定，遍历的顺序不同于添加元素的顺序，但是每次的遍历顺序是相同的，不等于随机性 - 不可重复性
向 Set 中添加的对象不可以重复，即保证添加的元素按照 equals() 判断时，不可返回true - 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 时，该索引位置上所有数据改为使用红黑树存储
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> 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
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before,after;
Entry(int hash,K key,V value,Node<K,V> 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)
Properties pros = new Properties();
// 加载对应的文件流，这里简写，实际应用时，需要捕捉异常和关闭资源
pros.load(new FileInputStream("jdbc.properties"));
String user = pros.getProperty("user");
System.out.println(user);
常用方法
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 的工具类
常用方法
void reverse(List<?> list)
// 反转 List 中的元素的顺序
void shuffle(List<?> list)
// 对List中的元素进行随机排序
void sort(List)
// 根据自然顺序升序排序，List 中的元素必须实现了 Comparable 接口
void sort(List<T> list, Comparator<? super T> 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 还提供了一组方法把可变集合封装成不可变集合
List<T> unmodifiableList(List<? extends T> list)
Set<T> unmodifiableSet(Set<? extends T> set)
Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> map)
注意：继续对原始的可变集合进行增删是可以的，并且，会直接影响到封装后的不可变集合。因此，如果希望把一个可变集合封装成不可变不可变，那么，返回不可变集合后，最好立刻置空可变集合的引用
线程安全集合
ArrayList 和 HashMap 都是线程不安全的，Collections还提供了一组方法，可以把线程不安全的集合变为线程安全的集合
List<T> synchronizedList(List<T> list)
Set<T> synchronizedSet(Set<T> set)
Map<K,V> synchronizedMap(Map<K,V> map)
注意：Java 5 引入了更高效的并发集合类，所以上述这几个同步方法已经没有什么用了