java集合(ArrayList/Vector/LinkedList/HashSet/TreeSet/ArrayDeque/PriorityQueue/HashMap/HashTable/TreeM)

此图来源于：http://blog.****.net/u010887744/article/details/50575735

大图可以点此访问：https://img-blog.****.net/20160124221843905

Java 集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。
Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类。
最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

List
List接口是一个**有序(插入输出的顺序一致，并不是说按大小排序)**的 Collection，使用此接口能够精确的控制每个元素插入的位置，能够通过索引(元素在List中位置，类似于数组的下标)来访问List中的元素，第一个元素的索引为 0，而且允许有相同的元素。

list实现类有：ArrayList/Vector/LinkedList，都是可伸缩数组。

其中ArrayList/Vector是基于Object[] array实现的，使用连续的空间，支持用序号访问元素。其中Vector是线程安全的（Vector 的所有方法加上了 synchronized 关键字），ArrayList是线程不安全的。java中Stack是Vector的一个子类。

LinkedList采用双向链表实现。非线程安全。

Set
Set是一个接口，只存储不相同的数据。Set都是基于Map的，即将数据存储在Map的key中，将value置为null。

Set实现类有：HashSet/TreeSet

HashSet判断是否有重复数据： HashSet 的 add() 方法添加集合元素时实际上转变为调用 HashMap 的 put() 方法来添加 key-value 对。故其实是调用调用hashCode方法判hashCode是否已经存在，如不存在则直接插入元素；如果已存在则调用Object对象的equals方法判断是否返回true，如果为true则说明元素已经存在，如为false则插入元素。

TreeSet判断是否有重复数据：TreeSet 的 add() 方法添加集合元素时实际上转变为TreeMap中调用put方法添加键值对，即调用compareTo对所有键进行比较。

Queue
Queue接口扩展了java.util.Collection接口，但是Queue使用时要尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素，它们的优点是通过返回值可以判断成功与否，而add()和remove()方法在失败的时候会抛出异常。peek（）可以使用队列头部元素而不移出。

Queue的实现类有：ArrayDeque/PriorityQueue/LinkedList
值得注意的是LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。（LinkedList也是List）

**PriorityQueue：**底层是最小堆，所以要使用最小堆的时候可以用PriorityQueue，用最大堆的时候，可以改变PriorityQueue。

PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>() {
		@Override  //用PriorityQueue实现大根堆只需要重写compare，11是默认大小
		public int compare(Integer o1, Integer o2) {
			// TODO Auto-generated method stub
			return o2.compareTo(o1);
		}
	});

Deque接口：Deque接口是Queue接口的子接口，代表一个双端队列。同时Deque不仅可以作为双端队列使用，而且可以被当成栈来使用，所以可以使用出栈，入栈的方法。其实现类为ArrayDeque。现在已经不建议用Stack做栈，而建议用ArrayDeque做栈。

LinkedList实现类
LinkedList类是List接口的实现类，但是同时也是Deque接口实现类，所以LinkedList既可以当做双端队列来使用，也可以当做栈来使用

Map
Map 接口存储一组键值对象，提供key（键）到value（值）的映射。

实现类有HashMap/HashTable/TreeMap/WeakHashMap

hashmap是hashtable的轻量级实现；

hashmap和hashtable的区别：
1、hashmap线程不安全，null可以作为键，这样的键只有一个，但可以有一个或多个键所对应的值为null；
hashtable线程安全，不允许允许null作为key和value值；
2、HashMap的迭代器（Iterator）是fail-fast迭代器，而Hashtable的enumerator迭代器
3、HashMap的默认大小是16，扩容方法是old2，故hashmap的存储数组一直是2的指数，每次扩容时，原来数组中的元素依次重新计算存放位置，并重新插入
Hashtable默认数组大小事11，的扩容方法是old2+1
4、HashMap把Hashtable的contains方法去掉了，变成了containsvalue和containsKey。

hashmap和hashtable的相同点：
1、hashmap和hashtable都不允许有重复的键（key值），即，每个键只能映射一个值。
2、都是用数组链表存储数据的（但是hashmap在jdk1.8后，当链表长度超过阈值时（默认为8），用红黑树代替链表）

LinkedHashMap是HashMap的一个子类 HashMap有一个问题，就是迭代HashMap的顺序并不是HashMap放置的顺序，也就是无序。这个时候，LinkedHashMap就闪亮登场了，它虽然增加了时间和空间上的开销，但是通过维护一个运行于所有条目的双向链表，LinkedHashMap保证了元素迭代的顺序。该迭代顺序可以是插入顺序或者是访问顺序。

hashtable和ConcurrentHashMap都是线程相同的，ConcurrentHashMap用来替代hashtable。
hashtable和ConcurrentHashMap的区别：
hahstable实现线程安全的方式是在修改数据时锁住整个HashTable，效率低；
ConcurrentHashMap每次锁住一个segment，只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。
ConcurrentHashMap的概念：
1、底层采用分段的数组+链表实现，线程安全
2、使用锁分段技术确保线程安全
锁分段技术：首先将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。

目前，hashtable已经不常用了，如果想要线程安全，可以用ConcurrentHashMap；

TreeMap实现了SortMap接口，所以键值对按照顺序存放。

WeakHashMap和HashMap类似，不同之处在于WeakHashMap的Key采用“弱引用”，即WeakHashMap中的key不被外部引用时，就可以被垃圾回收器回收，而HashMap中的key是强引用，只有将key删除了，才能被立即回收器回收。

Map.Entry
Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry<K,V>。它表示Map中的一个实体（一个key-value对）。接口中有getKey(),getValue方法。即可以同时返回key和value。

Map<String, String> map = new HashMap<String, String>();    
  map.put("key1", "value1");    
  map.put("key2", "value2");    
  map.put("key3", "value3");    
      
  //第一种：普遍使用，二次取值    
  System.out.println("通过Map.keySet遍历key和value：");    
  for (String key : map.keySet()) {    
   System.out.println("key= "+ key + " and value= " + map.get(key));    
  }    
      
  //第二种    
  System.out.println("通过Map.entrySet使用iterator遍历key和value：");    
  Iterator<Map.Entry<String, String>> it = map.entrySet().iterator();    
  while (it.hasNext()) {    
   Map.Entry<String, String> entry = it.next();    
   System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());    
  }    
      
 //第三种：推荐，尤其是容量大时</span>    
  System.out.println("通过Map.entrySet遍历key和value");    
  for (Map.Entry<String, String> entry : map.entrySet()) {    
   System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());    
  }    
    
  //第四种    
  System.out.println("通过Map.values()遍历所有的value，但不能遍历key");    
  for (String v : map.values()) {    
   System.out.println("value= " + v);    
  }

代码转自https://blog.****.net/yaomingyang/article/details/78748130