JavaSE集合相关知识(个人总结)

    声明: 1. 本文为我的个人复习总结, 并那种从零基础开始普及知识 内容详细全面, 言辞官方的文章
              2. 由于是个人总结, 所以用最精简的话语来写文章
              3. 若有错误不当之处, 请指出

基础:

  • List和Set都是Collection, Map不是Collection
  • ArrayList底层是数组, LinkedList底层是双向链表, HashSet底层是HashMap
  • LinkedList功能很强, 它同时是Queue和Deque的实现类

有序 & 无序:

​ List是有序的, Set和Map是无序的;

​ 这里的顺序指的不是元素添加顺序, 而是添加方式: Set/Map的话被Hash散列到哪个桶位置是无规律无序的, 而List是一定会被添加到链表尾

​ TreeSet(基于红黑树实现)对元素进行大小升序排序(元素本身具有可比较性),

​ LinkedHashSet使用额外的指针来记录元素的添加顺序, 但依旧都是无序的

​ 如果添加了相同key的key-value对, 则key不变, 而value被覆盖

​ TreeMap是按key进行比较的

Iterator:

Iterable接口(Collection的祖先)里有一个方法, 叫做Iterator<T> iterator( ); // 迭代器

遍历时的坑:

​ 迭代器遍历时, 不要修改增删集合的元素, 否则会报并发修改异常ConcurrentModificationException,

​ 比如遍历ArrayList集合期间删除了元素 导致modCount != expectedModCount

​ 这里的并发并非是线程并发, 而是指一边遍历一遍修改

要是想不报错, 即忽略迭代器 和 实际集合的元素数量不相等, 就使用CopyOnWriteArrayList;

仅仅是不报错而已, 迭代器并不能感知到新加的元素

ArrayList:

构造方法:

  1. ArrayList( ) 使用长度为零的数组
  2. ArrayList(int initialCapacity) 使用指定容量的数组
  3. public ArrayList(Collection<? extends E> c) 使用c的大小作为数组容量, 并拷贝c的元素

扩容规则:

数组扩容本质是 new一个新数组, 然后再把旧数组的值拷贝进去

  1. add(Object o):

    • 首次添加元素扩容为 10
    • 以后添加元素扩容为上次容量的 1.5 倍
  2. addAll(Collection c):

    • ArrayList没有元素时,扩容为max(10, 实际元素个数)

    • ArrayList有元素时, 扩容为max(原容量 1.5 倍, 实际元素个数)

LinkedList 对比 ArrayList 的区别:

LinkedList

  1. 基于双向链表,无需连续内存
  2. 随机访问慢(要沿着链表遍历)
  3. 头尾插入删除性能高; 其他部位插入删除性能略低
  4. 占用内存多, 因为要维护额外的

ArrayList

  1. 基于数组,需要连续内存
  2. 随机访问, 根据下标访问时较快; 如果要remove(Object o) 时较慢,因为没用到下标
  3. 尾部插入、删除性能高; 其它部分插入、删除性能很低, 因为要移动数据
  4. 可以利用 cpu 缓存+局部性原理, cpu会对访问过的元素以及它附近的元素加到缓存里, 那样下次访问附近元素时会较快

HashMap:

底层数据结构:

  • 1.7 数组 + 链表
  • 1.8 数组 + (链表 | 红黑树)

树化与退化:

树化的意义:

  • 红黑树用来避免 DOS 攻击,防止链表超长时性能下降;

  • TreeNode占用空间较大,如非必要的话尽量还是使用链表

  • 树化应当是极少的偶然情况,是保底策略

    hash 值如果足够随机,则在 hash 表内按泊松分布; 在负载因子 0.75 的情况下,长度超过 8 的链表出现概率是 0.00000006; 树化阈值选择 8 就是为了让树化几率足够小

树化的规则:

当链表长度超过树化阈值 8 时,先尝试扩容来减少链表长度;

如果数组容量已经 >=64,才会进行树化

退化规则:

在扩容时如果拆分树时,树元素个数 <= 6 则会退化链表

  1. 情况1, 在扩容时如果拆分树时,树元素个数 <= 6 则会退化链表
  2. 情况2, remove 树节点时,若 root、root.left、root.right、root.left.left 中任意一个为 null,也会退化为链表

索引桶下标计算:

计算方法:

  1. 先计算对象的 hashCode( )

  2. 再调用 HashMap 的 hash( ) 方法进行二次哈希, 这是是为了让哈希分布更为均匀;

    比如相邻的Integer整数的哈希码就相邻很近, 就没有很好的散列性了

    **容量大小是2^n个的副作用: **散列性不好,所以需要二次 hash 来作为补偿

    容量大小是质数时, 对质数求模的散列性较高(如.Net的Dictionary类)

    Hashtable没有采用二次哈希, 也不是质数, 而是新容量=2倍旧容量+1; 散列性 没质数好, 但比2^n偶数好

  3. 最后 & (capacity – 1) 求模得到索引

