一、JAVA中的集合分类

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

Collection 和 Map 的区别
Collection类型者，每个位置只有一个元素。
Map类型者，持有 key-value pair，像个小型数据库。

要注意：Collection、List、Set、Map都是接口，不能实例化。 继承自它们的 ArrayList, Vector, HashTable, HashMap是具象class，这些才可被实例化。

二、Collection接口

Collection是最基本的集合接口，声明了适用于JAVA集合(只包括Set和List)的通用方法。
  Collection接口的方法：

boolean add(Object o)    ：向集合中加入一个对象的引用 
void clear()             ：删除集合中所有的对象，即不再持有这些对象的引用   
boolean remove(Object o) ：从集合中删除一个对象的引用 
boolean isEmpty()        ：判断集合是否为空 
boolean contains(Object o) ：判断集合中是否持有特定对象的引用   
Iterartor iterator()       ：返回一个Iterator对象，可以用来遍历集合中的元素 
int size()                 ：返回集合中元素的数目
Object[] toArray()         ：返回一个数组，该数组中包括集合中的所有元素

注意：Collection没有get()方法来取得某个元素。只能通过iterator()遍历元素！

1. Set(集合)

Set是最简单的一种集合，存放的是对象的引用。集合中的对象不按特定的方式排序，没有重复的对象。Set接口主要有三个实现类：

• HashSet：HashSet类按照哈希算法来存取集合中的对象，存取速度较快，存入HashSet的对象必须定义hashCode()。
• TreeSet：TreeSet类底层为树结构，对象以升序顺序存储，访问和遍历的时间很快。
• LinkedHashSet：具有HashSet的查询速度，且内部使用链表维护元素的顺序(插入的次序)。于是在使用迭代器遍历Set时，结果会按元素插入的次序显示。

Set具有与Collection完全一样的接口，因此没有任何额外的功能，实际上Set就是Collection，只是行为不同。
  Set的add()方法是如何判断是否有重复的对象在集合中的呢？由以下代码实现

boolean isExists=false;  
Iterator iterator=set.iterator();  
    while(it.hasNext()){  
        String oldStr=it.next();  
        if(newStr.equals(oldStr)){  
               isExists=true;   
       }  
} 

2. List(链表)

List是有序的Collection，集合中可以存放重复的对象。List接口主要有两个实现类：

• ArrayList：代表长度可以改变的数组，可以对元素进行随机访问，插入和删除元素慢(数组的特征)。
• LinkedList：采用链表的数据结构实现，插入和删除速度快，访问速度慢(链表的特征)。

要注意，因为List是一接口，所以不能被构造，只能创建一个引用：

List list;     //正确，list=null
List list = new ArrayList();  //正确
List list = new List();   //错误的用法

同时也要注意下面两种用法：

//下面这句程序创建了一个ArrayList对象后上溯到了List对象，此时它是一个List对象
//因此有些ArrayList有但是List没有的属性和方法，它就不能再用了。
List list = new ArrayList();  
//下面这句程序创建的对象则保留了ArrayList的所有属性。 
ArrayList list = new ArrayList();  

使用ArrayList list = new ArrayList(); 的问题就在于List有多个实现类，现在你用的是ArrayList，也许哪一天你需要换成其它的实现类，如 LinkedList或者Vector等等，这时你只要改变这一行就行了：List list = new LinkedList()，其它使用了list地方的代码根本不需要改动。 假设你开始用 ArrayList alist = new ArrayList()，这下你有的改了，特别是如果你使用了 ArrayList特有的方法和属性。
  List为Collection添加了许多方法，使得能够向List中间插入与移除元素(这只推 荐LinkedList使用)，同时也提供了一些方法让我们可以对List中的元素进行随机访问。
  List的get(int index) 方法放回集合中由参数index指定的索引位置的对象，下标从“0”开始。下面展示最基本的两种检索集合中的所有对象的方法：

//for循环和get()方法
for(int i=0; i<list.size();i++){  
    System.out.println(list.get(i));  
}  

