Collection&Map继承树

一、Collection接口

Collection 是最基本的集合接口，一个 Collection 代表一组 Object，即 Collection 的元素（Elements）。一些 Collection 允许相同的元素、支持对元素进行排序，另一些则不行。JDK 不提供直接继承自 Collection 的类，JDK 提供的类都是继承自 Collection 的子接口，如 List 和 Set。所有实现 Collection 接口的类都必须提供两个标准的构造函数，无参数的构造函数用于创建一个空的 Collection，有一个 Collection 参数的构造函数用于创建一个新的 Collection，这个新的 Collection 与传入的 Collection 有相同的元素，后一个构造函数允许用户复制一个 Collection。

Collection接口继承树

Iterator it = collection.iterator(); // 获得一个迭代子
while(it.hasNext()){
   Object obj = it.next(); // 得到下一个元素 
}

（一）List 接口

List 是有序的 Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在 List 中的位置，类似于数组下标）来访问 List 中的元素，这类似于 Java 的数组。和下文要提到的 Set 不同，List 允许有相同的元素。
除了具有 Collection 接口必备的 iterator() 方法外，List 还提供一个 listIterator() 方法，返回一个 ListIterator 接口。和标准的 Iterator 接口相比，ListIterator 多了一些 add() 之类的方法，允许添加、删除、设定元素、向前或向后遍历等功能。实现 List 接口的常用类有 LinkedList，ArrayList，Vector 和 Stack 等。
List 接口提供的主要方法：
• void add(int index,Object element) 在指定位置上添加一个对象；
• boolean addAll(int index,Collection c) 将集合 C 的元素添加到指定的位置；
• Object get(int index) 返回 List 中指定位置的元素；
• int indexOf(Object o) 返回第一个出现元素 O 的位置；
• Object removeint(int index) 删除指定位置的元素；
• Object set(int index,Object element) 用元素 element 取代位置 index 上的元素, 返回被取代的元素。

1.ArrayList 类

ArrayList就是动态数组，它提供了动态的增加和减少元素，实现了ICollection和IList接口，灵活的设置数组的大小等好处。它允许所有元素，包括 Null。Size、IsEmpty、Get、Set 等方法的运行时间为常数，但是 Add 方法开销为分摊的常数，添加 N 个元素需要 O(N) 的时间，其他的方法运行时间为线性。
每个 ArrayList 实例都有一个容量（Capacity），用于存储元素的数组的大小，这个容量可随着不断添加新元素而自动增加。当需要插入大量元素时，在插入前可以调用 ensureCapacity 方法来增加 ArrayList 的容量以提高插入效率。和 LinkedList 一样，ArrayList 也是线程非同步的（unsynchronized）。
ArrayList 提供的主要方法：
• Boolean add(Object o) 将指定元素添加到列表的末尾；
• Boolean add(int index,Object element) 在列表中指定位置加入指定元素；
• Boolean addAll(Collection c) 将指定集合添加到列表末尾；
• Boolean addAll(int index,Collection c) 在列表中指定位置加入指定集合；
• Boolean clear() 删除列表中所有元素；
• Boolean clone() 返回该列表实例的一个拷贝；
• Boolean contains(Object o) 判断列表中是否包含元素；
• Boolean ensureCapacity(int m) 增加列表的容量，如果必须，该列表能够容纳 m 个元素；
• Object get(int index) 返回列表中指定位置的元素；
• Int indexOf(Object elem) 在列表中查找指定元素的下标；
• Int size() 返回当前列表的元素个数。

2.LinkedList类：

• LinkedList 是一个继承于AbstractSequentialList的双向链表。
• LinkedList 可以被当作堆栈、队列或双端队列进行操作。
• LinkedList 实现 List 接口，所以能对它进行队列操作。
• LinkedList 实现 Deque 接口，能将LinkedList当作双端队列使用。
• LinkedList 实现了Cloneable接口，即覆盖了函数clone()，能克隆。
• LinkedList 实现java.io.Serializable接口，所以LinkedList支持序列化，能通过序列化去传输。
• LinkedList 是非同步的。
LinkedList的本质是双向链表：
LinkedList继承于AbstractSequentialList，并且实现了Dequeue接口。
LinkedList包含两个重要的成员：header 和 size。

1. header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量： previous, next, element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
2. size是双向链表中节点的个数。

LinkedList 实现了 List 接口，允许 Null 元素。此外 LinkedList 提供额外的 Get、Remove、Insert 等方法在 LinkedList 的首部或尾部操作数据。这些操作使得 LinkedList 可被用作堆栈（Stack）、队列（Queue）或双向队列（Deque）。请注意 LinkedList 没有同步方法，它不是线程同步的，即如果多个线程同时访问一个 List，则必须自己实现访问同步。一种解决方法是在创建 List 时构造一个同步的 List，方法如 ：

