Java 集合整理

概述：

java的集合类存放在Java.util包中，主要有三种：List(包含Queue)、Set、Map

接口继承关系与实现（见下图）

• Iterator: 迭代器，迭代遍历集合中的元素
• Collection: Collection是集合List、Set、Queue最基本的接口
• Map: 做为映射表的基础接口
  

Iterator(迭代器)

集合很像是生活中的容器，作为容器，JAVA当然不希望局限集合存放元素的类型，集合的容纳性才足够强。但是，这样带来的问题就是我们不能够像for循环遍历数组一样遍历集合，因为我们不知道集合里元素确切的类型。迭代器就是遍历集合的很好解决方案，Iterator是一个对象，它可以遍历并选择序列中的对象，开发者不需要了解该序列的底层结构。

List

特点： 有序可重复
实现类： ArrayList、LinkedList、Vector

- ArrayList(数组实现)

优点： 底层通过数组实现，查询快，效率高
缺点： 线程不安全，增删慢
源码分析： Java集合之ArrayList源码分析

- LinkedList(链表实现)

优点： 底层通过链表实现，增删快（针对首尾的增删），效率高
缺点： 线程不安全，查询慢，随机增删慢（涉及指针的指向操作，但相对于ArrayList的增删开销更小）
源码分析： Java集合之LinkedList源码分析

- Vector(数组实现)

优点： 底层通过数组实现，查询快，线程安全
缺点： 增删慢，效率低

Set

特点： 无序不可重复
实现类： HashSet、TreeSet

- HashSet(哈希表)

• 以散列表形式存储，存入元素必须定义hashCode()
• 通过哈希值存取元素
• 判断是否为同一元素：先判断哈希值相同，再比较equals方法相同则为同一元素；若哈希值相同 equals为false，就会放在同一哈希值下面(形成哈希桶)

- TreeSet(二叉树)

• 保持次序的Set，底层为树结构，使用它可以从Set中提取有序的序列，元素必须实现 Comparable 接口
• 每增加一个元素都会进行排序，将元素插入二叉树指定位置
• 覆写 compare() 函数时，根据返回值来进行排序
• 比较此对象与指定对象的顺序，如果该对象小于、等于或大于指定对象，则分别返回负整数、零或正整数

- LinkHashSet(HashSet+LinkedHashMap)

LinkHashSet继承自HashSet，同时基于LinkedHashMap实现，它所有的方法与操作与HashSet相同，底层用LinkedHashMap存储数据。

Map(映射表)

• Map以 Key-Value 形式存储数据
• Value可以是某个对象甚至某个集合，可以很容易扩展到多维
• 实现类：HashMap、TreeMap、LinkedHashMap、WeakHashMap、ConcurrentHashMap、IdentityHashMap

- HashMap

• HashMap根据键的hashCode值存储数据，因此具有极快的访问速度
• 最多允许一条记录的键为null，允许多条记录的值为null
• hashMap非线程安全，Collections的synchronizedMap方法可以使HashMap具备线程安全，或者直接使用ConcurrentHashMap
• HashMap结构在Java集合之HashMap源码分析中具体介绍

- HashTable(线程安全)

HashTable已经不建议使用，基本功能与HashMap类似，并发性能不如ConcurrentHashMap。不考虑线程安全的情况使用HashMap，考虑线程安全的情况下则使用ConcurrentHashMap更好。

- TreeMap(可排序)

• TreeMap 实现 SortedMap接口，可以根据键排序(默认为升序排序)，也可以指定排序比较器
• 使用迭代器遍历后为排序过的记录
• key必须实现Comparable接口或在构造TreeMap时传入自定义的Comparator，否则会在运行时抛出java.lang.ClassCastException类型的异常。