// 使用 迭代器（Iterator）
Iterator it=list.iterator();  
while(it.hashNext()){   
    System.out.println(it.next());  
}  

LinkList提供了一些功能方法，这些方法 (没有在任何接口或基类中定义过)使得LinkedList可以当作堆栈、队列和双向队列使用：

addFirst()
addLast()
getFirst()
getLast()
removeFirst()
removeLast()
ListIterator  listIterator() ：和标准的Iterator接口比拟，ListIterator可以向List中添加对象，还可以实现逆向（顺序向前）遍历，这些都是Iterator没有的

• 对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针
• 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
• 查找操作indexOf，lastIndexOf，contains等，两者差不多。

三、Map接口

Map是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。Map中不允许有重复的键值。Map接口主要有两个实现类：

1.HashMap
  HashMap的数据结构和哈希表相同。下面看一下HashMap的存储：

int hash=key.hashCode(); //获取key的hashCode，这个值是一个固定的int值
int index=hash%Entry[].length; //获取数组下标：key的hash值对Entry数组长度进行取余
Entry[index]=value;

HashMap会先用key的hash值来检查是否发生了hash碰撞，也就是对应的位置是否为空，这个没问题。问题是当发生了hash碰撞时，就会比较该位置上存储的每一个key是否与新存入的相等，如果相等就替换之，否则就在该位置增加一个值。很明显，你代码中的前后两个key是相同的，所以后面的会替换掉前面的。
  此外介绍一下LinkedHashMap。我们都知道HashMap是无序的，HashMap在put时是根据 key 的 hashcode 进行 hash 然后放入对应的地方。所以在按照一定顺序 put 进 HashMap 中，然后遍历出 HashMap 的顺序跟 put 的顺序不同（除非在 put 的时候 key 已经按照 hashcode 排序号了，这种几率非常小）。JAVA 在 JDK1.4 以后提供了 LinkedHashMap来帮助我们实现了有序的 HashMap：LinkedHashMap 是HashMap的一个子类，它保留插入的顺序，如果需要输出的顺序和输入时的相同，那么就选用 LinkedHashMap。我们来通过一个例子看看如何实现LinkedHashMap。

public static void main(String[] args) {
    ap<String, String> map = new LinkedHashMap<String, String>();
    map.put("apple", "苹果");
    map.put("watermelon", "西瓜");
    map.put("banana", "香蕉");
    map.put("peach", "桃子");

    map.get("banana");
    map.get("apple");

    Iterator iter = map.entrySet().iterator();
    while (iter.hasNext()) {
        Map.Entry entry = (Map.Entry) iter.next();
        System.out.println(entry.getKey() + "=" + entry.getValue());
    }
}

看一下控制台的输出：

apple=苹果
watermelon=西瓜
banana=香蕉
peach=桃子

2.HashTable
  HashTable几乎可以等价于HashMap，但是HashMap是非synchronized，而Hashtable是synchronized，这意味着Hashtable是线程安全的，多个线程可以共享一个Hashtable；而如果没有正确的同步的话，多个线程是不能共享HashMap的。 sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁。

Map常用方法

【Map常用方法】

Object get(Object key) ：返回与给定“键”相关联的“值”
Object put(Object key, Object value)： 向集合中加入元素   
Object remove(Object key)： 删除与KEY相关的元素   
void clear()：从映像中删除所有映射  

【遍历Map的两种方法】
keySet()：keySet是键的集合，Set里面的类型即key的类型。
entrySet()：entrySet是 键-值 对的集合，Set里面的类型是Map.Entry。

//keySet
Map map=new HashMap();
Iterator it=map.keySet().iterator();
Object key;
Object value;
while(it.hasNext()){
     key=it.next();
     value=map.get(key);
     System.out.println(key+":"+value);
}

//entrySet()
Map map=new HashMap();
Iterator it=map.entrySet().iterator();
Object key;
Object value;
while(it.hasNext()){
     Map.Entry entry = (Map.Entry)it.next();
     key=entry.getKey();
     value=entry.getValue();
     System.out.println(key+"="+value);
}

