百木园-与人分享，
就是让自己快乐。
当前位置：百木园 > 野生技术 > 正文

Java常用集合基础概念及源码流程分析

2022-06-29 分类：野生技术 阅读(243) 评论(0)

java集合

学习资源：b站 人人都是程序员 《看动画学java集合》
b站 韩顺平 《java集合》 感谢二位的开源视频，本博客为个人笔记，如有错误还请包涵
学习方法：推荐观看视频，自己用idea敲一遍然后debug一步步看，最后自己写笔记和画流程图。

前 言

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

  2. java的集合
    image-20220608182525812

  3. 键值对

    image-20220628215836129

Collection

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

Collection

Set

  • HashSet,由HashMap实现

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

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

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

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

    5. add方法再次添加流程
      image-20220624190559250

image-20220624190828097

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

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

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

    3. 区别：
      image-20220609111157209

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

      image-20220626161246350

      image-20220626161639139

  • TreeSet

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

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

    3. HashSet，LinkedHashSet，TreeSet的区别：

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

Map

  • 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）得到，因此存放的顺序是无序的。如果有重复的值则会覆盖。
      image-20220608192636143

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

      image-20220627162007467

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

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

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

      image-20220624191048893

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

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

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

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

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

      TreeMap<Object, Object> treeMap = new TreeMap<>(new Comparator<Object>() {
    @Override
    public int compare(Object o1, Object o2) {
    return ((String)o1).length() - ((String)o2).length();
    }
});
 treeMap.put(\"aa\",\"aa\");
 treeMap.put(\"1213\",\"3\");
 treeMap.put(\"z\",\"aa\");

3

  1. 红黑树的特点，在插入时依次先比较，然后再根据规则左右旋。
    image-20220609105428265

  2. Hashtable，继承Dictionary<K,V> 实现了Map<K,V>

    • 初始化大小是11，负载因子为0.75，扩容按自己的机制来

    • Key和Value都不能为null，否则会抛出空指针异常

    • 是线程安全的，hashMap是线程不安全的

  3. Properties，继承自Hashtable，实现了Map接口，也是K-V形式

    • 通常用于配置文件

List

  • ArraysList，基于数组实现，默认容量为10，扩容时会先创建一个原始1.5倍的数组，然后再把元素复制过去。特点：

    1. 有序，可存重复元素，可存null
    2. 查询快，增删慢，适合查询较多的场景
    3. 如果使用无参构造器，则初始elementData容量为0，第一次添加时则扩容为10，如需再次扩容，则扩容1.5倍
    4. 如果使用指定大小的构造器，则初始elementData为指定大小，扩容仍为1.5倍。

    add方法，扩容机制，源码和流程分析

    public static void main(String[] args) {
        ArrayList<Object> list = new ArrayList<>();

        for (int i = 0; i < 10; i++) {
            list.add(i);
        }
        list.add(11);
        list.add(12);
    }

    创建ArrayList，循环添加元素，因为初始容量为10，当添加11时会扩容，观察源码执行情况。

    1. 先进入int的自动装箱
      image-20220621015551502
    2. 进入add方法，注意此时的size为0
      image-20220621015640575
    3. 调用ensureCapacityInternal方法，这里分为了三步计算容量
      image-20220621015948386
    4. 计算容量，返回minCapacity，初始值为10
      image-20220621020422058
    5. modCount标记修改次数，在需要考虑线程安全时起作用，if判断当前容量是否进行扩容
      image-20220621020157924
    6. 调用Grow方法，第一个if保证初次扩容时，容量为10，扩容后返回
      image-20220621020854237
    7. 添加成功
      image-20220621021212411

  • LinkedList，基于双向链表实现，增加则直接在尾部插入

    1. 有序，可存重复元素，可存null
    2. 查询慢，增删快，适合增删较多的场景
    3. 和ArraysList相比需要记录前后节点，所以内存消耗比ArraysList大

  • Vector，线程安全的，效率不高，无参构造默认是10，2倍扩容
    image-20220622164021738

fail-fast快速失败机制

  1. 为了避免多个线程对同一容器并发修改时造成的数据异常。

  2. 实现机制：在容器类种定义一个modCount属性，记录容器修改的次数，当容器有添加或删除的操作modCount就++，在迭代的时候比较，如果不相同说明有多个线程同时修改，则抛出ConcurrentModificationException异常。

  3. 采用线程安全的容器即可避免并发的问题。

    线程不安全 线程安全
    ArrayList CopyOnWriteArrayList
    HashMap ConcurrentHashMap
    HashSet CopyOnWriteArraySet

  4. 线程安全容器ConcurrentHashMap

    • 同步，仅对头节点加锁，因此并发度为数组容量
    • 统计元素个数，为了解决线程安全问题，使用CAS（compare and swap）算法，同一时刻只允许一个线程更新个数，其余线程更新失败，失败的线程再循环更新直到成功为止，但这样效率也很低，因此让更新失败的线程先把值累加到数组中。最后的个数由baseCount和CounterCell数组累加
    • 多线程协同扩容，每个线程负责一段步长的数据迁移。
    • key，value不为null，避免出现不知道是拿出来value为null还是key根本不存在。
    • 只针对位置加锁

来源：https://www.cnblogs.com/Liber-blog/p/16423569.html
本站部分图文来源于网络，如有侵权请联系删除。

未经允许不得转载：百木园 » Java常用集合基础概念及源码流程分析
标签：

相关推荐

  • 暂无文章

热门文章