List使用场景

涉及到“栈”、“队列”、“链表”等操作，应该考虑用List，具体的选择哪个List，根据下面的标准来取舍:
ArrayList在随机访问方面比较擅长，LinkedList在随机增删方面比较擅长
对于需要快速插入，删除元素，使用LinkedList。因为ArrayList要想在数组中任意两个元素中间添加对象时，数组需要移动所有后面的对象。
对于需要快速随机访问元素（get()），应该使用ArrayList，因为LinkedList要移动指针、遍历节点来定位，所以速度慢。
对于“单线程环境” 或者 “多线程环境，但List仅仅只会被单个线程操作”，此时应该使用非同步的类(如ArrayList)。
对于“多线程环境，且List可能同时被多个线程操作”，此时，应该使用同步的类(如Vector)。
什么时候使用Arraylist，什么时候使用LinkedList？
当你需要频繁查询数组的时候使用ArrayList比较快，当你需要频繁操作数组进行增删插入操作的时候使用LinkList比较合适。当然直接在末尾添加数据ArrayList用时也不是特别多，因为在末尾操作后面没有数据。

（二）Set接口:

set中不包含重复元素，有m，n，则m.equals(n)=false,可以有null元素，最多一个。
• 因为Set和List都是继承自Collection接口，所以Set和List中很多方法都是一样的。
• List接口中有add，set，indexOf方法，但Set中只有add方法，没有set，indexOf方法，因为Set是无序不可重复的，不存在某元素具体位置这个概念

HashSet类

HashSet低层是基于HashMap实现的set，用HashMap保存数据，和HashMap一样的性能，消耗较多内存。
• hashCode和equal()是HashMap用的，因为无需排序所以只需要关注定位和唯一性即可。
• hashCode是用来计算hash值的，hash值是用来确定hash表索引的。
• hash表中的一个索引存放的是一张链表，所以还要通过equal方法循环比较链上的每一个对象才可以真正定位到键值对应的Entry。
• put时，如果hash表中没定位到，就在链表前加一个Entry，如果定位到了，则更换Entry中的value(值)并返回旧value(值)
• （关于HashMap）覆写key的hashCode()和equal()时不要关联可变属性，否则属性变了hashCode会变，equal也会为false，这样在Map中就找不到它了，而且这样的对象因为找不到它，所以得不到释放，这样就变成了一个无效引用。(相当于内存泄漏)
HashSet如何确定两个对象是否相等？
① 先判断对象的hashCode( )，如果hashCode不同，那肯定不是一个对象。 如果hashCode相同，那继续判断equals( )方法；
② 重写equals( )方法。
如何使用HashSet储存元素：

HashSet储存数据

TreeSet类

与 HashSet 是基于 HashMap 实现一样，TreeSet 同样是基于 TreeMap 实现的。
TreeSet可以确保集合元素处于排序状态（元素是有序的），因此支持add、remove、get等方法。
自然排序(元素具备比较性)
• 让元素所属的类实现Comparable接口
• 在类中重写Comparable的抽象方法compareTo()
比较器排序(集合具备比较性)
• 让集合构造方法接收Comparator的实现类对象
• 在比较器中重写Comparator的抽象方法compare
实质上，compareTo方法和compare方法内实体几乎相同

public class MyClass {
    public static void main(String[] args){

        TreeSet<Person> score = new TreeSet<>();

        Person p1 = new Person("jack",20);
        Person p2 = new Person("jack",30);
        Person p3 = new Person("rose",20);

        score.add(p1);
        score.add(p2);
        score.add(p3);

        //equals 比较的是对象内部的内容
        //使用的两个对象必须实现Comparable接口的compareTo方法
        //在compareTo里面实现具体该如何比较
        System.out.println(p1==p2);
    }
}

class Person implements Comparable{
    String name;
    int age;

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

    @Override
    public String toString() {
        return "Person{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
     }
    @Override
    public int compareTo(Object o) {
        //1. 判断o对象是不是peron的一个对象
        if (o instanceof Person){
            Person o1 = (Person)o;
            //自己规定比较的策略
            if (this.age != o1.age){
                return this.age - o1.age;
            }else{
                //年龄相同的情况下 再比姓名的字母
                return this.name.compareTo(o1.name);
            }
        }else{
            return -1;
        }
    }
}

二、Map接口

Map 没有继承 Collection 接口。Map 提供 Key 到 Value 的映射，一个 Map 中不能包含相同的 Key，每个 Key 只能映射一个 Value。Map 接口提供 3 种集合的视图，Map 的内容可以被当作一组 Key 集合，一组 Value 集合，或者一组 Key-Value 映射。

