Set,List,Map

Set,List,Map是Java中提供的几种专门用于存储对象集合的数据结构,它们都是接口，有各自的实现类，它们都有一个共同的祖先（基类）Collection.

之所以在Java中不使用对象数组来存储对象，是因为对象数组有几个弊端：
1、数组一经建立，它的容量就已经确定了，容易出现数组下标越界异常，即使能扩容也会因为转移数据消耗大量机器的性能
2、对象数组若不进行初始化赋值，存储在其中的会是默认的NULL类型，很容易造成空指针异常。因为数组的length属性返回
的不是数组中所存的对象的数量，而是数组的容量。
3、数组进行插入删除操作要移动大量元素，时间复杂度较高。

1.List

List有三种实现类，ArrayList,LinkedList和Vector
List中文名叫做有序集合（也称序列）。它有几个特点：‘
1、可以精确访问和控制列表中每个位置的插入位置，和数组一样有随机读取的优点
2、序列中允许有重复的元素，。。。。。
3、可以存储多个null
4、有序：元素的插入顺序和按index从小到大遍历的顺序一致

1.1 基本操作：

插入： add(int index, Object element)
删除：remove(int Index) 清空：clear() //继承自Collection
按位序查找：get(int index)
按值查找：indexOf(Object o) lastIndexOf(Object o)
修改：set(int index, E element)
判空：isEmpty() //继承自Collection
子序列：subList(int fromIndex, int toIndex) //左闭右开
表长：size() //继承自Collection

1.2 遍历操作：

主要有四种主要的遍历方式：
1.使用迭代器Iterator(继承自Collection的方法）

       Iterator iter =  list.iterator();
       while(iter.hasNext()){
           Object obj = iter.next();
           System.out.println(obj);
       }
       
       for(  Iterator itr =  list.iterator();itr.hasNext();){
           Object obj = itr.next();//在使用迭代器迭代的时候  在一个循环中  next方法只能在一处调用
           System.out.println(obj);
       }

2.使用for循环和索引

       for(int i = 0 ; i < list.size();i++){
            Object obj = list.get(i);
           System.out.println(obj);
       }

3.使用foreach

       for(Object obj : list){
           System.out.println(obj);
       }

4.使用列表迭代器（本类的）

        // 获取列表迭代器
       ListIterator iterator =  list.listIterator();
       // 遍历同时天剑
        while(iterator.hasNext()){
            Object obj = iterator.next();
            // 当遇到元素为world的时候  给列表追加元素spring
            if(obj.equals("world")){
                iterator.add("spring");
                iterator.previous();//是的指针指向前一个元素
            }
            System.out.println(obj);
        }

若使用Iterator可能会出现并发修改异常：ConcurrentModificationException
原因是Iterator不能在遍历的同时修改原集合对象的元素

    public static void main(String[] args) {
        List list = new ArrayList();
        list.add("hello");
        list.add("world");
        list.add("java");
        Iterator iter =  list.iterator();
        while(iter.hasNext()){
            Object obj = iter.next();
            String str = (String) obj;
            if(str.equals("world")){
                list.add("hadoop");//这里会引起异常
            }
        }
    }

ListIterator可以在遍历的同时修改原集合对象

        ListIterator iterator2 =  list.listIterator();
        while(iterator2.hasNext()){
            Object obj = iterator2.next();
            if(obj.equals("hello")){
                iterator2.set("mybatis");
                iterator2.previous();

            }else{
                System.out.println(obj);
            }
        }

2.ArrayList和LinkedList和Vector

ArrayList的底层是一个动态数组，查询快，增删慢，每次扩容扩大为原先容量的1.5倍可以用索引随机访问List中任一元素
LinkedList底层采用双向链表实现，查询慢，增删慢，可以直接访问列表的开头和结尾，其它位置需要逐个遍历。添加元素采用
头插法和尾插法。
Vector相对前两者的优点是线程安全，但效率不高，底层也是可变数组，扩容是变为原始容量的两倍

3.Set集合

特点：

不包含重复元素的集合
最多只能有一个null值
没有索引，只能通过迭代器和增强for进行遍历
set集合是无序的（无序指的是set集合中的元素的添加顺序和迭代顺序不一致）

4.HashSet

特点：

底层的数据结构是哈希表
实现不同步
对集合的迭代顺序不做任何保证，也就是说保存的顺序和获取的顺序是不一致的
没有带索引的方法，只能使用增强for和迭代器进行遍历
不能包含重复元素
可以存储null 但是只能存一个
HashSet如何保证元素的唯一性
1.根据对象的哈希值计算存储位置：
如果当前位置没有元素则直接存入，如果有则进入第二步
2.当前元素和计算所得位置的所有元素进行哈希值的比较
如果哈希值不同，则直接存储
如果哈希值相同，则进入第三步
3.通过equals方法比较元素的内容
如果内容不同则直接进行存储，如果内容相同，则认为元素重复，不存储
简单来说，元素的重复性就是哈希值和equals结果相与

所以：对于存入hashSet集合中对象，都必须重写hashCode 和equals方法，以保证元素的唯一性

什么是哈希表
哈希表属于一种数据结构，jdk8以前哈希表采用数组和链表来实现，
jdk8以后哈希表采用数组，链表和红黑树来实现，当链表的长度超过一定值时，就会将链表转换成红黑树