目录

为什么需要集合

 Collection（单列集合）

 List —— Arraylist

List —— LinkedList

集合的三大遍历方式

Set —— HashSet

Set —— LinkedHashSet

Set —— TreeSet

Map(双列集合)

Map —— HashMap（key，value）

Map —— HashTable

Map —— TreeMap

Map —— LinkedHashMap 

         总结

为什么需要集合

让我们来先思考下为什么需要集合呢？

1. 数组长度固定，一旦确定下来了就不可改变。

2. 数组存放的一组数据类型必须一致（可以是基本数据类型，也可以是引用类型）。

集合的优点:

1. 集合长度是可变的。

2. 集合存放的是引用类型，存放的每个元素都是一个对象。

3. 集合提供了一些列方便的操作对象的方法。

 Collection（单列集合）

 Collection是单列集合的顶层接口，它有两个重要的子接口，分别是List接口和Set接口

list ：元素存放按先后顺序，可重复，支持索引。

set ：元素唯一性，不可重复，内部排序。

 List —— Arraylist

1 Arraylist底层数据结构是数组

2 Arraylist扩容机制，Arraylist扩容倍数为1.5倍

3 Arraylist 线程不安全，没有做线程同步，效率高

List list = new Arraylist();//默认使用无参构造器创建Aarrylist 则它初始化容量是0，第一次添加，则容量扩容为10，//如果需要再次扩容，每次扩容是之前的1.5倍List list = new Arraylist(15);//使用带参构造器创建Arraylist时，第一次扩容则为15，如需再次扩容，则容量为参数的1.5倍

4 Arraylist 常用方法

//演示Arraylist常用方法List list = new Arraylist();list.get(int index);//返回lsit集合中索引对应的元素list.set(int index,Object element);//替换索引中对应的元素list.add(Object element);//添加元素list.remove(Object element);//删除元素list.remove(int index);//删除对应索引的元素list.isEmpty();//判断集合中是否有该元素，返回类型是Boolean类型 list.contains();//判断集合中是否包含该元素，返回类型是Boolean类型list.indexOf();//查询该元素第一次出现的索引list.lastindexOf();//查询该元素最后出现的索引list.size();//返回该集合的元素个数list.subList(int index,int toIndex);//截取index到toIndex中的元素（index包含 toIndex不包含）

1 Vector底层数据结构是数组

2 Vector扩容机制 Vector扩容倍数2倍

//使用无参构造器创建Vector，初始化容量为0，第一次添加容量为10，如需再扩容则容量

是之前的2倍

//使用有参构造器创建Vector，第一次添加容量则为实际传入的参数，如需再次扩容则容量

是之前的2倍

3 Vector 是线程安全的（做了线程同步），效率较低

4 Vetor 和 Arraylist 比较

List —— LinkedList

1 LinkedList底层数据结构是双向列表

2 LinkedList原理

LinkedList维护了两个属性 first 和 last分别指向首节点和尾节点，每个节点（Node）里面又

维护了三个属性（prev，next，item），其中通过prev指向前一个节点，next指向后一个节点形成了双向链表

3 LinkedList 线程不安全，增删快，查询慢

集合的三大遍历方式

 //演示集合三大遍历方式    List list = new ArrayList();   list.add(0,"张三");   list.add(1,"李四");   list.add(2,"王五");   list.add(3,"赵六");   list.add(4,"韩七");   //使用普通for遍历list集合   for (int i = 0; i < list.size(); i++) { System.out.println(list.get(i));   }   //使用增强for遍历list集合   for (Object o : list) { System.out.println(o);  }   //使用迭代且遍历list集合   Iterator iterator = list.iterator();   while (iterator.hasNext()) { Object next = iterator.next(); System.out.println(next);   }

Set —— HashSet

1 HashSet 底层实际上是HashMap（数组+链表+红黑树）

2 HashSet 可以存null值 （但只能有一个），元素唯一且无序，没有索引（不能使用普通for遍历）

3 分析HashSet添加元素如何实现唯一性的