四、数组和集合的比较

世间上本来没有集合，有人想要，所以有了集合。有人想有可以自动扩展的数组,所以有了List ；有的人想有没有重复的数组,所以有了set；有人想有自动排序的组数,所以有了TreeSet、TreeList、Tree** ....。
  几乎所有的集合都是基于数组来实现的。因为集合是对数组做的封装，所以数组永远比任何一个集合要快，但任何一个集合，比数组提供的功能要多。

数组与集合的对比：
1.数组要声明了它容纳的元素的类型，并且同一个数组织能存放类型一样的数据；而集合元素类型是object，即不用声明元素类型。
2.一个数组实例具有固定的大小，不能伸缩；集合则可根据需要动态改变大小。
3.数组要有整数下标才能访问特定的元素。集合也是数据列表却不使用下标访问。
4.数组是一种可读/可写数据结构，没有办法创建一个只读数组。然而集合可以提供ReadOnly方法，以只读方式来使用集合。

Java中有一个Arrays类，专门用来操作array，但是Array还有一个缺点是，无法判断其中实际存有多少元素，length只是告诉我们array的容量。
  如果我们想将一个数组转化为一个List对象，可以使用Arrays.asList()，这个方法会返回一个ArrayList类型的对象，这个ArrayList并不是java.util.ArrayList，它是一个Arrays类中的重新定义的内部类！这个生成的List，它是固定长度的，如果对其进行add或者remove的操作，会抛出UnsupportedOperationException。我们来看看这个ArrayList的实现：

 private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable
    {
        private static final long serialVersionUID = -2764017481108945198L;
    private Object[] a;
    ArrayList(E[] array) {
            if (array==null)
                throw new NullPointerException();
        a = array;
    }
    public int size() {
        return a.length;
    }
    public Object[] toArray() {
        return (Object[])a.clone();
    }
    public E get(int index) {
        return (E)a[index];
    }
    public E set(int index, E element) {
        Object oldValue = a[index];
        a[index] = element;
        return (E)oldValue;
    }
        public int indexOf(Object o) {
            if (o==null) {
                for (int i=0; i<a.length; i++)
                    if (a[i]==null)
                        return i;
            } else {
                for (int i=0; i<a.length; i++)
                    if (o.equals(a[i]))
                        return i;
            }
            return -1;
        }
        public boolean contains(Object o) {
            return indexOf(o) != -1;
        }
    }

在这里，传递基本类型数组时强烈建议转为其封装类对象的数组 int ->Integer ,long->Long ，不然不管数组里面有多少个元素，使用Arrays.asList(array).size()得出来的结果都为1。

五、迭代器

Iterator接口声明了如下方法：

hasNext()：判断集合中元素是否遍历完毕，如果没有，就返回true  
next()   ：返回下一个元素  
remove() ：从集合中删除上一个有next()方法返回的元素。  

而上面我们讲到的LinkList中的ListIterator迭代器包含的方法有：

add(E e): 将指定的元素插入列表，插入位置为迭代器当前位置之前
hasNext()：以正向遍历列表时，如果列表迭代器后面还有元素，则返回 true，否则返回false
hasPrevious():如果以逆向遍历列表，列表迭代器前面还有元素，则返回 true，否则返回false
next()：返回列表中ListIterator指向位置后面的元素
nextIndex():返回列表中ListIterator所需位置后面元素的索引
previous():返回列表中ListIterator指向位置前面的元素
previousIndex()：返回列表中ListIterator所需位置前面元素的索引
remove():从列表中删除next()或previous()返回的最后一个元素（有点拗口，意思就是对迭代器使用hasNext()方法时，删除ListIterator指向位置后面的元素；当对迭代器使用hasPrevious()方法时，删除ListIterator指向位置前面的元素）
set(E e)：从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e

六、集合中的数据结构

(1)哈希表
详情可以看我写的哈希详解，具体的将不再描述。
(2)链表