数组容量为何是 2^n

  1. 计算索引时效率更高:如果是2的n次幂可以使用位与运算代替取模
  2. 扩容时重新计算索引效率更高: hash( )后的值 & 旧容量== 0 的元素留在原来位置, 否则新位置 = 旧位置 + 旧容量

put 流程

  1. HashMap 是懒惰创建数组的,首次使用才创建数组, 默认是16

    如果是指定数组容量, 则会选择一个 最接近且≥指定容量的2^n的数字作为容量

  2. 计算索引(桶下标)

  3. 如果桶下标还没人占用,创建 Node 占位

  4. 如果桶下标已经有人占用

    1. 已经是 TreeNode 走红黑树的添加或更新逻辑
    2. 是普通 Node,走链表的添加或更新逻辑; 如果链表长度超过树化阈值,走树化逻辑
  5. 返回前检查容量是否超过阈值(总Node个数达到容量的3/4),一旦超过则进行扩容

哈希冲突:

概念: 两个Key散列后落在了同一个桶下标位置

解决办法:

  1. 开放定址法: 发生冲突时就依次往下一个桶下标位置找, 直至找到空位为止
  2. 再哈希法: 有多个Hash函数, 这个冲突了就用别的备用Hash函数
  3. 链地址法: 冲突的元素都放在这个桶下标位置, 靠 链表或红黑树 来连接这多个元素
  4. 建立一个公共溢出区: 将哈希表分为基本表溢出表两部分, 凡是和基本表发生冲突的元素, 一律填入溢出表

1.7 与 1.8 的区别

  1. 1.7 是头插法,1.8 是尾插法
  2. 1.7 是≥阈值 & 此桶下标位置已有元素时 扩容,而 1.8 是>阈值时扩容
  3. 1.8 在扩容时的计算Node的索引时会优化

扩容因子为何是 0.75?

  1. 在 空间占用 与 查询时间 之间取得较好的折中权衡
  2. 大于这个值,空间节省了,但链表就会比较长影响性能
  3. 小于这个值,冲突减少了,但扩容就会更频繁,空间占用也更多

扩容规则:

扩容时新容量是旧容量的2倍

扩容时元素位置的变化: 1.8 在扩容时的计算Node的索引时会优化: hash( )后的值 & 旧容量== 0 的元素留在原来位置, 否则新位置 = 旧位置 + 旧容量

并发问题:

并发死链问题(1.7才存在):

由于1.7的头插, 每次扩容后链表都会逆序, 容易在并发场景造成环状死链问题

  • e 和 next 都是局部变量,用来指向当前节点和下一个节点
  • 线程1的临时变量e和next刚引用了这俩节点,还未来得及移动节点,发生了线程切换,由线程2完成扩容和迁移
  • 线程2 扩容完成,由于头插法,链表顺序颠倒。但线程1的临时变量e和next还引用了这俩节点,还要再来一遍迁移, 形成了死链

并发数据覆盖问题(1.7,1.8都存在):

A线程计算得到索引1的位置没有元素, 刚准备占位但还没来得及占;

这时B线程也发现了索引1的位置没有元素, 然后也刚准备占位但还没来得及占;

切到A线程放了K-V对, 再切到B线程放K-V对时, 覆盖了A线程刚放的K-V对

key 的设计:

Map里key 的设计要求:

  1. HashMap 的 key 可以为 null,但Map的其他实现类并不允许key为null

  2. 作为 key 的对象, 必须实现 hashCode( ) 和 equals( ),

  3. key 的内容不能修改;

    • 会导致map中出现了相同的key
    • 会导致再次查询时就查询不到数据了, 因为hashCode变了, 计算桶下标时就可能会找错桶

    put时会计算索引位置, 会查看key的值; 而put进map集合后, 对于key的变化 map就感知不到了

  4. key 的 hashCode 应该有良好的散列性, 使均匀分布

String 对象的 hashCode( ) 设计, 为啥每次都是乘31?

字符串中的每个字符都可以表现为一个数字,称为 S_i,其中 i 的范围是 [0, n-1]

散列公式为: S_0∗31^(n-1)+ S_1∗31^(n-2)+ … S_i ∗ 31^(n-1-i)+ …S_(n-1)∗31^0

目标: 达到较为均匀的散列效果, 每个字符串的 hashCode 足够独特;

  1. 为了增大散列性: 31是质数, 有较好的散列特性

  2. 为了提高计算效率: 31接近2^5, 2^n可以用移位操作, 所以31 * h 可以被优化为 (h<<5)-h

上一篇:Suricata开源IDS安装与配置


下一篇:Css3渐变(Gradients)-径向渐变