集合体系

    • Collection（单列）
      • List：ArrrayList, LinkedList, Vector
      • Set：HashSet, LinkedHashSet, TreeSet
    • Map（双列）
      • HashMap, Hashtable, LinkedHashMap, TreeMap, Properties

    总结：

    • ArrayList的实现底层是一个数组；当有需要扩容的时候，调用Array.copyOf()方法来创建更长的数组和复制数组中的内容
    • LinkedList实现的基础是内部类Node，Node的成员属性定义了item指向List中的元素，而成员属性next和prev则指向了链表的下一个和上一个元素；LinkedList中还有成员属性first和last指向链表中的第一个和最后一个元素
    • HashSet实现的底层是HashMap；HashMap的原理是数组和（单向）链表，HashMap内部定义了一个Node数组来放载元素，其实现的基础内部类Node继承了Map.Entry，除了成员属性key和value，Node还定义了hash来存储元素的hash值，和Node next用于指向链表的下一个元素
    • LinkedHashSet实现的底层是LinkedHashMap；LinkedHashMap继承了HashMap，实现的原理跟HashMap大同小异，不过与HashMap的区别在于，数组内使用的是LinkedHashMap.Entry来记录数据；LinkedHashMap.Entry继承了HashMap.Node，不过除了HashMap.Node原有的成员属性，LinkedHashMap.Entry多增了before和after来指向双向链表的上一个和下一个；同时LinkedHashMap中还重新了newNode方法，每次向Map中新增元素的时候都会通过newNode来更新链表的last，以及末尾元素的prev和next
    • TreeSet实现的底层是TreeMap，TreeMap中使用TreeMap.Entry来放载数据，除了key和value，Entry还定义了left和right指向了元素左边和右边的元素；添加元素的时候，会使用comparator的compare()方法或者元素本身的compareTo()来决定元素的顺序；除此之外，TreeMap中还定义了root成员变量来指向所有元素的根，root会随着新元素的加入而改变

    实战中集合选择原则

    • 根据存储的数据类型：单列 / 双列
      • 单列：存储的数据是否允许重复？平时的操作是增删多一点还是改查多一点？对存储数据的排序是否有要求？如果有，是要求元素按一定的规则排序？还是要求插入和取出的顺序一致？
      • 双列：对键的排序是否有要求？如果有，是要求键按一定的规则排序？还是要求插入和取出的顺序一致？如果是用于读取文件中的键值对 -> Properties 常用方法

    Collections工具类中的一些常用方法（均为静态方法）

    • 虽然工具类的名字叫做Collections，不过还是有些工具方法是针对Map类对象定义的
    • reverse( List ) - 反转List中元素的顺序
    • shuffle( List ) - 对List集合中的元素进行随机排序
    • sort( List ) - 根据元素的自然顺序对指定List集合中的元素进行排序
    • sort( List, Comparator ) - 根据指定的Comparator对List集合中的元素进行排序
      • 其底层还是如果有Comparator的话就会根据重写的compare()来进行比较，不然的话就是元素本身的compareTo()来比较
    • swap( List, int, int ) - 将List集合中的指定位置的两个元素进行交换
    • copy( List dest, List src ) - 将src集合中的元素拷贝至dest集合中；不过在拷贝之前会先对两者的size进行比较，如果dest的size小于src的size，那么就会抛出异常IndexOutOfBoundsException
      • 注意是比较size，而不是比较elementData的capacity

    Note

    • ArrayList每次扩容的倍数是1.5，HashMap是2倍，而TreeMap则是扩容到2倍加1

    Collection接口和常用方法：

    • add() 添加指定元素；remove() 删除指定元素；contains() 查找元素是否存在；size() 获取元素个数；isEmpty() 判断是否为空；clear() 清空；addAll() 添加多个元素；containsAll() 查找多个元素是否都存在；removeAll() 删除多个元素
    • iterator()
      • next()；hasNext()；remove()
      • 当iterator迭代器指向最后一个元素时，再次调用next()将会抛出NoSuchElement的异常；可以通过重新赋值iterator的方法来重置指针
      • 增强for的底层也还是迭代器

    List接口和常用方法

    • List接口
      • List集合类中的元素有序，添加和取出的顺序一致，而且可以重复
      • List集合中的每个元素都有其对应的顺序索引
    • List接口的常用方法
      • add(int index, Object ele) 在index位置插入元素ele；addAll(int index, Collection eles) 在index位置插入集合eles；get() 获取指定位置的元素；indexOf() 返回某个元素在集合中第一次出现的位置；lastIndexOf() 返回某个元素在集合中最后一次出现的位置；remove() 移除指定index位置的元素，并返回该元素；set(int index, Object ele) 设置指定index位置的元素为ele，相当于是替换；subList(int fromIndex, int toIndex) 返回从fromIndex到toIndex位置的子集合
      • 因为List是有序的，所以add()&addAll()方法可以指定插入的位置，而不像Collection中的那样只能在末位 插入；而且可以按照参数index来查找或者移除特定位置上的元素

    ArrayList底层结构和源码分析

    • ArrayList底层实现其实是一个Object类型的数组elementData；当创建ArrayList对象时，如果调用的是无参构造器，那么默认的数组长度为0，之后第一次添加元素会扩容到10，之后的再次扩容则为之前容量的1.5倍；也可以调用有指定初始数组大小的构造器，不过同样之后的扩容为1.5倍

    ArrayList中add() 方法调用的过程

    • add() ->
    • ensureCapacityInternal( size + 1 ) ->
      • 确定 minCapacity -> 根据elementData是否 == DEFAULTTCAPACITY_EMPTY_ELEMENTDATA
      • (如果ArrayList一开始创建时调用的是无参构造，那么就会将DEFAULTTCAPACITY_EMPTY_ELEMENTDATA赋值给elementData)
    • ensureExplicitCapacity( minCapacity )
      • modCount ++ (记录ArrayList被修改次数？)
      • 判断 minCapacity - elementData.length > 0
    • 如果当前elementData容量不够 grow( minCapacity )，如果容量够用就不会调用 grow
      • 先根据当前elementData长度计算正常扩容后的容量大小（1.5倍）
      • 判断新的容量大小是否能满足 minCapacity（minCapacity = size + 1 或者 10, DEFAULT_CAPACITY）
      • 所以新的容量要么为原来容量的1.5倍要么为10
      • 根据新容量调用 elementData = Arrays.copyOf( elementData, newCapacity )
    • 确保了elementData有足够空间之后（要么原有空间不够，则会调用grow( minCapacity )进行扩容；要么原来空间足够，则会不进行任何操作，不过还是会modCount），就将要添加的元素加到elementData中：elementData[ size++ ] = e;

    Vector的底层结构和源码分析

    • Vector的基本介绍
      • 其底层也是一个对象数组；Vector是线程安全的，其操作方法一般都带有synchronized关键字，因此也导致了其运行效率不如ArrayList
      • 调用无参构造也会默认创建一个长度为10的elementData；在数组容量满了之后每次扩容的倍数为2

    LinkedList

    • LinkedList底层的实现原理是一个双向链表；其中维护了两个属性：first & last，分别指向了首节点和尾节点
    • 节点（Node对象），其中维护了prev，next，item三个属性；prev指向前一个，next指向下一个；node class中只包含了一个构造方法：Node( Node prev, E element, Node next)
    • LinkedList元素的增删不是通过数组完成的，所以相对而言效率比较高
    • LinkedList的无参构造其中没有包含任何操作

    LinkedList执行add()方法添加元素

    • add( element ) -> linklast( element )
      • 首先，LinkedList添加元素的思路就是往链表的最后一位添加元素，所以是将LinkedList对象中的last和原最后一位的next进行修改
      • final Node l 指向当前的last
      • final Node newNode = new Node<>(l, e, null)，创建新的last节点，因为是加在链表的最后一位，所以last为null
      • last = newNode，给last赋予新值
      • 判断 l 变量（即原last变量）是否为null
        • 如果为null，即之前的last为null，说明之前的链表为空，那么同时将first也赋值为newNode
        • 否则只将 l 变量的next赋值为newNode就足够了
        • size++ & modCount ++

    LinkedList中的remove方法

    • remove() -> 无参数，int参数，Object参数，如果无参数，那么默认移除链表中的第一个元素
    • removeFirst / removeLast
    • removeFirstOccurrence / removeLastOccurrence

    Set接口

    • 无序 -> 所以放入和取出的顺序是不一致的，但是每次取出的顺序是固定的；不允许重复元素 -> 所以也导致了只能包含一个null；但是不能使用索引的方式来遍历

    Set接口的实现类：HashSet

    • 其底层本质是一个HashMap，HashMap的底层是数组+单向链表+红黑树
    • HashSet扩容机制
      • 当HashSet添加一个元素时，会先得到该元素的hash值，并使用hash值作为存储时的key值（HashSet的本质是一个HashMap）
      • 根据hash值（key），找到Map中的对应位置是否有元素
      • 如果没有则直接放入表中；如果已经有元素则依次调用equals方法比较两者是否相同，如果相同则放弃添加，如果不相同则将新元素加到已有末位元素next的位置上
      • 在java8中，如果某条链表的元素个数达到TREEIFY_THRESHOLD（8个），而且整个table的大小 >= MIN_TREEIFY_CAPACITY（64个），那么就会进行树化（红黑树）

    创建HashSet对象并且添加元素的过程

    • Set testSet = new HashSet<>(); -> 底层是：map = new HashMap<>();
    • HashSet.add( E element ); -> map.put( element, PRESENT );
      • PRESENT 是HashSet类中的一个静态属性，仅仅是一个Object对象，作用只是在put方法中占位
      • element 和 PRESENT 传递到 map.put() 之后，被接收为 key & value
    • putVal( hash( key ), key, value, false, true );
      • hash( key ) 会计算key的hash值并做一定的处理，减低不同对象hash值碰撞的可能性
      • putVal()
        • 初始化变量 Node[] tab & Node p & int n & int i
        • 然后将tab指向属性table
        • 如果是添加第一个元素的话，那么table为null -> n = ( tab = resize() ).length;
        • resize() 会判断并创建一个新的长度为16的Node数组，并对table赋值；现在的tab为一个长度16的空数组（同样也是table），n也被赋值为该数组的长度，即16
        • 然后根据 ((p = tab[i = (n - 1) & hash]) == null)，算出来该key应该放到数组中的哪个索引位置，赋值给变量i，并且将该位置上的元素赋值给p；判断p是否为null
        • 为null则以hash和key创建Node对象，将该Node对象放到数组的i位置上
        • 如果不是第一次添加元素
        • 同样还是会根据 (p = tab[i = (n - 1) & hash]) 找出当前元素应该放到数组中的位置；如果该位置上还是null的，就直接放置该元素；如果不是null，则要进行比较两者是否相同
        • 判断1：根据hash值和equals判断当前元素和该位置链表的第一个元素是否相同
        • 判断2：当前节点是否为一个红黑树节点
        • 判断3：遍历该位置链表上其他的元素，如果不相同则轮到下一个，直到找到相同的元素则break退出或者找到null值，那么就是遍历到链表末位，因为已经遍历到链表末位都没有找到相同的元素，那么就将当前元素添加到该链表的末位
        • note：如果添加成功，则会返回一个null对象，那么整个add方法的返回值为true；不然为false
        • note：每次创建Node对象收录的时调用的构造方法都是：newNode(hash, key, value, null);，意思是之前传递的PRESENT Object() 也会一并收录到table中
        • note：class Node为HashMap中的一个内部类，有hash, key, value, next 4个成员属性

    LinkedHashSet

    • LinkedHashSet底层是一个LinkedHashMap，LinkedHashMap是HashMap的子类，其维护了一个数组+双向链表；根据元素的hashCode值来决定元素的存储位置，同时使用链表来维护元素的次序，是的元素看起来是以插入顺序保存的
    • LinkedHashSet的创建
      • 调用无参构造new LinkedHashSet<>() -> super( initialCapacity, loadFactor, dummy ) -> new LinkedHashMap<>(initialCapacity, loadFactor)；HashSet（LinkedHashSet的父类中专门为LinkedHashSet定义了一个构造器，会生成一个LinkedHashMap），然后LinkedHashMap是继承自HashMap的，调用LinkedHashMap的构造器的时候，会调用其父类的构造器生成一个HashMap
      • LinkedHashMap中：Entry是LinkedHashMap中用于存放元素的单位，定义为LinkedHashMap中的一个内部类，继承了HashMap中的Node类，除了hash, key, value, next这些Node类中的成员属性之外，还定义了 Entry before, after用于指向双向链表中的上一个和下一个；Entry head, tail 用于定位双向链表的第一个和最后一个
      • LinkedHashMap中重写了 newNode() 方法，在创建了新的Entry之后，会LinkNodeLast()方法，将新的Entry挂载到链表的末尾，同时根据情况更新LinkedHashMap中head & tail指向的对象（根据putVal()方法中的定义，只有当参数跟已有元素不重复的情况下才会调用newNode，确保了每次调用newNode就是有新元素要放入到table中）

    Map接口：

    • 用于保存具有映射关系的数据：Key - Value（双列元素）；当具有相同key值的元素被放到Map中时，会替换掉原先的元素；同样地，可以以null值为key，不过null key只可以有一个
    • 除了一个个的Node，在HashMap中还有 entrySet，values，keySet 成员属性方便程序员遍历Map中的元素（其中values和keySet不是直接在HashMap定义的成员变量）；不过要注意 keySet 和 entrySet 取出来是 Set 的形式；而 values 取出来是 Collection 的形式
    • HashMap放入元素的过程（概述）
      • 调用 hash( key ) 根据键值求出来当前元素应该放置的位置；然后再依次跟已在该位置上的元素进行比较，比较的依据是两者的hash已经equals()方法；一旦找到相同的key，那么就会退出循环，将旧的value替换为新的value，并返回被替换掉的旧value；如果一直到循环到null都没有找到相同的元素，那么就会依据传入的参数创建新的Node，并放置到null的位置上，然后返回null
      • 最后，put()方法根据putVal()的返回值是否为null，输出最后的布尔值

    Map接口的常用方法

    • remove() 根据键删除映射关系；get() 根据键获取值；size() 获取元素个数；isEmpty() 判断个数是否为0；clea() 清除键值对；containsKey() 查找键是否存在；keySet() 获取所有的键；entrySet() 获取所有的键值对；values() 获取所有的值

    HashTable 简介

    • HashTable的键和值都不能为null，否则会抛出NullPointerException
      • 如果尝试着向HashTable中put key 或者 value为null的键值对的话，put()方法中会首先判断是否为null，如果是null的话就会直接抛出NullPointerException；如果key是null，在随后的代码块中调用 key.hashCode()的时候就会抛出异常
    • HashTable的使用方法基本上都有加synchronized关键字，所以这些方法都是线程安全，不过这也导致了HashTable的效率对比HashMap会较低一点

    Properties

    • 继承了HashTable，集合中所有的键值对都是String
    • 通常用于从 xxx.properties 文件中加载数据到 Properties 类对象中

    TreeSet & TreeMap

    调用 put() 向TreeMap中添加元素的过程

    • TreeMap 中维护了一个成员属性root，类型为Entry，其中有 key, value, left, right, parent 等成员属性；仅有一个接收 key, value, parent 三个构造参数的构造方法
    • TreeMap中还有一个成员属性comparator，用于指向对TreeMap中元素进行排序的比较器，一般可以在创建TreeMap的时候将比较器作为参数传递进来
    • 添加过程
      • 定义赋值变量 t，指向成员变量 root，root的数据类型就是Entry
      • 检查 t 是否为null（说明之前没有向该TreeMap中添加过元素），如果是那么就直接使用传递过来的 key value 值创建Entry实例，并赋值给 root，并返回null
      • 如果 t 不为null
        • 定义辅助变量 cmp & parent，并创建变量cpr指向成员变量comparator，然后检查cpr（也就是comparator）是否为null，如果不为null那么就调用comparator的compare方法对key进行比较，如果comparator为null，那么就调用key本身的compareTo来比较key的大小
        • note：如果TreeMap中没有定义comparator，那么在每次调用put()朝里面添加元素的时候都会将添加的元素转型为一个Comparable的对象，如果该元素没有实现Comparable接口的话就会报错 -> 这是为了保证所有的元素都能按照某个规则来排序
        • 比较的原则有三条：
        • 原则一：如果比较方法（指comparator的compare() 或者是 比较对象本身的 compareTo() ）的返回值为0，那么就说明当前传递元素的key值与已有元素的key值重复，那么就调用重复元素Entry的setValue方法，替换新老value值，并将原有oldValue返回
        • 原则二：如果比较方法返回值为负，则将添加的元素放到当前元素的左边；如果返回值为正，则放到右边；note：比较过后唯一可以确定的就只有是左边还是右边，确切的位置要等到一直比较出现null为止才可以确定
        • 原则三：root会根据新元素的加入而改变，估计root的确定跟红黑树有关？

    调用add()方法向TreeSet中添加元素

    • TreeSet的底层实现是一个TreeMap，每次调用TreeSet的add()方法，其底层都是调用了TreeMap的put()方法
    • 要向TreeSet中添加的元素作为key传递，而value则是TreeSet中一个static final的成员变量PRESENT