11.1 Java集合框架概述

1 集合与数组

• 集合、数组都是对多个数据进行存储操作的结构，简称为java容器。
  • 说明：此时的存储，主要指的是内存层面的存储，不涉及到持久化存储(.txt, .jpg, 数据库等)。
• 数组在存储多个数据方面的特点：
  • 一旦初始化后，长度就确定了
  • 一旦定义好，其元素类型就确定了，只能操作指定类型数据。
• 数组在存储多个数据方面的缺点：
  • 一旦初始化后，数组长度不能改变。
  • 数组中提供的属性和方法少，不便于进行添加、删除、插入等操作，且效率不高。同时无法直接获取存储元素的个数。
  • 数组存储的数据是有序的、可以重复的(对于无序、不可重复的需求无法满足)。---->存储数据的特点单一

2 集合应用场景

3 集合体系

• Java 集合可分为 Collection 和 Map 两种体系
• Collection接口：单列数据，定义了存取一组对象的方法的集合
  • List：元素有序、可重复的集合 --->动态“数组”
  • Set：元素无序、不可重复的集合 --->类似高中数学讲的“集合”
• Map接口：双列数据，保存具有映射关系“key-value对”的集合 --->y = f(x)

11.2 Collection接口方法

• 添加
  • add(Object obj)
  • addAll(Collection coll)：将集合coll的元素添加到当前集合中
• 获取有效元素的个数
  • int size()
• 清空集合
  • void clear()
• 是否是空集合
  • boolean isEmpty()
• 判断当前集合是否包含某个元素
  • boolean contains(Object obj)：是通过元素的equals方法来判断是否是同一个对象（比较的是内容，不是地址，所以，向collection接口的实现类的对象中添加数据obj时，要求obj所在类重写equals方法）
  • boolean containsAll(Collection c)：判断c中所有元素是不是都在当前集合中。也是调用元素的equals方法来比较的。
• 删除
  • boolean remove(Object obj) ：通过元素的equals方法判断是否是要删除的那个元素。只会删除找到的第一个元素
  • boolean removeAll(Collection coll)：取当前集合的差集。在当前集合中，删除coll1中所有元素
• 取两个集合的交集
  • boolean retainAll(Collection c)：把交集的结果存在当前集合中，不影响c
• 集合是否相等
  • boolean equals(Object obj)：元素和顺序都比较
• 转成对象数组
  • 集合--->数组：Object[] toArray()
  • 数组--->集合：List<类型> list = Arrays.asList(new 封装类数组);
• 获取集合对象的哈希值
  • hashCode()
• 遍历
  • iterator()：返回迭代器对象，用于集合遍历

11.3 Iterator迭代器接口

1 介绍

• Iterator对象称为迭代器(设计模式的一种)，主要用于遍历 Collection 集合中的元素。
• GOF给迭代器模式的定义为：提供一种方法访问一个容器(container)对象中各个元素，而又不需暴露该对象的内部细节。迭代器模式，就是为容器而生。

2 Iterator接口方法

• next()：返回迭代器中下一个元素
• hasNext()：判断是否还有下一个元素
• remove()：迭代器定义了remove方法，可以在遍历的时候，删除集合中的元素。不同于集合中的remove方法

Iterator iterator = coll.iterator();
while(iterator.hasNext()){//next():①指针下移 ②返回下移以后集合位置上的元素System.out.println(iterator.next());
}

1. 在调用it.next()方法之前必须要调用it.hasNext()进行检测。若不调用，且下一条记录无效，直接调用it.next()会抛出NoSuchElementException异常。
2. 集合对象每次调用iterator()方法都得到一个全新的迭代器对象，默认游标都在集合的第一个元素之前。所以写成如下形式是错误的：

while(coll.iterator().hasNext()){System.out.println(coll.iterator().next());
}

while(iterator.hasNext()){if(iterator.next().equals(123))iterator.remove();
}

1. Iterator可以删除集合的元素，但是是遍历过程中通过迭代器对象的remove方法，不是集合对象的remove方法。
2. 如果还未调用next()或在上一次调用 next 方法之后已经调用了 remove 方法，再调用remove都会报IllegalStateException。

3 foreach遍历集合

for(集合元素类型 局部变量：集合对象){//操作
}
foreach内部仍然调用了迭代器。
练习题：
String[] str1 = new String[]{"a","a","a"};
//普通for循环赋值
for(int i = 0; i < str1.length;i++){str1[i] = "b";
}
String[] str2 = new String[]{"a","a","a"};
//foreach形式赋值
for(String s : str2){s = "b";
}//str1: b b b  ;  str2: a a a
//foreach形式使用了新的变量，赋值只是赋给了s，没有改变原数组

