Collection子接口之一 List接口

|----Collection接口：单列集合，用来存储一个一个的对象
  |----List接口：存储有序的、可重复的数据。 -->“动态”数组
    |----ArrayList
    |----LinkedList
    |----Vector

★★★★★ArrayList，LinkedList，Vector三者的异同？

同：三个类都是实现了List接口，存储数据的特点相同：存储有序的、可重复的数据
不同点：
ArrayList ： 作为List接口的主要实现类；线程不安全的，效率高；底层使用Object[] elementData存储 扩容1.5倍 jdk1.2
LinkedList： 对于频繁的插入，删除操作，使用此类效率比ArrayList高；底层结构使用的双向链表存储 jdk1.2
Vector ： 作为List接口的古老实现类；线程安全的，效率低； 底层使用Object[] elementData存储 扩容2.0倍 jdk1.0

1.ArrayList底层源码分析：

（一）jdk7情况下ArrayList源码

1. 底层是Object[] elementData 存储
2. ArrayList arrayList = new ArrayList();底层创建了长度为10的Object[]数组 elementData
3. 默认情况扩容为原来的1.5倍，扩容后将原来的数据拷贝到新的数组中

• 结论：建议开发中使用带参的构造器：ArrayList arrayList = new ArrayList(int capacity); //减少反复扩容浪费的时间，提高效率

（二）jdk8中ArrayList的源码变化

1. ArrayList list = new ArrayList();底层Object[] elementData初始化为{}。并没有创建长度为10数组

2. list .add(12);//第一次调用add()时，底层才创建了长度为10的数组，并将数据12添加到elementData[0]
3. 后序添加和扩容与jdk7相同

• 总结：jdk7中的ArrayList的对象的创建类似于单例模式的饿汉式，而jdk8中的ArrayList的对象的创建类似于单例模式的懒汉式，延迟了数组的创建，节省内存。

StringBuffer底层源码
StringBuffer stringBuffer = new StringBuffer();底层创建了长度为16的char[]类型的数组value

2.LinkedList底层源码分析：

底层是双向链表，频繁的插入，删除操作比较快

1. LinkedList list = new LinkedList();内部声明了Node类型的first和last属性，默认值为null
2. list.add(12);//将12封装到Node中，创建了Node对象。
3. 其中，Node定义为：体现了LinkedList的双向链表的说法

    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

3.Vector底层源码分析：

Vector ： 作为List接口的古老实现类；线程安全的，效率低； 底层使用Object[] elementData存储 jdk1.0

1. jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。
2. 在扩容方面，默认扩容为原来的数组长度的2倍
3. 在实际开发中Vector是线程安全的，很少用。

解决ArrayList的线程安全问题

Collections中的synchronizedList(List<> list);
ArrayList arrayList = new ArrayList();
List list = Collections.synchronizedList(arrayList);

集合List接口中常用方法

1. void add(int index, Object ele):在index位置插入ele元素
2. boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
3. Object get(int index):获取指定index位置的元素
4. int indexOf(Object obj):返回obj在集合中首次出现的位置
5. int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置
6. Object remove(int index):移除指定index位置的元素，并返回此元素
7. Object set(int index, Object ele):设置指定index位置的元素为ele
8. List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的子集合

总结：常用方法

