JAVA 中的 List,Set,Map

List,Set,Map 之间的类关系如下：

Collection   
├List  
│├LinkedList  
│├ArrayList  
│└Vector  
│　└Stack  
└Set  
Map  
├Hashtable  
├HashMap  
└WeakHashMap  

Collection 是最基本的集合接口，代表了一组 Object 的集合。其中的元素根据实例化的子类有不同的规则，有的集合元素可以重复存在，而有些集合元素则是唯一的；有的集合可以排序，有的不能。

只要是 Collection 对象，都可以用同一个方法遍历所有元素 ：

Iterator iterator = list.iterator();
while(iterator.hasNext()) {
    System.out.println(iterator.next());
}

Collection 接口派生的两个接口为 List,Set

List

---

List 接口为一个有序的 Collection ，能够精确的控制每个插入元素的位置，并能够使用类似数组下标的索引来访问元素。

与 Set 不同，List 允许有相同元素。

List 还提供了一个 listIterator() 方法，返回一个 ListIterator 接口，相比于 Iterator, ListIterator 增加了向前遍历、向后遍历 List 、添加元素、set 元素、删除元素等操作：

        LinkedList<String> list = new LinkedList<String>();
        list.add("sdsd");
        list.add("sdsd1");
        list.add("sdsd2");
        list.add("sdsd3");