11.4 Collection子接口之一：List接口

1 ArrayList、LinkedList和Vector的异同

• 相同：三个类都实现了List接口，存储数据的特点相同，均存储有序的、可重复的数据
• 不同：
  • ArrayList：作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[]存储
  • LinkedList：底层使用双向链表存储，对于频繁插入删除操作，使用效率高。
  • Vector：List接口的古老实现类，很少使用。线程安全，效率低；底层使用Object[]存储

补充题目：请问ArrayList/LinkedList/Vector的异同？谈谈你的理解？ArrayList底层是什么？扩容机制？Vector和ArrayList的最大区别?

• ArrayList和LinkedList的异同

二者都线程不安全，相对线程安全的Vector，执行效率高。此外，ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。对于新增和删除操作add(特指插入)和remove，LinkedList比较占优势，因为ArrayList要移动数据。

• ArrayList和Vector的区别

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。正常情况下,大多数的Java程序员使用ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

2 源码分析

//采用空参构造器
ArrayList list = new ArrayList(); //底层直接创建一个初始容量为10的Object[]数组elementData
list.add(123); //elementData[0] = new Integer(123);
...
list.add(11); //此时elementData数组容量不够，则扩容。默认时，扩容为原来的1.5倍，同时需要将原有的数组中数据复制到新数组中//建议使用带参构造器，指定容量
ArrayList list = new ArrayList(int capacity);

LinkedList list = new LinkedList(); //内部声明了Node类型的first和last属性，默认值为null
list.add(123); //将123封装到Node中，创建了Node对象//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;}
}

• 底层创建了长度为10的数组
• 默认扩容为原来数组长度的2倍

3 List常用方法

• 增：void add(Object ele) 
• 删：Object remove(int index) / Object remove(Object obj)
• 改：Object set(int index, Object ele)
• 查：Object get(int index)
• 插：void add(int index, Object ele)
• 长度：size()
• 遍历：Iterator迭代器； 增强for循环； 普通for循环

11.5 Collection子接口之一：Set接口

1 子类 

• Hashset：作为接口的主要实现类；线程不安全；可以存储null值
• LinkedHashSet：作为Hashset的子类；遍历其内部数据时，可以按照添加顺序遍历。对于频繁的遍历操作，效率更高。
• TreeSet：可以按照添加对象指定属性进行排序。放入数据必须是同一个类的对象。

2 特性（以HashSet为例说明）

3 添加元素过程（以HashSet为例说明）

1. 首先调用元素a所在的类的hashcode()方法，计算元素的哈希值
2. 此哈希值接着通过某种散列算法计算出在HashSet底层数组中存放的位置（即：索引位置）
3. 判断此位置有无元素，若果没有，则元素a添加成功；若已经有元素（或以链表形式存在的多个元素），则比较元素a与已存在元素的哈希值
4. 如果哈希值相同，则调用元素a所在类的equals方法，若方法返回true，则添加失败，否则添加成功。

1. 向Set中添加数据，对应的类一定要重写equals()和hashCode(Objectobj)方法，以实现对象相等规则。
2. 重写的equals()和hashCode(Objectobj)方法尽可能保持一致。即：“相等的对象必须具有相等的散列码”。

1. 在程序运行时，同一个对象多次调用 hashCode() 方法应该返回相同的值。
2. 当两个对象的 equals() 方法比较返回 true 时，这两个对象的 hashCode()方法的返回值也应相等。
3. 对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

public List duplicateList(List list){HashSet set = new HashSet();set.addAll(list);return new ArrayList(set);
}

HashSet set = new HashSet();
Person p1 = new Person(1001,"AA");
Person p2 = new Person(1002,"BB");
set.add(p1);
set.add(p2);
p1.name = "CC";
set.remove(p1);
System.out.println(set); //含有1002,"BB", 1001,"CC"两个元素
//HashSet是按照哈希值存储和查找的，p1内容变了，哈希值变了，一开始存储的位置不变。此时用新的p1查找，相应哈希值位置上并无元素，所以删除失败。
set.add(new Person(1001,"CC"));
System.out.println(set); //含有1002,"BB", 1001,"CC", 1001,"CC"三个元素
set.add(new Person(1001,"AA"));
System.out.println(set); //含有1002,"BB", 1001,"CC", 1001,"CC", 1001,"AA"四个元素

4 LinkedHashSet添加元素

5 TreeSet

• 向TreeSet添加的数据必须是同一个类的对象。
• 需要指定排序方式：自然排序或定制排序。（类似于java比较器的操作）
• 自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()方法。（当compare()只使用其中某些属性比较，则如果两个对象其他属性不同，也无法同时存入集合）
• 存储时采用红黑树
• 定制排序

