java集合基础概念及源码流程分析

学习资源：b站 韩顺平 java集合/人人都是程序员 看动画学java集合 感谢二位的开源视频，无基础先看
《看动画学java集合》，有基础看 《 java集合》 文章为个人学习笔记，如有错误还请包涵

1. 目的：为了方便和高效地存储大批量的数据，变量和数组是远远不够的，我们需要能动态扩容的容器来存储。

2. java的集合
   

3. 键值对

• 分类
  
• Collecion工具类
  • 排序方法
    
  • 查找替换
    
• 迭代器Iterator
  • 所有的集合都实现了迭代器Iterable接口，迭代器是遍历集合的元素，并且返回。
  • 实现：1. 先新建迭代器 2. 调用hashnext方法 3. 调用next方法
  • 增强型for循环的底层实现也是迭代器

• HashSet,由HashMap实现

  1. 无序，存取顺序不一致，其他特点与HashMap一致

  2. 区别，HashMap是以key-value存放，而HashSet则是把key当value用，而value则由统一的值代替。

  3. 添加元素时，如果在同一个下标处有别的值，则用equals进行比较，如果相同则放弃添加，不同则添加到后面。

  4. add方法初次添加，源码及流程分析
     

  5. add方法再次添加流程
     

• LinkedHashMap，继承自HashSet，但是由LinkedHashMap实现及数组+双向链表，因此具有LinkedHashMap的特点

  1. 有序，由双向链表维护添加顺序，即存取顺序一致

  2. 其他特点与LinkedHashMap相同，key唯一，key可为null

  3. 区别：
     

  4. LinkedHashMap数组存放的节点为LinkedEntry，$表示内部类。
     

• TreeSet

  1. 无序，存取顺序不一致，其他特点于TreeMap相同

  2. 实现了NavigableSet和SortedSet接口，可以使用Comparator的compareTo方法进行排序

  3. HashSet，LinkedHashSet，TreeSet的区别：

     HashSet，添加查询快性能优于后两者。LinkedHashSet添加修改删除快，有序
     TreeSet只有在需要对元素进行排序时使用

• Map的遍历

  • 基于EntrySet机制，可以分别拿到所有单独的Key或所有Value，以及k-v。

    Hashmap map = new HashMap();
    Set entrySet = map.entrySet(); 
    Collection values = map.values();
    Set keySet = map.keySet();
    //example
    for(Object key : keySet) {
        System.out.println(key);
    }
    

  • 可以使用增强for/迭代器Iterator来遍历指定的集合（keyset，values，entryset）

• HashMap，基于数组与链表（JDK1.7）/链表+红黑树（JDK1.8）实现，初始容量16，增删改查快

  1. 无序，key可以为null但只能有一个，并且hash值为0，key不可以重复，value可以重复，以键值对的形式存储，会被封装到HashMap$Node中。元素的下标由数据的hash值&（数组容量-1）得到，因此存放的顺序是无序的。如果有重复的值则会覆盖。
     

  2. Map接口的特点：key-value会以Node类型存放，但是为了方便遍历会创建EntrySet集合，该集合存放的类型为Entry，即 transient Set> entrySet; 然而entrySet中定义的类型是Map.Entry，但实际上存放的仍是Node，因为Node实现了Entry接口，之所以能够存放进EntrySet中是此处是做了向下转型的操作。并且数据只会存放一份在Node中，EntrySet存放的是引用。（先看图再看文字）

  3. 哈希冲突，当同一个下标有多个数据时，会以链表的形式存放数据

     • 树（红黑树）化,当链表长度大于8且数组容量大于64时，链表会转化为红黑树（自平衡二叉树），以此提高查询速度，新增数据时需要计算节点的位置
       
     • 链化，当红黑树中的节点小等于6时，树将转化为链表，因为此时节点数很少，用红黑树查询的速度不比链表快。并且在新增元素的适合，链表不需要计算节点的位置，可以直接插入队尾。

  4. 扩容，当元素个数超过临界值时就需要扩容，临界值 = 容量 * 负载因子（默认0.75），扩容后的容量是之前的两倍

• LinkedHashMap,继承自HashMap，用双向链表解决了HashMap无序的问题。

  • 有序，key唯一，key可为null
  • 维护的元素排序顺序：默认维护添加顺序
    • 添加顺序，元素添加和取出的顺序一致，头节点为第一个元素，尾节点为最后一个元素
      
    • 访问顺序，用get访问某元素，则该元素为尾节点，该元素的next节点为头节点
      

• TreeMap，基于红黑树实现的Map。

  1. 无序并会对key排序，key唯一，key不可以为null，因为红黑树是自平衡二叉树，会先比较，而null不能比较，会抛出NullPointerException。

  2. 可以自定义的比较器来排序，put流程源码如下图

     TreeMap treeMap = new TreeMap<>(new Comparator