• 增：add(Object obj)
• 删：remove(int index) / remove(Object obj)
• 改：set(int index, Object ele)
• 查：get(int index)
• 插：add(int index, Object ele)
• 长度：size()
• 遍历：① Iterator迭代器方式
  ② 增强for循环
  ③ 普通的循环

    public void test01(){
        ArrayList list = new ArrayList(); //有序可重复
        list.add(123);
        list.add(456);
        list.add("AAA");
        list.add(new Person("Tom",18));
        list.add(456);
        System.out.println(list);  //[123, 456, AAA, Person{name='Tom', age=18}, 456]

        //1.void add(int index, Object ele):在index位置插入ele元素
        list.add(1,"BB");
        System.out.println(list); //[123, BB, 456, AAA, Person{name='Tom', age=18}, 456]

        //2.boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
        List list1 = Arrays.asList(1,2,3);
        list.addAll(list1);
        System.out.println(list);//[123, BB, 456, AAA, Person{name='Tom', age=18}, 456, 1, 2, 3]

        //3.Object get(int index):获取指定index位置的元素
        System.out.println(list.get(2)); //456

        //4.int indexOf(Object obj):返回obj在集合中首次出现的位置。如果不存在，返回-1.
        int index = list.indexOf(4567);
        System.out.println(index); //不存在返回-1

        //5.int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置。如果不存在，返回-1.
        System.out.println(list.lastIndexOf(456));  //5

        //6.Object remove(int index):移除指定index位置的元素，并返回此元素
        Object obj = list.remove(0);
        System.out.println(obj);  //123
        System.out.println(list); //[BB, 456, AAA, Person{name='Tom', age=18}, 456, 1, 2, 3]

        //7.Object set(int index, Object ele):设置指定index位置的元素为ele
        list.set(1,"CC");
        System.out.println(list);  //[BB, CC, AAA, Person{name='Tom', age=18}, 456, 1, 2, 3]

        //8.List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex位置的左闭右开区间的子集合
        List subList = list.subList(2, 4);  //左闭右开
        System.out.println(subList); //[AAA, Person{name='Tom', age=18}]
        System.out.println(list); //[BB, CC, AAA, Person{name='Tom', age=18}, 456, 1, 2, 3] （对原本的数据没有影响）
    }

遍历：Iterator/foreach/for

① Iterator迭代器方式
② 增强for循环
③ 普通的循环

    public void test3() {
        ArrayList list = new ArrayList();
        list.add(123);
        list.add(456);
        list.add("AA");

        //方式一：Iterator迭代器方式
        Iterator iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        System.out.println("***************");

        //方式二：增强for循环
        for (Object obj : list) {
            System.out.println(obj);
        }

        System.out.println("***************");

        //方式三：普通for循环
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
    }

区分List中的remove(int index) 和 remove(Object obj)

    public void testListRemove() {
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        updateList(list);
        System.out.println(list);//[1, 3]
    }

    private void updateList(List list) {
        //list.remove(2); // index 2是下标
        list.remove(new Integer(2));  //value 2 是元素
    }

Collection子接口之二 Set接口

Set接口的框架：

|----Collection接口：单列集合，用来存储一个一个的对象
  |----Set接口：存储无序的、不可重复的数据 -->高中讲的“集合”
    |----HashSet：作为Set接口的主要实现类；线程不安全；可以存储null值
      |----LinkedHashSet：作为HashSet的子类；遍历其内部数据时，可以按照添加的顺序遍历； 对于频繁的遍历操作，LinkedHashSet效率高于HashSet.
    |----TreeSet：可以按照添加对象的指定属性，进行排序

1. Set接口中没有额外定义新的方法，使用的都是Collection中声明过的方法。

2. 要求： 向Set(主要指：HashSet、LinkedHashSet)中添加的数据，其所在的类一定要重写hashCode()和equals()
   要求： 重写的hashCode()和equals()尽可能保持一致性：相等的对象必须具有相等的散列码
   重写两个方法的小技巧：对象中用作 equals() 方法比较的 Field，都应该用来计算 hashCode 值。

一，Set: 存储无序的，不可重复的数据 （以HashSet为例说明：）

1. 无序性：不等于随机性（是添加的顺序和读取的顺序不一致）。存储的数据在底层数组中并非按照数组索引的顺序添加，而是根据数据的哈希值决定的。

2. 不可重复性：保证添加的元素按照equals()判断时，不能返回true.即：相同的元素只能添加一个。

二、添加元素的过程：以HashSet为例：

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

对于添加成功的情况2和情况3而言：元素a 与已经存在指定索引位置上数据以链表的方式存储。

jdk 7 :元素a放到数组中，指向原来的元素。
  jdk 8 :原来的元素在数组中，指向元素a
总结：七上八下

HashSet底层：数组+链表的结构。

Set实现类之一：HashSet

Set实现类之二：LinkedHashSet

在原有的HashSet的基础上添加了一个双向链表，来记录添加的先后顺序

