1.集合

堆栈和队列数据结构的特点：堆栈数据结构先进后出，后进先出；队列结构是先进先出，后进后出。

1.1 什么是集合

存储对象的容器，面向对象语言对事物的体现都是以对象的形式，所以为了方便对多个对象的操作，存储对象，集合是存储对象最常用的一种方式。

集合的出现就是为了持有对象。集合中可以存储任意类型的对象,而且长度可变。在程序中有可能无法预先知道需要多少个对象, 那么用数组来装对象的话, 长度不好定义, 而集合解决了这样的问题。

1.2集合和数组的区别

数组和集合类都是容器。

数组长度是固定的，集合长度是可变的。数组中可以存储基本数据类型，集合只能存储对象数组中存储数据类型是单一的，集合中可以存储任意类型的对象。缺点主要体现在存储类型单一，操作复杂。

集合类的特点：用于存储对象，长度是可变的，可以存储不同类型的对象。

1.3.集合的分类

集合主要实现：1：将对象添加到集合

2：从集合中删除对象

3: 从集合中查找一个对象

4：从集合中修改一个对象就是增删改查

注意：集合和数组中存放的都是对象的引用而非对象本身

Java工程师对不同的容器进行了定义,虽然容器不同,但是还是有一些共性可以抽取最后抽取了一个顶层接口,那么就形成了一个集合框架。如何学习呢?当然是从顶层学起,顶层里边具有最共性,最基本的行为。具体的使用,就要选择具体的容器了。为什么? 因为不断向上抽取的东西有可能是不能创建对象的.抽象的可能性很大，并且子类对象的方法更多一些. 所以是看顶层,创建底层。那么集合的顶层是什么呢 叫做Collection。

---|Collection: 单列集合

---|List: 有存储顺序, 可重复

---|ArrayList: 数组实现, 查找快, 增删慢。由于是数组实现,在增和删的时候会牵扯到数组增容, 以及拷贝元素.所以慢。数组是可以直接按索引查找, 所以查找时较快。

---|LinkedList: 链表实现, 增删快, 查找慢。由于链表实现,增加时只要让前一个元素记住自己就可以,删除时让前一个元素记住后一个元素, 后一个元素记住前一个元素.这样的增删效率较高但查询时需要一个一个的遍历, 所以效率较低

---|Vector: 和ArrayList原理相同, 但线程安全, 效率略低。和ArrayList实现方式相同,但考虑了线程安全问题, 所以效率略低

---|Set: 无存储顺序, 不可重复

---|HashSet

---|TreeSet

---|LinkedHashSet

---| Map: 键值对

---|HashMap

---|TreeMap

---|HashTable

---|LinkedHashMa

