2集合基础

1. 集合框架体系

两大类：

2. Collection接口和常用方法

1. ```java
2. add（）方法：添加单个元素
3. remove（）方法：删除指定元素
4. contains（）方法：查找元素是否存在
5. size：获取元素个数
6. isEmpty（）方法：判断是否为空
7. clear（）方法：清空
8. addAll（）方法：添加多个元素
9. containsAll（）方法：查找多个元素是否都存在
10. removeAll（）方法：删除多个元素 ```

3. 迭代器的执行原理

Iterator iterator = coll.iterator();//得到iterator
while(iterator.hasNext()) {//调用hasNext()方法判断是否还有元素
    Object obj = iterator.next();//next()方法返回元素
}
//注意此时iterator已经到集合末尾，如需使用则重新调用iterator()方法即可。

增强版的for循环可以理解成简化版的迭代器循环

for (Object obj : col) {
    sout(obj);
}

4. List接口和常用方法

List接口是Collection接口的子接口

1.List集合类中的元素有序（取出的顺序和放入的顺序一致）、且可重复。

2.List集合的元素都有对应的顺序索引，支持索引。

3.List集合可以根据序号存取容器中的元素。

常用方法：

1.void add(int index,Object obj);//在index位置放入obj元素
2.boolean addAll(int index,Collection ele);//在index位置将ele集合中的元素添加进来
3.Object get(int index);//取出index处的元素
4.int indexOf(Object obj);//返回obj首次在集合中出现的位置
5.int lastIndexOf(Object obj);//返回obj在集合中末次出现的位置
6.Object remove(int index);//删除Index出的元素，并返回此元素
7.Object set(int index,Object obj);//设置指定Index位置的元素为obj，相当于是替换
8.List subList(int fromIndex,int toIndex);//返回从fromIndex（包括）到toIndex（不包括）处的子集合

接口遍历及常用方法：

1.iterator; 2.增强for循环；3.使用普通for

5. ArrayList底层结构和源码解析

1、底层维护了一个Object类型的数组elementData。

  **transient** Object[] elementData. **transient**表示该属性不会被序列化。

2、当创建对象时，如果使用的是无参构造器，则初始化elementData容量为0.

3、当添加元素时：先判断是否需要扩容，如果需要扩容则调用grow（）方法，否则直接添加元素到合适位置。

4、如果使用的是无参构造器，如果第一次添加，需要扩容的话，则扩容elementData为10，如果需要再次扩容的化，则扩容elementData为1.5倍。

5、如果使用的是指定容量capacity的构造器，则初始elementData容量为capacity，需要扩容的话，则直接扩容elementData为1.5倍。

6. Vector底层结构和ArrayList的比较

7. LinkedList底层结构

1、底层维护了一个双向链表

2、LinkedList中为何两个属性first和last指向头节点和尾节点

3、每个节点是Node对象，里面又维护了prev、next、item三个属性，其中通过prev指向前一个，通过next指向后一个节点。最终实现双链表

4、所以Linkedlist的添加和删除不是通过数组来完成的。

8. LinkedList和ArrayList比较

9.Set接口和常用方法

基本介绍：

1、无序（添加和取出的顺序不一致），没有索引

2、不允许重复元素，所以最多包含一个null

3、可以用增强for来遍历

10.HashSet

1、HashSet实现了Set接口

2、HashSet实际上是HashMap

public HashSet() {
    map = new HashMap();
}

3、可以存放null值，但最多只能有一个

4、HashSet不保证元素是有序的，取决于hash后，在确定索引的结果

5、底层是HashMap，HashMap底层是数组+链表+红黑树

1.添加元素时，先得到Hash值，会转换成索引值
2.找到存储数据表table，看这个索引位置是否已经存放的有元素
3.如果没有则直接加入
4.如果有，调用equal()方法比较，如果相同，就放弃添加，如果不相同，则添加到最后
5.在java8中，如果一个链表中的元素个数超过TREEIFY_THRESHOLO(默认值为8)，并且table的大小>= MIN_TREEIFY_CAPACITY(默认为64)，就会转换成红黑树，否则仍然采用数组扩容机制。
6.第一次添加时，table数组扩容到16，临界值（threshold）是16*加载因子（loadFactor)0.75f = 12
7.如果table数组使用到了临界值12，就会扩容到16*2=32，此时临界值为32*0.75=24，依此类推

11. LinkedHashSet

1.LinkedHashSet是HashSet的子类；

2.LinkedHashSet底层是一个LinkedHashMap,底层维护了一个数组加双向链表（数组table+双向链表）

3.添加第一次时，直接将数组table扩容到16，存放的节点类型是LinkedHashMap$Entry

4.数组table类型为HashMapEntry

• 在LinkedHashSet中维护了一个hash表和双向链表（LinkedHashSet有head和tail）
• 每一个节点有before和after属性，这样可以形成双向链表
• 在添加一个元素时，先求hash值，在求索引，确定该元素在table的位置，然后将添加的元素加入到双向链表（如果已经存在则不添加）
• 这样的话就能确保LinkedHashSet也能确保插入顺序和遍历顺序一致

