Java集合复习总结


别问 问就是为了面试豁出了老命

List

  • Vector
    • 线程安全
  • ArrayList
    • 基于数组实现
    • 适合读,不适合改
    • 线程不安全
  • LinkedList
    • 基于链表实现
    • 适合修改,但不适合读
    • 线程不安全
  • CopyOnWriteArrayList
    • 读写分离
    • 在执行修改操作的时候会复制一块新的空间
    • 写操作会出现进程阻塞,但是读操作不会
  • Collectionbs.synchronizedlist
    • 线程安全所有方法都加了synchronized关键字

ArrayList源码分析

  • 扩容机制以及初始化
    • JDK1.7之前默认大小为10,JDk1.8之后,之后开始使用list集合才会分配10的空间
    • 1.5倍扩容
  • 读写操作分析
    • 扩容
      扩容利用Arrays.copyOf() (在原来的数组中重新创建数组) 进行扩容
    • 插入或修改
      利用System.arraycopy()进行操作,如果是删除,则向前移动,如果是插入则向后移动

      LinkedList源码分析

  • 删除插入都比较容易双向链表的插入
  • 在指定位置插入数据

    • toArray转化成对象数组
    • 之后遍历对象数组
    • 之后再插入

      Map

  • hashmap

    • 线程不安全
    • 默认大小16
    • 可以存储值为null的key和value
    • 双倍扩容
  • hashtable
    • 线程安全
    • 默认大小11
    • 不可以存储值为null的key和value
    • 2n+1倍扩容
  • concurrentHashmap
    • 线程安全
    • 读取用cas,更改用synchronized
    • 发生hash冲突,会用cas写入

HashMap源码分析

  • 参阅原帖
    hashmap
  • 扩容机制和默认大小
    默认大小为16,扩容为双倍扩容
  • 链表转红黑树
    当链表节点超过8时,转为红黑树
  • 红黑树转链表
    6个节点红黑树转回链表
  • 定位哈希桶数组的位置
    hash桶.jpg

    1. 获取map中 key的hash值
    2. 将 hashCode 的高位参与运算,重新计算 hash 值(当table比较小的时候,让高位也参与运算)
      • hashcode 异或 hashcode高16位 以此获取hash值
      • 如果没有这一步,table长度为16,直接进行 与 运算,那么高28位的运算结果都是0,那么hash桶则只在15的区间内分布,那么hash冲突的概率就会上升。
        hashmap1.8优化.jpg
    3. 计算出来的 hash 值与 (table.length - 1) 进行 & 运算
  • jdk1.7为头插法,jdk1.8改为尾插法