集合源码分析与List操作

同 : 三个类都实现了List 接口 存储数据的特点相同: 存储有序 可重复

不同 :  ArrayList 作为List的主要实现,线程不安全,效率高, 底层使用Object [] 存储
        LinkedList 对于频繁的使用插入, 删除操作效率比ArrayList效率高 底层使用双向链表存储

        Vector 线程安全 效率低 底层使用Object[] elementData存储\

        ArrayList list = new ArrayList(10);  // 底层创建了长度是10的Object[]数组 elementDate
        list.add(123);  ---> elementData[0] = new Integer(123);
        ...
        list.add();  // 如果此次的添加导致底层的elementData数组容量不够,则扩容,默认情况下扩容为原来的1.5倍
                        同时需要将原有数组中的数据复制到新的数组中

        建议开发中使用带参的构造器 :ArrayList list = new ArrayList(int capacity)


        ArrayList() jdk1.8 源码分析

        ArrayList list =  new ArrayList(10)  elementData 初始化为{}并没有创建底层为10 的数组
        list.add(123); 第一次调用add添加操作的时候才创建底层为10 的数组并添加数据

        扩容的机制和jdk7的相同

        小结: jdk7的ArrayList的对象创建相当于单例模式的饿汉式, jdk8的ArrayList的对象创建相当于单例模式的懒汉式

    LinkedList 源码分析
        LinkedList list = new LinkedList()内部声明了Node的类型first和last属性,默认值为null
        list.add(123)// 将123 封装到Node中 创建了Node对象  其中Node就是双向链表的体现

       /*
        ArraylList   方法

        增: add(Object obj)
        删: remove(int index) / remove(Object obj)
        改 : set(int index, Object obj)
        查: get(int index)
        插: add(int index, Object obj)
        长度: size()
        遍历: 1: Iterator 迭代器
              2: for循环
        */

List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来 操作集合元素的方法。
?void add(int index, Object ele):在index位置插入ele元素
?boolean addAll(int index, Collection eles):从index位置开始将eles中
的所有元素添加进来
?Object get(int index):获取指定index位置的元素
?int indexOf(Object obj):返回obj在集合中首次出现的位置
?int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置 
?Object remove(int index):移除指定index位置的元素，并返回此元素 
?Object set(int index, Object ele):设置指定index位置的元素为ele 
?List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex
位置的子集合

HashSet 是Set的主要实现类 线程不安全可以存储null值
    |---- LinkedHashSet 作为HashSet的子类遍历其内部数据结构时可以按照添加顺序遍历
TreeSet 可以按照添加对象的指定属性 进行排序


Set接口中没有添加新的方法 都是使用Collection中的方法

1: 无序性: 不等于随机性 存储的数据再底层中并非按照数组索引的顺序添加,而是根据数据的哈希值来的
2: 不可重复性 :保证添加的元素按照equals()判断时,不能反回true, 即相同的元素只能添加一个

添加元素的过程:


        我们向HashSet中添加元素a,首先调用元素a所在类的hashCode()方法,计算元素a的哈希值,此哈希值接着通过某种蒜放计算出
        在HashSet底层数组中存放的位置(即为: 索引位置),判断数组此位置上是否已经有其他元素
            如果位置上没有其他元素,则把元素a添加到此位置,元素a添加成功 ---->情况1
            如果此位置上有其他元素b(或以链表形式存在的多个元素),则比较元素a与元素b的哈希值
            如果hash值不同元素a添加成功 ---- > 情况2
            如果hash值相同,进而需要田勇元素a所在类的equals()方法:
            equals()返回true,元素a添加失败,
            equals()返回false,元素a添加成功 --- > 情况3


       对于添加成功的情况2 和3 而言,元素a与已经存在指定索引位置上的数据以链表的形式存储
       jdk7: 元素a放在的数组中,指向原来的元素
       jdk8: 原来的元素在数组中指向元素a