//        Iterator iterator = list.iterator();
//        while(iterator.hasNext()) {
//            System.out.println(iterator.next());
//        }
        ListIterator<String> iterator = list.listIterator();
        System.out.println("next:" + iterator.next());//next返回下一个值，游标前进
        iterator.add("sdsd9");//add插入在next返回值之前，previous返回值之后,且之后游标会前进
        System.out.println("next2:" + iterator.next());
        iterator.add("sdsd8");
        System.out.println("previous2:" + iterator.previous());//previous返回前一个值，游标后退
        iterator.set("sdsd88");//用指定的值替换next或previous最后一次返回的元素的值
        iterator.add("22");
        iterator.add("11");
        for(int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

实现 List 接口的类常用的有 ArrayList,LinkedList,Vector,Stack

ArrayList

• 可变大小的数组
• 允许所有元素，包括 null
• 非同步 （unsynchronized）
• ArrayList 实例都有一个容量 （Capacity）,即用于存储元素的数组大小。会随着添加新元素而增加大小。当需要插入大量元素时，可以调用 ensureCapacity() 来增加容量以提高效率

LinkedList

• 允许元素为 null
• 额外提供了对首元素和尾元素的 get,remove,insert, 所以 LinkedList 可用于堆栈（stack）、队列(queue)、双向队列(deque)
• 非同步，多线程同时访问该 List 时实现同步的一个方法是：

List syncList = Collections.synchronizedList(new LinkedList<Object>());

Vector

• 与 ArrayList 类似，都是实现了一个可增长的数组
• 同步的，由于 Vector 是同步的，由 Vector 所创建的 Iterator, 虽然与 ArrayList 创建的 Iterator 为同一接口， 但是，当一个 Iterator 被创建并使用，另一个线程改变了 Vector 的状态（例如，添加或删除了一些元素），这时调用 Iterator 的方法会抛出 ConcurrentModificationException,因此必须捕获该异常。

Stack

• Stack 继承自 Vector
• 实现了一个后进先出的堆栈。
• 作为堆栈提供了5个额外的方法：
  • push: 添加一个元素到 Stack 顶部
  • pop: 移除 Stack 元素，并将该移除元素作为函数的返回值返回
  • peek: 获取 Stack 顶部元素，并不移除它
  • search: 检测一个元素在 Stack 中的位置
  • empty: 检测 Stack 是否为空

Set

---

Set 是一种不包含重复元素的 Collection ，通过对象的 equals 方法来对比。最多有一个 null 元素

注意：小心操作可变对象（Mutable Object）。如果 Set 中的元素改变导致 e1.equals(e2) = true 将导致一些问题。

HashSet

• 由 HashMap 作为内部数据支持，存取速度比较快
• 存储顺序与添加元素顺序无任何关联

LinkedHashSet

• 存储顺序为添加元素顺序

TreeSet

• 对 Set 中的元素进行排序存放

Map

---

Map没有继承 Collection 接口

Map 提供 Key 到 Value 的映射。一个 Map中不能包含相同的 Key,每个 Key 只能映射一个 Value。 Map 接口提供3种集合的视图，Map 的内容可以被当作一组 key 集合，或一组 Value 的集合，或一组 Key-Value 的集合。

为了更好的遍历 Map ，可以使用 Map.Entry ，其中 K,V 代表了 Map 的键与值。

调用 Map 的 entrySet 会返回一个 Set<map.entry> 。

遍历 Map 的例子如下：

Map<String, String> map = new HashMap<String, String>();
map.put("test1", "1");
map.put("test1", "2");
map.put("test2", "3");
map.put("test3", "4");
map.put("test4", "5");
map.put("test5", "5");
map.put("test1", "5");
Set<Map.Entry<String, String>> entrySet = map.entrySet();
for(Map.Entry<String, String> entry : entrySet) {
    System.out.println(entry.getKey() + "," + entry.getValue());
}

Hashtable

• 实现一个 Key-Value 映射的哈希表。
• 任何非空对象都可作为 Key 或 Value
• 由于作为 Key 的对象将通过计算其散列函数来确定与之对应的 Value 的位置，因此作为 Key 的对象都必须实现 hashCode 和 equals 方法。如果是自定义的对象作为
Key ，必须要重写 hashCode 和 equals
• 同步的

HashMap

• 与 Hashtable 类似
• 非同步
• 允许 null 作为 Key 或 Value

WeakHashMap

• 以弱键实现的基于哈希表的 Map
• 在 WeakHashMap 中，当某个键不再正常使用时，将自动移除其条目。更精确地说，对于一个给定的键，其映射的存在并不阻止垃圾回收器对该键的丢弃，这就使该键成为可终止的，被终止，然后被回收。丢弃某个键时，其条目从映射中有效地移除，因此，该类的行为与其他的 Map 实现有所不同。
• 其实就是除了本map引用以外, 没有其他对象引用该key对象, 则WeakHashMap会自动移除这个key以及对应的值.

IdentityHashMap

• 此类利用哈希表实现 Map 接口
• 比较键（和值）时使用引用相等性代替对象相等性。换句话说，在 IdentityHashMap 中，当且仅当 (k1==k2) 时，才认为两个键 k1 和 k2 相等（在正常 Map 实现（如 HashMap）中，当且仅当满足下列条件时才认为两个键 k1 和 k2 相等：(k1==null ? k2==null : k1.equals(k2))）。
• 根据此特性可以实现重复Key

• 也就是说, 如果Key是同一个对象才算是键相等, 如果只是值相等, 那么不算相等.例如：

    Map<Pet, String> map = new IdentityHashMap<Pet, String>();
    Pet p = new Pet("eric");
    map.put(new Pet("eric"), "eric");
    map.put(new Pet("eric"), "hello");
    System.out.println("size = " + map.size());
  
    Map<Pet, String> hashMap = new HashMap<Pet, String>();
    hashMap.put(new Pet("eric"), "eric");
    hashMap.put(new Pet("eric"), "hello");
    System.out.println("hashMap size = " + hashMap.size());
    //Pet中的equals中只要name相等, 就算这两个pet对象相等. 
    //执行结果为: size = 2 ;hashMap size = 1

总结

• 涉及到堆栈，队列等操作，应该考虑用 List
• 需要快速插入，删除，使用 LinkedList
• 需要快速随机访问元素，使用 ArrayList
• 单线程环境考虑非同步类，多线程考虑同步类