基础结构和特点
- Map
键映射到值的对象。一个映射不能包含重复的键；每个键最多只能映射到一个值。
某些映射实现可明确保证其顺序，如 TreeMap 类；另一些映射实现则不保证顺序，如 HashMap 类。
Map中元素，可以将key序列、value序列单独抽取出来。
使用keySet()抽取key序列，将map中的所有keys生成一个Set。
使用values()抽取value序列，将map中的所有values生成一个Collection。
为什么一个生成Set，一个生成Collection？那是因为，key总是独一无二的，value允许重复。
- Set
一个不包含重复元素的 collection。更确切地讲，set 不包含满足 e1.equals(e2) 的元素对 e1 和 e2，并且最多包含一个 null 元素。
不可随机访问包含的元素
只能用Iterator实现单向遍历
Set 没有同步方法
- List
可随机访问包含的元素
元素是==有序==的
可在任意位置增、删元素
不管访问多少次，元素位置不变
允许重复元素
用Iterator实现单向遍历，也可用ListIterator实现双向遍历
- Queue
先进先出
Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。 如果要使用前端而不移出该元素，使用element()或者peek()方法。
值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
Queue 实现通常不允许插入 null 元素，尽管某些实现（如 LinkedList）并不禁止插入 null。即使在允许 null 的实现中，也不应该将 null 插入到 Queue 中，因为 null 也用作 poll 方法的一个特殊返回值，表明队列不包含元素。
- Stack
后进先出
Stack继承自Vector（可增长的对象数组），也是同步的
它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。
- 用法
如果涉及到堆栈、队列等操作，应该考虑用List；
对于需要快速插入，删除元素，应该使用LinkedList；
如果需要快速随机访问元素，应该使用ArrayList。
如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高 - Map
概述:
- List , Set, Map都是接口，前两个继承至Collection接口，Map为独立接口
- Set下有HashSet，LinkedHashSet，TreeSet
- List下有ArrayList，Vector，LinkedList
- Map下有Hashtable，LinkedHashMap，HashMap，TreeMap
- Collection接口下还有个Queue接口，有PriorityQueue类
ArrayList、LinkedList、Vector的区别
List的三个子类的特点
ArrayList:
- 底层数据结构是数组，查询快，增删慢。
- 线程不安全，效率高。
Vector:
- 底层数据结构是数组，查询快，增删慢。
- 线程安全，效率低。
- Vector相对ArrayList查询慢(线程安全的)。
- Vector相对LinkedList增删慢(数组结构)。
LinkedList
- 底层数据结构是链表，查询慢，增删快。
- 线程不安全，效率高。
Vector和ArrayList的区别
- Vector是线程安全的,效率低。
- ArrayList是线程不安全的,效率高。
- 共同点:底层数据结构都是数组实现的,查询快,增删慢。
ArrayList和LinkedList的区别
- ArrayList底层是动态数组结构,查询和修改快。
- LinkedList底层是链表结构的,增和删比较快,查询和修改比较慢。
- 共同点:都是线程不安全的
hashmap
什么是HashMap
HashMap实现了Map接口，Map接口对键值对进行映射。Map中不允许重复的键。Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。HashMap允许键和值为null。HashMap是非synchronized的，但collection框架提供方法能保证HashMap synchronized，这样多个线程同时访问HashMap时，能保证只有一个线程更改Map。
hashmap结构；
JAVA7:HashMap 里面是一个数组，然后数组中每个元素是一个单向链表。包含四个属性：key, value, hash 值和用于单向链表的 next；
Java8 对 HashMap 进行了一些修改，最大的不同就是利用了红黑树，所以其由 数组+链表+红黑树组成；
查找时需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。一棵含有n个节点的红黑树的高度至多为2log(n+1).
Entry节点在插入链表的方式
java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上面的例子一样，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。（Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系）
但是，在java8之后，都是所用尾部插入了。
什么对象能做为key?
重写过hashCode和equals的对象，才能做为key，如果要将对象做为key，需要重写hashCode和equals。null可以做为key值，null也可以做为value值。
时间复杂度：理想情况下是 O(1)的，但是实际中会出现 hash 碰撞，导致无法达到效果。
hashtable,concurrentHashMap,hashtable比较
- Hashtable：底层数组+链表实现，无论key还是value都不能为null，线程安全，实现线程安全的方式是在修改数据时锁住整个HashTable，效率低，ConcurrentHashMap做了相关优化；
- Hashmap：底层数组+链表实现，可以存储null键和null值，线程不安全。当我们将键值对传递给put()方法时，它调用键对象的hashCode()方法来计算hashcode，然后找到bucket位置来存储值对象。当获取对象时，通过键对象的equals()方法找到正确的键值对，然后返回值对象
。 - ConcurrentHashMap：分段锁概念实现，相当于多个hashtable，底层采用分段的数组+链表实现，线程安全。
什么是HashSet
HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要先确保对象重写equals()和hashCode()方法，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。
public boolean add(Object o)方法用来在Set中添加元素，当元素值重复时则会立即返回false，如果成功添加的话会返回true。
public Object put(Object Key,Object value)方法用来将元素添加到map中。
hashmap和hashset比较
| HashMap | HashSet |
|---|---|
| HashMap实现了Map接口 | HashSet实现了Set接口 HashMap储存键值对 |
| 使用put()方法将元素放入map中 | 使用add()方法将元素放入set |
| HashMap中使用键对象来计算hashcode值 | HashSet使用成员对象来计算hashcode值，对于两个对象来说hashcode可能相同，所以equals()方法用来判断对象的相等性，如果两个对象不同的话，那么返回false |
| HashMap比较快，因为是使用唯一的键来获取对象 | HashSet较HashMap来说比较慢 |