添加元素时，会通过hashCode（）得出hash值，再通过算法得到索引值，索引位有对象则调用equals（）判断是不是同一个对象，是则放弃加入，不是则以链表的方式添加到最后，索引位没对象直接添加。

Set —— LinkedHashSet

1  LinkedHashSet 是HashSet的一个子类

2  LinkedHashSet底层数据结构是LinkedHashMap（数组 + 双向链表）

3  LinkedHashSet是有序且唯一的，底层使用链表维护元素次序，

4  LinkedHashSet非线程安全，效率高

 LinkedHashSet底层维护了一个哈希表和双向链表，每个节点都有两个属性before和after，形成双向链表。

Set —— TreeSet

1 TreeSet底层数据结构是二叉树，元素唯一且有序

2 二叉树结构保证了元素的有序性，有两种排序方式 ：

 1 自然排序（实现Comparable接口,重写compareTo()方法）

 2 定制排序（单独写一个比较器类,实现Comparator接口,重写compare()方法）

 Map(双列集合)

Map（映射集合）是由两个键值对构成的（key ， value），键集合是Set类型，值集合是Collection类型（通俗一点就是key不可重复，value可重复）

Map —— HashMap（key，value）

1 Hashmap底层数据结构是数组+链表+红黑树

2 HashMap 扩容机制

3 HashMap线程不安全，效率高 

4 key value 允许为null（且只能一个）可以理解为key为身份证，value就是名字

身份证是唯一的，名字却可以重复。

5 HashMap扩容机制，初始容量16，2倍扩容

HashMap扩容：第一次添加时，table数组扩容到16，加载因子是0.75，当数组添加到临界值时，就会进行扩容，临界值 = 当前的容量 * 加载因子。扩容倍数为2倍 以此类推使用到了临界值就会进行扩容 。

当 table数组的容量>= 64,且链表的个数= 8 时 ，就会进行树化。

 3 常用方法  

ap map = new HashMap(); map.put(0, "小白"); map.put(1, "小红"); map.put(2, "小蓝");      //获取集合中所有key的元素 for (Object o : map.keySet()) {     System.out.println(o); } //获取集合中所有value的元素 for (Object value : map.values()) {     System.out.println(value); } //获取集合中所有键值对的元素 for (Object o : map.entrySet()) {     System.out.println(o); }

Map —— HashTable

1 HashTable线程安全，效率不高（鱼和熊掌不可兼得，提高安全性，牺牲效率）

2 HashTable key 和 value 都不能为null

3 HashTabel扩容机制 初始化容量11，扩容当前容量2倍加1

Map —— TreeMap

1 Treemap底层数据结构是二叉树，支持排序，默认情况下通过Key值的自然顺序进行排序

2 Treemap非线程安全（未做线程同步）

//演示常用方法//增加元素 put(key,value);将指定映射放入该TreeMap中 putAll(Map map);将指定map放入该TreeMap中//删除元素clear();清除TreeMap中的所有元素remove(Object key);从TreeMap中移除指定key对应的映射//修改元素replace(key,value);替换指定key对应的value值//查找元素boolean containsKey(Object key);判断该TreeMap中是否包含指定key的映射

Map —— LinkedHashMap 

1 LinkedHashMap维护了一个Entry的双向链表，保证了插入的Entry中的顺序

2 LinkeHashMap 非线程安全 允许key，value为null

常用方法

     总结

结合业务逻辑选择用适合的容器，实际开发中80%都是查询，我们要对业务进行分析：

1 存储方式 （单列还是双列）

       Collection 单列：

         允许重复（List）：

             查询多：

                       单线程： Arraylist 底层数组

                       多线程： Vector 底层数组

             增删多：Linedlist 底层双向链表

        不允许重复（Set）：

              无序：HashSet 底层数组+红黑树+链表

              排序：TreeSet 底层二叉树

        Map （key value）：

                 键无序：HashMap 底层数组+红黑树+链表

                 键有序：TreeMap底层二叉树

                插入和取出顺序一致：LinkedHashMap