Comparator com = new Comparator(){public int compare(Object o1, Object o2){//比较的方式}
}
TreeSet set = new TreeSet(com);

11.6 Map接口

• LinkedHashMap：保证在遍历map时，可以按照添加的顺序遍历。（在原有的HashMap的底层结构基础上，添加了一对指针，指向添加时前一个和后一个元素）对于频繁的遍历操作，执行效率高

• Properties：常用来处理配置文件。key和value都是String类型。

1 map结构理解

• Map 中的 key 用Set来存放，不允许重复，即同一个 Map 对象所对应的类，须重写hashCode()和equals()方法
• 常用String类作为Map的“键”
• key 和 value 之间存在单向一对一关系，即通过指定的 key 总能找到唯一的、确定的 value
• values为无序，可重复
• 存放时是以Entry = (key, value)存放的，key-value构成了一个Entry对象，Entry是无序，不可重复的

2 HashMap的底层实现原理

• 首先，调用key所在的hashCode()计算key1哈希值，此哈希值经过某种算法以后，得到在Entry[]数组中的位置。
• 如果此位置上数据为空，此时key value添加成功；
• 如果不为空(有一个或多个数据，以链表形式存在)，比较key和已经存在的一个或多个数据的哈希值：
• 如果key1哈希值与已经存在的数据哈希值不相同，则添加成功；
• 如果key1哈希值和已经存在的某一个数据相同，继续比较，调用key1所在类的equals()方法，
• 如果返回false，添加成功，
• 如果返回true，使用value替换相应的value值（修改）

1. new HashMap()：底层没有创建一个长度为16的数组
2. 底层的数组是：Node[]
3. 首次调用put()方法时，底层创建长度为16的数组
4. 当数组的某一个索引位置上的元素以链表形式存在的数据个数>8且当前数组长度>64时，此时此索引位置上的所有数据改为使用红黑树存储。（查找效率更高）

• DEFAULT_INITIAL_CAPACITY : HashMap的默认容量，16
• DEFAULT_LOAD_FACTOR：HashMap的默认加载因子，0.75
• TREEIFY_THRESHOLD：Bucket中链表长度大于该默认值，转化为红黑树，8
• MIN_TREEIFY_CAPACITY：桶中的Node被树化时最小的hash表容量，54
• threshold：扩容的临界值，=容量*填充因子 16*0.75 = 12
• loadFactor：填充因子

3 LinkedHsahMap

HashMap中内部类Node：
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;
}LinkedHashMap中的内部类Entry：
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);}
}

4 Map中定义的方法

• 添加、删除、修改操作：
  • 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
  • void clear()：清空当前map中的所有数据（与map = null操作不同）
• 元素查询的操作：
  • 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是否相等
• 元视图操作的方法：（遍历）
  • Set keySet()：返回所有key构成的Set集合
  • Collection values()：返回所有value构成的Collection集合
  • Set entrySet()：返回所有key-value对构成的Set集合

public void test1(){Map map = new HashMap();map.put("AA",123);map.put("45",45);map.put("bb",123);//遍历所有的keySet set = map.keySet();Iterator iterator = set.iterator();while (iterator.hasNext()){System.out.println(iterator.next());}//遍历所有valuesCollection values = map.values();for(Object obj : values){System.out.println(obj);}//遍历key-valueSet entrySet = map.entrySet();iterator = entrySet.iterator();while (iterator.hasNext()){Map.Entry entry = (Map.Entry) iterator.next();System.out.println(entry.getKey() + "---" + entry.getValue());}
}

5 TreeMap

• 向TreeMap中添加key-value，要求key必须是由同一个类创建的对象
• 具体操作与TreeSet类似

6 properties

public void test2() throws IOException {Properties properties = new Properties();properties.load(new FileInputStream("jdbc.properties"));String name = properties.getProperty("name");String pass = properties.getProperty("password");System.out.println(name + " " + pass);
}

11.7 Collections工具类

• 排序操作：（均为static方法）
  • reverse(List)：反转 List 中元素的顺序
  • shuffle(List)：对 List 集合元素进行随机排序
  • sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
  • sort(List，Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
  • swap(List，int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换
• 查找、替换
  • Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
  • Object max(Collection，Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
  • Object min(Collection)
  • Object min(Collection，Comparator)
  • int frequency(Collection，Object)：返回指定集合中指定元素的出现次数
  • void copy(List dest,List src)：将src中的内容复制到dest中
  • boolean replaceAll(List list，Object oldVal，Object newVal)：使用新值替换List 对象的所有旧值
• 同步控制
  • Collections 类中提供了多个 synchronizedXxx() 方法，该方法可使将指定集合包装成线程同步的集合，从而可以解决多线程并发访问集合时的线程安全问题