一张图解决List&Map集合

单列体系

Collection 接口

    |-List 接口：存取有序（怎么存进去就怎么取出来），可以存储重复元素，有索引
        |-ArrayList 类：使用数组结构
        |-LinkedList 类：使用链表结构
    |-Set  接口：存取无序（不能保证怎么存进去就怎么取出来），不能存储重复元素，无索引
        |-HashSet 类
            |-LinkedHashSet 类

遍历方式
1、迭代器（Iterator） [适用于所有的单列集合] *
2、增强for [适用于所有的单列集合] *
3、普通for（size()和get(int index)） [只适用于List集合] *
4、列表迭代器（ListIterator） [只适用于List集合]
5、将集合转数组，遍历遍历数组toArray() [适用于所有的单列集合]

List集合

    List接口
        常用特有方法：和索引相关的方法
             void add(int index, E element)
             E get(int index)
             E remove(int index)
             E set(int index, E element)

ArrayList类
    List集合拥有的3个特点它都有，因为它是List的实现类
    底层使用的是数组结构：查询快，增删慢
LinkedList类
    List集合拥有的3个特点它都有，因为它是List的实现类
    底层使用的是链表结构：查询慢，增删快

List集合的选择：优先选择ArrayList、如果增删多，则选择LinkedList



E unlink(Node<E> x) {
        // assert x != null;
        // x代表world节点
        // x.item获取的是数据"world" = element
        final E element = x.item;
        // x.next = next 表示的都是java节点
        final Node<E> next = x.next;
        // x.prev = prev 表示的都是hello节点
        final Node<E> prev = x.prev;

        // 判断要删除的world是否是第一个元素
        if (prev == null) {
            // 将要删除的元素的下一个节点作为头节点
            first = next;
        } else {
            // 把hello节点的下一个节点记录为java节点
            prev.next = next;
            // 把world的上一个节点记录为null
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            // 将java节点的上一个节点记录为hello节点
            next.prev = prev;
            // 把world的下一个节点记录为null
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

Collections工具类

    排序
        static void shuffle(List<?> list)
        static void sort(List<T> list)：按照默认规则排序
        static void sort(List<T> list, Comparator<? super T> c)：按照指定规则排序

Set集合
存取无序（不能保证怎么存进去就怎么取出来），不能存储重复元素，无索引
HashSet类
HashSet类底层使用了哈希表=数组+链表/树
Set集合拥有的3个特点它都有，因为它是Set的实现类

    不能存储重复元素（保证元素唯一）原理
        在使用HashSet的add方法添加元素的时候，add方法底层依赖了两个方法：hashCode()和equals()方法
        首先会计算要存储元素的哈希值，和集合中的所有元素的哈希值一一进行比较，
            如果哈希值不同，则直接存储到集合中
            如果哈希值相同，则无法直接判断是否是相同元素，要进一步判断，通过equals方法
                如果equals的结果不同，则存储到集合中
                如果equals的结果相同，则不存储

    结论
        以后我们在使用HashSet存储元素的时候，如果该元素是JDK提供的类的对象，比如String、Integer，则存进去自动去重。
        如果存储的元素是我们自定义的类的对象，比如Student、Person类等，则要先在这些类中重写hashCode和equals方法
        然后存进去就可以做到去重了，如何重写？快捷生成


    哈希值
        是一个十进制的整数，根据hashCode()方法获取到

        哈希值相同的不一定是相同对象，哈希值不同的绝对是不同对象

LinkedHashSet 类
    它和其父类HashSet除了一点不同之外，其余全相同。
    不同点：它底层加了一条双向链表，保证了元素有序

TreeSet类
    了解，开发中基本不会去使用它，而且还比较难

Map

|-HashMap
    |-LinkedHashMap
|-TreeMap

Set的体系和Map的体系很相似，Set体系底层调用的就是Map体系
Set体系使用的是Map体系的键（key），Map体系的key的特点和Set一致

Map
Map是双列集合，第一列叫键（key），第二列叫值（value）
特点：
1、Map的键key不能重复的，值可以重复
如果键相同则值覆盖
2、Map的键和值（键值对）是一一对应的，通过键可以找到唯一的值，但是通过值不能找到唯一的键

Map的常用方法  【掌握】
    判断方法
     boolean containsKey(Object key)：判断Map中是否包含指定键的元素
     boolean containsValue(Object value)：判断Map中是否包含指定值的元素
     boolean isEmpty():判断Map中是否有元素

    增删改查的方法
     V put(K key, V value)：添加/修改
     V get(Object key)：查
     V remove(Object key)：删
     void clear()：删所有

    获取
     int size()：获取长度
     Collection<V> values()：获取Map中所有的值
     Set<K> keySet()：获取Map中所有的键
     Set<Map.Entry<K,V>> entrySet()：获取Map中所有的元素（键值对）

Map的遍历      【掌握】
    遍历方式一：根据键找值，keySet()和get(Object key)方法
    遍历方式二：根据键值对找键和值，entrySet()方法

HashMap
    最常用的Map集合，底层是哈希表结构=数组+链表/树
    Set体系使用的是Map体系的键（key），Map体系的key的特点和Set一致

LinkedHashMap
    LinkedHashMap与HashMap的关系，和LinkedHashSet与HashSet的关系一样

    LinkedHashMap除了一个特点之外，所有（方法、特点）都和父类HashMap一致
    不同的特点是：LinkedHashMap可以保证元素有序（怎么存进去怎么取出来）


TreeMap  【了解】
    排序，对于整数按照从大到小，或者从小到大顺序排，它排序针对的键

    构造方法：
        TreeMap()
                  使用键的自然顺序构造一个新的、空的树映射。
        TreeMap(Comparator<? super K> comparator)
                  构造一个新的、空的树映射，该映射根据给定比较器进行排序。

    使用比较器排序


    Collections.sort(List,Comparator)
    TreeSet
        TreeSet(Comparator)
    TreeMap
        TreeMap(Comparator)
    类似的用法