LinkedHashSet作为HashSet的子类，在添加数据的同时，每个数据还维护了两个引用，记录此数据前一个数据和后一个数据。
优点： 对于频繁的遍历操作，LinkedHashSet效率高于HashSet

   public void test02(){
        Set set = new LinkedHashSet();
        set.add(456);
        set.add(123);
        set.add(123);
        set.add("AA");
        set.add("CC");
        set.add(new Person("Tom",12));
        set.add(new Person("Tom",12));
        set.add(129);

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

输出结果：

456
123
AA
CC
Person{name=‘Tom’, age=12}
129

Set实现类之三：TreeSet

1. 向TreeSet中添加的数据，要求是相同类的对象
2. 两种排序方式：自然排序(实现Comparable接口) 和 定制排序（Comparator）
3. 自然排序中，比较两个对象是否相同的标准为：compareTo()返回0，不再是equals()方法
4. 定制排序中，比较两个对象是否相同的标准为：compare()返回0，不再是equals()
5. 不可重复，，，，排序从小到大

自然排序 （实现Comparable接口）

public class Person implements Comparable {
    String name;
    int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Person person = (Person) o;

        if (age != person.age) return false;
        return name != null ? name.equals(person.name) : person.name == null;
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result + age;
        return result;
    }


    //按照姓名从大到小排序,年龄从小到大
    @Override
    public int compareTo(Object o) {
        if (o instanceof Person) {
            Person person = (Person) o;
            //return this.name.compareTo(person.name);
            int compare = this.name.compareTo(person.name);
            if (compare != 0) {
                return compare;
            } else {
                return Integer.compare(this.age, person.age);
            }
        } else {
            throw new RuntimeException("输入类型不匹配");
        }
    }
}

    public void test03(){
        //自然排序
        TreeSet treeSet = new TreeSet();
        treeSet.add(new Person("Tom",18));
        treeSet.add(new Person("Good",23));
        treeSet.add(new Person("Jerry",20));
        treeSet.add(new Person("Jack",14));
        treeSet.add(new Person("Jack",56));

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

    }

结果输出：

Person{name=‘Good’, age=23}
Person{name=‘Jack’, age=14}
Person{name=‘Jack’, age=56}
Person{name=‘Jerry’, age=20}
Person{name=‘Tom’, age=18}