为什么出现这么多集合容器，因为每一个容器对数据的存储方式不同，这种存储方式称之为数据结构(data structure。

注意：集合和数组中存放的都是对象的引用。

1.4. 什么时候该使用什么样的集合

1.4.1Collection

我们需要保存若干个对象的时候使用集合。

1.4.2 List

如果我们需要保留存储顺序, 并且保留重复元素, 使用List；

如果查询较多, 那么使用ArrayList

如果存取较多, 那么使用LinkedList

如果需要线程安全, 那么使用Vector

1.4.3 Set

如果我们不需要保留存储顺序, 并且需要去掉重复元素, 使用Set.

如果我们需要将元素排序, 那么使用TreeSet

如果我们不需要排序, 使用HashSet, HashSet比TreeSet效率高.

如果我们需要保留存储顺序, 又要过滤重复元素, 那么使用LinkedHashSet

2.集合类(Collection)

Collection接口有两个子接口：List(链表|线性表)和Set(集)。

特点：Collection中描述的是集合共有的功能(CRUD)，List可存放重复元素，元素存取是有序的； Set不可以存放重复元素，元素存取是无序的

java.util.Collection

----| Collection 描述所有接口的共性

----| List接口 可以有重复元素的集合

----| Set 接口 不可以有重复元素的集合

2.1.Collection接口的共性方法

增加：

1：add()将指定对象存储到容器中，add方法的参数类型是Object，便于接收任意对象

2：addAll() 将指定集合中的元素添加到调用该方法和集合中

删除：

3：remove() 将指定的对象从集合中删除

4：removeAll() 将指定集合中的元素删除

修改

5：clear() 清空集合中的所有元素

判断

6：isEmpty() 判断集合是否为空

7：contains() 判断集合何中是否包含指定对象

8：containsAll() 判断集合中是否包含指定集合，使用equals()判断两个对象是否相等

获取:

9：int size() 返回集合容器的大小

转成数组

10：toArray()集合转换数组

11. hasNext()：判断集合中元素是否遍历完毕，如果没有，就返回true

12. next() ：返回下一个元素

13. remove()：从集合中删除上一个有next()方法返回的元素。

2.2 List

2.2.1 List接口及其特有方法

----| Iterable接口，Iterator iterator()

------| Collection接口

--------| List 接口，元素可以重复，允许在指定位置插入元素，并通过索引来访问元素

特有方法

增加

1.void add(int index, Eelement)指定位置添加元素

2.boolean addAll(int index, Collection c) 指定位置添加集合

删除

E remove(int index)删除指定位置元素

修改

E set(int index, E element)返回的是需要替换的集合中的元素

查找

E get(int index)

int indexOf(Object o)// 找不到返回-1

lastIndexOf(Object o)

求子集合

List subList(int fromIndex, int toIndex) //不包含toIndex

2.2.2 ArrayList

--| Iterable

----| Collection

------| List

---------| ArrayList底层采用数组实现，默认10.每次增长60%,查询快，增删慢。

---------| LinkedList

因为数组的内存空间地址是连续的，所以实现查找快,增删慢.

ArrayList底层维护了一个Object[]用于存储对象，默认数组的长度是10。可以通过 new ArrayList(20)显式的指定用于存储对象的数组的长度。

当默认的或者指定的容量不够存储对象的时候，容量自动增长为原来的容量的1.5倍。

由于ArrayList是数组实现, 在增和删的时候会牵扯到数组增容, 以及拷贝元素. 所以慢。数组是可以直接按索引查找, 所以查找时较快。

可以考虑,假设向数组的0角标未知添加元素,那么原来的角标位置的元素需要整体往后移,并且数组可能还要增容,一旦增容,就需要要将老数组的内容拷贝到新数组中.所以数组的增删的效率是很低的.

2.2.3 LinkedList

LinkedList:链表实现, 增删快, 查找慢。

由于LinkedList:在内存中的地址不连续,需要让上一个元素记住下一个元素.所以每个元素中保存的有下一个元素的位置.虽然也有角标,但是查找的时候,需要从头往下找,显然是没有数组查找快的.但是,链表在插入新元素的时候,只需要让前一个元素记住新元素,让新元素记住下一个元素就可以了.所以插入很快.

由于链表实现,增加时只要让前一个元素记住自己就可以, 删除时让前一个元素记住后一个元素,后一个元素记住前一个元素.这样的增删效率较高。

但查询时需要一个一个的遍历, 所以效率较低。

特有方法有：

addFirst(E e)

addLast(E e)

getFirst()

getLast()

removeFirst()

removeLast()

如果集合中没有元素，获取或者删除元素抛：NoSuchElementException

数据结构

1：栈：先进后出

push()

pop()

2：队列：先进先出

offer()

poll()

3：返回逆序的迭代器对象

descendingIterator()返回逆序的迭代器对象

可以使用该集合去模拟出队列(先进先出) 或者堆栈(后进先出) 数据结构。

//堆栈(后进先出) 数据结构

public class Demo3 {

public static void main(String[] args) {

LinkedList list = new LinkedList();

// 压栈，先进后出

list.push("西游记");

list.push("三国演义");

list.push("石头记");

list.push("水浒传");

System.out.println(list);

// 弹栈

String str1 = (String) list.pop();

System.out.println(str1);

String str2 = (String) list.pop();

System.out.println(str2);

String str3 = (String) list.pop();

System.out.println(str3);

String str4 = (String) list.pop();

System.out.println(str4);

System.out.println(list.size());// 0

System.out.println(list);//[]

}

}

队列，先进先出

public class Demo3 {

public static void main(String[] args) {

LinkedList list = new LinkedList();

// 队列，先进先出

list.offer("西游记");

list.offer("三国演义");

list.offer("石头记");

list.offer("水浒传");

System.out.println(list);

// 出队列

System.out.println(list.poll());

System.out.println(list.poll());

System.out.println(list.poll());

System.out.println(list.poll());

System.out.println(list.size());

System.out.println(list.peek()); // 获取队列的头元素，但是不删除

System.out.println(list.peekFirst()); // 获取队列的头元素，但是不删除

System.out.println(list.peekLast()); // 获取队列的最后一个元素但是不删除

}

}

ArrayList 和LinkedList的存储查找的优缺点：1、ArrayList 是采用动态数组来存储元素的，它允许直接用下标号来直接查找对应的元素。但是，但是插入元素要涉及数组元素移动及内存的操作。总结：查找速度快，插入操作慢。

2、LinkedList 是采用双向链表实现存储，按序号索引数据需要进行前向或后向遍历，但是插入数据时只需要记录本项的前后项即可，所以插入速度较快

问题：有一批数据要存储，要求存储这批数据不能出现重复数据，ArrayList、LinkedList都没法满足需求。解决办法：使用 set集合。

2.3 Set集合

Set是最简单的一种集合。集合中的对象不按特定的方式排序，并且没有重复对象。存入Set的每个元素都必须是唯一的，因为Set不保存重复元素。加入Set的元素必须定义equals()方法以确保对象的唯一性。Set与Collection有完全一样的接口。Set接口不保证维护元素的次序。Set接口主要实现了两个实现类：HashSet： HashSet类按照哈希算法来存取集合中的对象，存取速度比较快。为快速查找设计的Set。存入HashSet的对象必须定义hashCode()。

TreeSet ：TreeSet类实现了SortedSet接口，能够对集合中的对象进行排序。保存次序的Set,底层为树结构。使用它可以从Set中提取有序的序列。

LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示

Set的功能方法Set具有与Collection完全一样的接口，因此没有任何额外的功能，不像前面有两个不同的List。实际上Set就是Collection,只是行为不同。(这是继承与多态思想的典型应用：表现不同的行为。)Set不保存重复的元素(至于如何判断元素相同则较为负责)。

3.Map映射

Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。

Map 的常用方法：

1 添加，删除操作：

Object put(Object key, Object value)： 向集合中加入元素

Object remove(Object key)： 删除与KEY相关的元素

void putAll(Map t)： 将来自特定映像的所有元素添加给该映像

void clear()：从映像中删除所有映射

2 查询操作：Object get(Object key)：获得与关键字key相关的值。Map集合中的键对象不允许重复，也就说，任意两个键对象通过equals()方法比较的结果都是false.，但是可以将任意多个键独享映射到同一个值对象上。

put(Object key, Object value)添加一个“值”(想要得东西)和与“值”相关联的“键”(key)(使用它来查找)。

get(Object key)返回与给定“键”相关联的“值”。

containsKey()和containsValue()测试Map中是否包含某个“键”或“值”。

执行效率是Map的一个大问题。看看get()要做哪些事，就会明白为什么在ArrayList中搜索“键”是相当慢的。而这正是HashMap提高速度的地方。HashMap使用了特殊的值，称为“散列码”(hashcode)，来取代对键的缓慢搜索。“散列码”是“相对唯一”用以代表对象的int值，它是通过将该对象的某些信息进行转换而生成的。所有Java对象都能产生散列码，因为hashCode()是定义在基类Object中的方法。HashMap就是使用对象的hashCode()进行快速查询的。此方法能够显着提高性能。

Map : 维护“键值对”的关联性，使你可以通过“键”查找“值”

HashMap：Map基于散列表的实现。插入和查询“键值对”的开销是固定的。可以通过构造器设置容量capacity和负载因子load factor，以调整容器的性能。

LinkedHashMap：类似于HashMap，但是迭代遍历它时，取得“键值对”的顺序是其插入次序，或者是最近最少使用(LRU)的次序。只比HashMap慢一点。而在迭代访问时发而更快，因为它使用链表维护内部次序。

TreeMap ： 基于红黑树数据结构的实现。查看“键”或“键值对”时，它们会被排序(次序由Comparabel或Comparator决定)。TreeMap的特点在 于，你得到的结果是经过排序的。TreeMap是唯一的带有subMap()方法的Map，它可以返回一个子树。

WeakHashMao ：弱键(weak key)Map，Map中使用的对象也被允许释放: 这是为解决特殊问题设计的。如果没有map之外的引用指向某个“键”，则此“键”可以被垃圾收集器回收。

IdentifyHashMap： : 使用==代替equals()对“键”作比较的hash map。专为解决特殊问题而设计。

4.list与Set、Map区别及适用场景

1、List,Set都是继承自Collection接口，Map则不是;

2、List特点：元素有放入顺序，元素可重复，Set特点：元素无放入顺序，元素不可重复，重复元素会覆盖掉，(注意：元素虽然无放入顺序，但是元素在set中的位置是有该元素的HashCode决定的，其位置其实是固定的，加入Set的Object必须定义equals()方法，另外list支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。)

3.Set和List对比：Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变。

4.Map适合储存键值对的数据

5.线程安全集合类与非线程安全集合类LinkedList、ArrayList、HashSet是非线程安全的，Vector是线程安全的;

HashMap是非线程安全的，HashTable是线程安全的;

StringBuilder是非线程安全的，StringBuffer是线程安全的。

5.ArrayList与LinkedList的区别和适用场景

Arraylist：优点：ArrayList是实现了基于动态数组的数据结构,因为地址连续，一旦数据存储好了，查询操作效率会比较高(在内存里是连着放的)。

缺点：因为地址连续，ArrayList要移动数据,所以插入和删除操作效率比较低。

LinkedList：优点：LinkedList基于链表的数据结构,地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址，对于新增和删除操作add和remove，LinedList比较占优势。LinkedList适用于要头尾操作或插入指定位置的场景

缺点：因为LinkedList要移动指针,所以查询操作性能比较低。

适用场景分析：当需要对数据进行对此访问的情况下选用ArrayList，当需要对数据进行多次增加删除修改时采用LinkedList。

6.ArrayList与Vector的区别和适用场景

ArrayList有三个构造方法：

public ArrayList(int initialCapacity)//构造一个具有指定初始容量的空列表。

public ArrayList()//构造一个初始容量为10的空列表。

public ArrayList(Collection<?extends E> c)//构造一个包含指定 collection 的元素的列表

Vector有四个构造方法：

public Vector()//使用指定的初始容量和等于零的容量增量构造一个空向量。

public Vector(int initialCapacity)//构造一个空向量，使其内部数据数组的大小，其标准容量增量为零。

public Vector(Collection<?extends E> c)//构造一个包含指定collection中的元素的向量

public Vector(int initialCapacity,int capacityIncrement)//使用指定的初始容量和容量增量构造一个空的向量

ArrayList和Vector都是用数组实现的，主要有这么三个区别：1.Vector是多线程安全的，线程安全就是说多线程访问同一代码，不会产生不确定的结果。而ArrayList不是，这个可以从源码中看出，Vector类中的方法很多有synchronized进行修饰，这样就导致了Vector在效率上无法与ArrayList相比；

2.两个都是采用的线性连续空间存储元素，但是当空间不足的时候，两个类的增加方式是不同。

3.Vector可以设置增长因子，而ArrayList不可以。

4.Vector是一种老的动态数组，是线程同步的，效率很低，一般不赞成使用。

适用场景分析：1.Vector是线程同步的，所以它也是线程安全的，而ArrayList是线程异步的，是不安全的。如果不考虑到线程的安全因素，一般用ArrayList效率比较高。

2.如果集合中的元素的数目大于目前集合数组的长度时，在集合中使用数据量比较大的数据，用Vector有一定的优势。

7.HashSet与Treeset的适用场景1.TreeSet是二差树(红黑树的树据结构)实现的,Treeset中的数据是自动排好序的，不允许放入null值

2.HashSet是哈希表实现的,HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束

3.HashSet要求放入的对象必须实现HashCode()方法，放入的对象，是以hashcode码作为标识的，而具有相同内容的String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例

适用场景分析:HashSet是基于Hash算法实现的，其性能通常都优于TreeSet。为快速查找而设计的Set，我们通常都应该使用HashSet，在我们需要排序的功能时，我们才使用TreeSet。

8.HashMap与TreeMap、HashTable的区别及适用场景HashMap：非线性安全，基于哈希表实现。使用HashMap要求添加的键类明确定义了hashCode()和equals()[可以重写hashCode()和equals()]，为了优化HashMap空间的使用，您可以调优初始容量和负载因子。

TreeMap：非线程安全基于红黑树实现。TreeMap没有调优选项，因为该树总处于平衡状态。

适用场景分析：HashMap和HashTable:HashMap去掉了HashTable的contains方法，但是加上了containsValue()和containsKey()方法。HashTable同步的，而HashMap是非同步的，效率上比HashTable要高。HashMap允许空键值，而HashTable不允许。

HashMap：适用于Map中插入、删除和定位元素。

Treemap：适用于按自然顺序或自定义顺序遍历键(key)。

9.总结与注意

9.1总结

1.如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

2.如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。

3.在除需要排序时使用TreeSet,TreeMap外,都应使用HashSet,HashMap,因为他们的效率更高。

4.要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。

5.容器类仅能持有对象引用(指向对象的指针)，而不是将对象信息copy一份至数列某位置。一旦将对象置入容器内，便损失了该对象的型别信息。

6.尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

9.2注意

1、Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素。

2、Set和Collection拥有一模一样的接口。

3、List，可以通过get()方法来一次取出一个元素。使用数字来选择一堆对象中的一个，get(0)...。(add/get)

4、一般使用ArrayList。用LinkedList构造堆栈stack、队列queue。

5、Map用 put(k,v) / get(k)，还可以使用containsKey()/containsValue()来检查其中是否含有某个key/value。HashMap会利用对象的hashCode来快速找到key。

6、Map中元素，可以将key序列、value序列单独抽取出来。

使用keySet()抽取key序列，将map中的所有keys生成一个Set。

使用values()抽取value序列，将map中的所有values生成一个Collection。