12.Map接口

1.Map与Collection并列存在，用于保存具有映射关系的Key-value

2.Map中的key与value可以是任何类型的引用数据，会封装到HashMap$Node对象中

3.Map中的key不允许重复，原因和HashSet一样，value可以重复

4.Map中的key可以为null,value也可以为null，注意key为null只能有一个，value为null可以多个

5.常用String类作为Map的key，key与value之间存在一对一关系，通过指定的key可以找到value值

6.map存放的数据中一对k-v是放在一个Node中的，是因为Node实现了Entry接口

• k-v是这样封装的HashMap$Node node = newNode(hash,key,value,null)
• k-v为了方便程序员的遍历，还会创建EntrySet集合，该集合存放的元素的类型是Entry，而一个Entry对象就有k,v EntrySet> entrySet
• entrySet中，定义的类型是Map.Entry，但实际上存放的还是HashMap$Node,这是因为static class Node implements Map.Entry
• 当把HashMap$Node对象存放到entrySet就方便我们的遍历，因为Map.Entry提供了重要方法 K getKey(),V getValue()

13.Map接口和常用方法

1.put:添加

2.remove:根据键删除映射关系

3.get:根据键获取值

4.size:获取元素个数

5.isEmpty:判断个数为空

6.clear:清除

7.containsKey:查找键是否存在

14.Map的六种取值

//第一组：先取出所有的key,通过key取出对应的value
Set keyset = map.keySet();
//(1)增强for
for(Object obj: keyset) {
    sout(obj + map.get(obj));
}
//(2)使用迭代器
Set keySet = map.keySet();
Iterator iterator = keySet.Iterator();
while(iterator.hasNext()) {
    Object obj = iterator.next();
    sout(obj + map.get(obj));
}
//第二组：取出所有的value
Collection values = map.values();
//(1)增强for
for(Object obj : values) {
    sout(obj);
}
//(2)使用迭代器
Iterator iterator = values.iterator();
while(iterator.hasNext()) {
    Object obj = iterator.next();
    sout(obj);
}
//第三组：取出所有的Entry
Set entrySet = map.entrySet();
//(1)增强for
for(Object obj : set){
    Map.Entry m = (Map.Entry) entry;
    sout(m.getKey() + m.getValue());
} 
//(2)使用迭代器
Iterator iterator = entrySet.Iterator();
while(iterator.hasNext()) {
    Object obj = iterator.next();
    Map.Entry m = (Map.Entry) entry;
    sout(obj);
}

15.HashMap

1.Map接口的常用实现类：HashMap、Hashtable和Properties

2.HashMap是以K-V对的方式来存储数据的，是使用频率最高的实现类

3.key不能重复，但是值可以重复，允许使用null键和null值

4.如果添加相同的key则会覆盖原来的key-value，等同于修改（key不会替换，value会替换）

5.与HashSet一样，不保证映射的顺序，因为底层是以Hash表的方式来存储的

6.没有实现同步，线程不安全

7.底层机制与HashSet一致，在此不再赘述

16.Hashtable

1.hashtable键和值都不能为null，否则会抛出NullPointer异常

2.使用方式基本和HashMap一样

3.hashtable线程安全，hashMap线程不安全

17.Properties

1.Properties继承自Hashtable类并且实现了Map接口，也是使用一种键值对的形式来保存数据

2.使用特点和hashtable类似

3.Properties还可以用于从xxx.properties文件中，加载数据到Properties类对象，并读取和修改

4.工作后，xxx.Properties常作为配置文件

18.开发中如何选择集合实现类

1.先判断存储的类型(一组对象或一组键值对)

2.一组对象：Collection接口

                ~允许重复：List
                      ~增删多：LinkedList(底层维护了一个双向链表)
                      ~改查多：ArrayList(底层维护了一个Object[]数组)
                ~不允许重复：Set
                      ~无序：HashSet(底层是HashMap，数组 + 链表 +红黑树)
                      ~有序：TreeSet(底层是TreeMap)
                      ~取出与插入顺序一致：LinkedHashSet(底层是LinkedHashSet，数组 + 双向链表)

3.一组键值对：Map接口

                ~键无序：HashMap(数组+链表+红黑树)
                ~键排序：TreeMap
                ~键插入与取出顺序一致：LinkedHashMap
                ~读取文件:Properties

19.TreeSet

1.当我们使用无参构造器，创建TreeSet时，仍然是无序的？

2.使用TreeSet提供的构造器，可以传入一个比较器（匿名内部类），并指定排序规则

TreeSet treeSet = new TreeSet(new Comparator() {
    @Override
    public int compare(Object o1,Object o2) {
        return (String)o2.compareTo(String)(o1)
    }
})

20.Collections工具类

1.Collections工具类是一个操作Set、List和Map等集合的工具类

2.Collections中提供了一系列的静态方法来对集合元素进行排序、查询和修改等操作

排序：

• reverse(List)：反转List中的元素
• shuffle(List): 对List中的元素进行随机排序
• sort(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):使用新值newVal代替所有的oldVal