**定制排序Comparator **

    public void test04(){
        //定制排序
        Comparator com = new Comparator(){
            //按照年龄的从小到大排序
            @Override
            public int compare(Object o1, Object o2) {
                if (o1 instanceof Person && o2 instanceof Person){
                    Person p1 = (Person) o1;
                    Person p2 = (Person) o2;
                    return Integer.compare(p1.getAge(),p2.getAge());
                }else {
                    throw new RuntimeException("数据类型不匹配");
                }
            }
        };

        TreeSet treeSet = new TreeSet(com); //采用定制排序
        treeSet.add(new Person("Tom",18));
        treeSet.add(new Person("Good",23));
        treeSet.add(new Person("Jerry",20));
        treeSet.add(new Person("Mary",20));//年龄为20的已存在，不可重复
        treeSet.add(new Person("Jack",14));
        treeSet.add(new Person("Jack",56));


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

结果输出：

Person{name=‘Jack’, age=14}
Person{name=‘Tom’, age=18}
Person{name=‘Jerry’, age=20}
Person{name=‘Good’, age=23}
Person{name=‘Jack’, age=56}

1.集合Collection 中存储的如果是自定义类的对象，需要自定义类重 写哪个方法?为什么?

equals()方法
List：equals()方法
Set：(HashSet，LinkedHashSet为例) : equals(), hashCode()
    (TreeSet为例)：Comparable： compareTo(Object obj)
           Compaeator: compare(Object o1,Object o2)

2.List接口的常用方法有哪些？（增删改查，插入，长度，遍历）

add(Object obj)
remove(Object obj)/remove(int index)
set(int index,Object obj)
get(int index)
add(int index,Object obj)
size() //元素的个数

使用迭代器Iterator；foreach；普通的for

3.Set存储数据的特点是什么？常见的实现类有什么？说明一下彼此的特点

无序性和不可重复性
HashSet， LikedHashSet，TreeSet
底层分别对应：HashMap，LikedHashMap，TreeMap

4.使用Collection集合存储对象，要求对象所属的类满足

向Collection接口的实现类的对象中添加数据obj时，要求obj所在类要重写equals()

5.Collection集合与数组间的转换

 //集合---->数组：toArray()
        Object[] arr = coll.toArray();
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
//扩展：数组---->集合:调用Arrays类的静态方法aslist()
        List<String> list = Arrays.asList(new String[]{"AA", "BB", "CC"});
        System.out.println(list);  //[AA, BB, CC]

        List arr1 = Arrays.asList(1,2,3,4,5);
        System.out.println(arr1); //[1, 2, 3, 4, 5]

        List arr2 = Arrays.asList(new Integer[]{1,2,3,4,5});
        System.out.println(arr2); //[1, 2, 3, 4, 5]

List：
1.可以允许重复的对象。
2.可以插入多个null元素。
3.是一个有序容器，保持了每个元素的插入顺序，输出的顺序就是插入的顺序。
4.常用的实现类有 ArrayList、LinkedList 和 Vector。ArrayList 最为流行，它提供了使用索引的随意访问，而 LinkedList 则对于经常需要从 List 中添加或删除元素的场合更为合适。

Set：
1.不允许重复对象
2.无序容器，你无法保证每个元素的存储顺序，TreeSet通过 Comparator 或者 Comparable 维护了一个排序顺序。
3.只允许一个 null 元素
4.Set 接口最流行的几个实现类是 HashSet、LinkedHashSet 以及 TreeSet。

List, Set,是否继承自Collection接口，Map不是。

Map：
1.Map不是collection的子接口或者实现类。Map是一个接口。
2.Map 的 每个 Entry 都持有两个对象，也就是一个键一个值（键值对），Map 可能会持有相同的值对象但键对象必须是唯一的。
3. TreeMap 也通过 Comparator 或者 Comparable 维护了一个排序顺序。
4. Map 里你可以拥有随意个 null 值但最多只能有一个 null 键。
5.Map 接口最流行的几个实现类是 HashMap、LinkedHashMap、Hashtable 和 TreeMap。（HashMap、TreeMap最常用）

参考代码： ListSetMapTest

/**
 * List和Set,map有什么区别 
 */
public class ListSetMapTest {
	public static void main(String[] args) {
		List<String> list = new ArrayList<String>();
		list.add("A");
		list.add("B");
		list.add("C");
		list.add("D");
		list.add("D");
		list.add(null);
		list.add(null);
		System.out.println("list:" + list);
		
	    Set<String> set = new HashSet<String>();
	    set.add("A");
	    set.add("B");
	    set.add("C");
	    set.add("D");
	    set.add("D");
	    set.add(null);
	    set.add(null);
	    System.out.println("set:" + set);
	    
	    Map<String, String> map  = new  HashMap<String,String>();
	    map.put("A", "A");
	    map.put("B", "B");
	    map.put("C", "C");
	    map.put("D", "D");
	    map.put(null, null);
	    map.put(null, null);
	    map.put("E", null);
	    System.out.println("map:" + map);
	    
	}
}

List 和 Set 的区别

List , Set 都是继承自Collection 接口

List 特点：一个有序（元素存入集合的顺序和取出的顺序一致）容器，元素可以重复，可以插入多个null元素，元素都有索引。常用的实现类有 ArrayList、LinkedList 和 Vector。

Set 特点：一个无序（存入和取出顺序有可能不一致）容器，不可以存储重复元素，只允许存入一个null元素，必须保证元素唯一性。Set 接口常用实现类是 HashSet、LinkedHashSet 以及 TreeSet。

另外 List 支持for循环，也就是通过下标来遍历，也可以用迭代器，但是set只能用迭代，因为他无序，无法用下标来取得想要的值。

Set和List对比

Set：检索元素效率低下，删除和插入效率高，插入和删除不会引起元素位置改变。

List：和数组类似，List可以动态增长，查找元素效率高，插入删除元素效率低，因为会引起其他元素位置改变