Map接口继承树

        HashMap<String,Integer> score = new HashMap<>();

        //添加对象：键值对
        score.put("Chinese",89);
        score.put("Math",94);
        score.put("English",92);

        //更改某个键对应的值
        score.put("Chinese",91);

        //获取键值对的个数
        score.size();

        //获取所有的key
        System.out.println(score.keySet());

        //获取所有的value
        System.out.println(score.values());

        //获取Entry:key-value
        System.out.println(score.entrySet());

        //获取一个键key对应的值
        System.out.println(score.get("English"));

        //键值对的遍历
        //1.通过遍历key来得到每一个key对应的值
        for (String key: score.keySet()){
            //通过key得到值
            int s = score.get(key);
            System.out.println("key:"+key+" value:"+s);
        }
        System.out.println("-------------");
        //2.通过EntrySet 得到Entry对象的集合
        //  一个Entry管理一个键值对 getKey getValue
        Set<Map.Entry<String, Integer>> entrys = score.entrySet();
        for (Map.Entry entry: entrys){
            //得到Entry对应的key
            String key = (String)entry.getKey();

            //获取Entry对应的值
            Integer value = (Integer)entry.getValue();

            System.out.println("key:"+key+" value:"+value);
        } 

（一）TreeMap实现类

Map接口派生了一个SortedMap子接口，TreeMap为其实现类。类似TreeSet排序，TreeMap也是基于红黑树对TreeMap中所有key进行排序，从而保证TreeMap中所有key-value对处于有序状态。TreeMap两种排序方法：
自然排序：TreeMap的所有key必须实现Comparable接口，而且所有key应该是同一个类的对象，否则将会抛出ClassCastExcepiton异常。
定制排序：创建TreeMap时，传入一个Comparator对象，该对象负责对TreeＭap中所有key进行排序。采用定制排序时不要求Map的key实现Comparable接口。
TreeMap中判断两个key相等的标准也是两个key通过equals比较返回true，而通过compareTo方法返回0，TreeMap即认为这两个key是相等的。
如果使用自定义的类作为TreeMap的key，应重新该类的equals方法和compareTo方法时应有一致的返回结果：即两个key通过equals方法比较返回true时，它们通过compareTo方法比较应该返回0。如果equals方法与compareTo方法的返回结果不一致，要么该TreeMap与Map接口的规则有出入（当equals比较返回true,但CompareTo比较不返回0时），要么TreeMap处理起来性能有所下降（当compareTo比较返回0，当equals比较不返回true时）。
TreeMap中提供了系列根据key顺序来访问Map中key-value对方法：

TreeMap的一些方法

（二）HashMape类

HashMap 是基于哈希表的 Map 接口的非同步实现。此实现提供所有可选的映射操作， 并允许使用 null 值和 null 键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。
常用方法：
put()：向HashMap中添加元素 key - value，key不允许重复，否则覆盖。

public class Map {
    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();//尖括号内容是泛型
        map.put("A", 149);
        map.put("B", 26);
        map.put("C", 39);
    }
}

get()：获取key所对应的value

public class Map {

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();//尖括号内容是泛型
        map.put("A", 149);
        map.put("B", 26);
        map.put("C", 39);
    }
}

size()：获取HashMap集合容器中有多少键值对

public class Map {

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();//尖括号内容是泛型
        map.put("A", 149);
        map.put("B", 26);
        map.put("C", 39);
    }
}

clear()：清空容器键值对，isEmpty()：空返回true

public class Map {

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();//尖括号内容是泛型
        map.put("A", 149);
        map.put("B", 26);
        map.put("C", 39);
    }
}

remove()：删除HashMap元素，返回value

public class Map {

    public static void main(String[] args) {
        HashMap<String,Integer> map = new HashMap<String,Integer>();//尖括号内容是泛型
        map.put("A", 149);
        map.put("B", 26);
        map.put("C", 39);
    }
}

addEntry方法
addEntry方法是将新增的key-value键值对存入到map中。该方法主要完成两个功能：

1. 添加新元素前， 判断是否需要对map的数组进行扩容，如果需要扩容，则扩容空间大小是多少?
2. 对于新增key-value键值对，如果key的hash值相同，则构造单向列表。

存储结构：
hashmap底层是以数组方式进行存储。将key-value对作为数组中的一个元素进行存储。
key-value都是Map.Entry中的属性。Entry是hashMap中封装key-value键值对的。其中将key的值进行hash之后进行存储，即每一个key都是计算hash值，然后再存储。每一个Hash值对应一个数组下标，数组下标是根据hash值和数组长度计算得来。
由于不能的key有可能hash值相同，即该位置的数组中的元素出现两个，对于这种情况，hashmap采用链表形式进行存储。