一、概述

要了解Java的集合，就要先说说数据结构。

数据结构描述数据元素的集合及元素间的关系和运算。在数据结构中，元素之间的相互关系称之为数据的逻辑结构。按照逻辑关系的不同将数据结构分为线性结构和非线性结构。其中，线性结构包括线性表、栈、队列和串。非线性结构包括树和图。数据元素及元素间关系的存储形式称之为存储结构，按存储形式的不同分为顺序存储和链式存储。

在Java中主要逻辑结构有线性结构Collection和非线性结构Map。

二、Collection

Collection是一种线性结构，线性结构包括线性表、栈、队列和串。在Java中Collection有三种类型，即List、Set 和 Queue，而线性结构的串对应的是Java字符串。

List，数据元素有序，按线程是否安全分为线程安全的：Vector、Stack；线程不安全的：LinkedList、ArrayList。ArrayList：底层数据结构是数组，查询快，增删慢，线程不安全，效率高，可以存储重复元素；LinkedList 底层数据结构是链表，查询慢，增删快，线程不安全，效率高，可以存储重复元素；Vector:底层数据结构是数组，查询快，增删慢，线程安全，效率低，可以存储重复元素。

Set，数据元素无序，且不可重复。主要有HashSet、LinkedHashSet、TreeSet，HashSet底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储null元素，元素的唯一性是靠所存储元素类型是否重写hashCode()和equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性；LinkedHashSet底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。线程不安全，效率高；TreeSet底层数据结构采用二叉树来实现，元素唯一且已经排好序；唯一性同样需要重写hashCode和equals()方法，二叉树结构保证了元素的有序性。根据构造方法不同，分为自然排序（无参构造）和比较器排序（有参构造），自然排序要求元素必须实现Compareable接口，并重写里面的compareTo()方法，元素通过比较返回的int值来判断排序序列，返回0说明两个对象相同，不需要存储；比较器排需要在TreeSet初始化是时候传入一个实现Comparator接口的比较器对象，或者采用匿名内部类的方式new一个Comparator对象，重写里面的compare()方法；

三、Map

Map是非线性结构，是以Key/Value形式进行数据存储的。主要有Hashtable、HashMap、LinkedHashMap、WeakHashMap、TreeMap、IdentifyHashMap，其中Hashtable是线程安全的。在jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。IdentityHashMap和HashMap的具体区别，IdentityHashMap使用 == 判断两个key是否相等，而HashMap使用的是equals方法比较key值。

四、集合的迭代

4.1 Collection迭代

Collection继承了接口Iterable，故所有直接或间接实现了接口Collection的集合类都是可迭代的，都可以通过调用.iterator()方法得到一个属于自身的迭代器。在Java中可以有如下集中迭代方式：

//迭代器迭代，最基本的方式
Iterator it = list.iterator();
while(it.hasNext()) {
　　Object obj = it.next();
}
//第一种方式的for形式
for(Iterator iterator = list.iterator();iterator.hasNext();){                    
    int i = (Integer) iterator.next();                   
    System.out.println(i);               
}
//普通for循环
for(int i = 0 ;i{});
//java8流迭代
list.stream().foreach(object->{});

4.2 Map迭代

因Map是一种K/V形式的数据结构，所以map的迭代与Collection不同，主要有如下几种方式：

//遍历所有key，然后获取value
for (Integer in : map.keySet()) {
    String str = map.get(in);//得到每个key多对用value的值
}
//entrySet迭代
Iterator> it = map.entrySet().iterator();
while (it.hasNext()) {
     Map.Entry entry = it.next();
       System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//entrySet迭代的for循环形式
for (Map.Entry entry : map.entrySet()) {
    //Map.entry 映射项（键-值对）  有几个方法：用上面的名字entry
    //entry.getKey() ;entry.getValue(); entry.setValue();
    //map.entrySet()  返回此映射中包含的映射关系的 Set视图。
    System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//如果只要value可以只迭代value
for (String v : map.values()) {
    System.out.println("value= " + v);
}
//java8forEach迭代
map.forEach((key, value) -> {         
        System.out.println(key + "：" + value);      
});