武功滞涩处(算法篇)
Nico Liao 阿蒙

文章格式提醒:问题2级、答案分支依次递减 ; 未解决的结尾用”?”进行标识;倒序更新。

Java常用的数据结构?

Collection

List – 有序可重复列表

ArrayList

1、底层是用数组实现的,重要的成员有 元素数组/数组中元素数 size/ modCount 修改次数;操作系统层面:数组在内存中存储是地址连续的,而链表节点是分散的,这就可能造成前驱 节点在一页,后继节点在另一页,在遍历时可能会发生页表置换

2、进行 add 添加时,若没有指定添加位置,就会根据 size 确定添加的新元素在数组中的下标进行添加, 若 size >= 数组长度,则需要扩容

3、在进行扩容时,会将 modCount++,并且会将原数组中的元素,拷贝至新数组中,新数组的大小是 原数组的 1.5 倍,默认的初始容量是 0,且在第一次添加元素时,设置数组大小为 10

4、若指定 i 为添加元素的位置,会调用 System.ArrayCopy 方法对 i 下标以后的元素进行拷贝,拷贝完成 后再把添加的元素放在 i 位置

5、调用 get 方法时,由于 ArrayList 底层基于数组,因此他实现了一个 RandomAccess 标识接口,表示 按下标读取数据速度很快,主要是由于数组在内存中是连续存储,可以通过第一个元素的存储地址和偏移量 offset 直接计算得到访问的元素的存储地址

6、若 get 方法是通过元素的值进行查找,则需要遍历数组

LinkedList

1、LinkedList 是基于链表存储的,链表中节点 Node 重要包含存储的元素的引用 E,指向前驱节点指针 prev 和指向后继节点的指针 next,LinkedList 中重要成员主要有 size/头节点 first/尾节点 last

2、LinkedList 由于 Node 在内存中是分散存储的,因此没有对 size 限制,在执行 add 方法时,默认添加在 链表的尾部

3、若指定添加元素在链表中的位置,LinkedList 需要调用 node 方法,传入参数 Index 找到对应的节点, 在查找对应的节点时,若 Index < size / 2,从头节点向后遍历,若 Index > size / 2,从尾节点向前遍历, 因此即使添加元素只需要改变节点的指针,但查找添加的位置的耗时仍然不小,开销不比 ArrayList 少

4、调用 get 方法时,若按下标查找,也需要进行同样的遍历,性能比 ArrayList 差很多,按元素值进行查找时, 也需要进行遍历,与 ArrayList 相比半斤八两

5、链表节点除了元素值,还需要维护两个指针,导致 LinkedList 存储的内存开销远大于 ArrayList

Vector & Stack

1、Vector 也是基于数组进行存储,其原理与 ArrayList 类似,区别在于,Vector 中会维护一个 CapacityIncrement 变量,每一次进行扩容时,只增加一个 CapacityIncrement 变量的大小,若没有指定 CapacityInc,默认为 0,且在 扩容时,若 CapacityInc 为 0,则将数组大小翻倍

2、Vector 中的所有增删改查方法,包括 get 方法,都通过在方法上加 Sychronized 锁方式锁住 Vector 对象, 实现线程安全,性能较差

Set – 不可重复列表

HashSet

内部有一个成员变量的 HashMap,实际上就是使用的 HashMap 的方法

TreeSet

内部有一个成员变量的 TreeMap,底层就是 TreeMap

LinkedHashSet:底层调用的 HashSet 的方法,HashSet 中的 HashMap 也可以是 LinkedHashMap,因此实际是由 LinkedHashMap 实现

Queue / Deque

LinkedList 实现 Queue 和 Deque,LinkedList 中使用 first 和 last 两个节点的指针用来标记链表的头/尾节点, 当进行 add 方法添加时,默认是在链表尾部添加,调用 poll 方法时,就会返回 first 节点,调用 pop 方法时, 返回 last 节点

ArrayDeque

数组的方式实现了双端队列,主要是使用 head 和 tail 两个指针来标记 队列头/栈底 和 队列尾/栈顶

PriorityQueue

使用数组的方式实现了优先队列,内部其实是一个二叉堆结构(小顶堆),原理逻辑与堆排序一致

重要属性有 size,用来标记数组中元素的个数,即新添加的元素的下标

执行 offer 方法时,先确认 size 是否大于等于数组长度,若大于等于则进行扩容,执行 siftup 方法

siftup 方法中,若制定了 Comparator,按照 Comparator 的 compare 方法与父节点比较,也就是 (size - 1) >>> 1 下标对应的元素进行堆的插入,若没有指定,按元素实现的 Comparable 接口的 compareTo 方法进行比较

执行 poll() 方法时,若 size 为 0,返回空值,否则返回数组中下标为 0 的堆顶元素,将数组下标 0 位置替换为 size - 1 位置的元素,并减小 size,调用 siftdown 方法整理堆

siftdown 方法同样也分为根据 Comparator 和 Comparable 两种比较,主要是对 0 位置新换上来的元素与子节点进行 比较,将其与最大的并大于 0 位置的子节点进行交换,并循环直到将其放到合适的位置

BlockQueue

阻塞队列,详见并发

Map

HashMap

重要成员变量

1、负载因子:默认为 0.75,表示 HashMap 存储的元素数到达 HashMap 散列数组长度的 0.75 时就进行扩容

负载因子越大,散列数组的

2、散列数组:HashMap 通过分离链表法解决哈希冲突的问题,在散列数组中存储的就是链表中的一个个头节点

3、K-V 键值对以 Node 节点的方式进行存储,Node 继承自 Map.Entry,包含 Next 指针,Key,Value 和 hash

4、threshold 门限,就是 负载因子 * 数组容量

5、size,HashMap 中当前存储的节点数

put 方法流程

1、再哈希:首先对 Key 进行再哈希,将 Key 的 HashCode 按位有符号右移 16 位,再与原本的 HashCode 进行抑或 # 目的:在对散列数组长度取余时,高位通常不参与运算,再哈希让高位参与哈希运算,让低位尽量不同,使哈希分 布更均匀

2、检查散列数组是否为空,若为空

3、若 Key 的 HashCode 对应的散列数组位置上节点为空,则直接将新节点加入

4、若不为空,比较链表的头节点 Key 与 put Key 的 HashCode 是否相等(== || equals),若相等,进行更新, 若不相等,顺着链表按同样的逻辑进行比较

5、若是 1.8 的HashMap,会先判断链表的头节点是否是 TreeNode,若是,则按照红黑树的逻辑 进行插入

6、1.7 的 HashMap 中,若遍历完链表仍未找到 Key 相同的节点,则将新节点加入到链表头,会造成并发扩容的死链问题, 1.8 中,将头插法改为了尾插法,解决了死链问题,但并发环境下的其他基本问题,如更新丢失等,仍然没有解决

7、若添加后 size >= threshold,就会进行扩容

扩容流程

1、首先 HashMap 的初始容量是 16,并且每次对原数组长度 * 2 进行扩容,当 size > threshold 时就会进行扩容 # HashMap 每次 * 2 的原因:1)2 的幂次可以用 & 的方式进行取余运算,效率更高;2)在扩容移动链表节点时, 节点在新数组中的位置只可能是原位置 i 或 i + oldCap 旧数组长度,扩容时效率更高

2、创建新的散列数组,并将旧的散列数组中的链表的头节点拷贝至新数组中,在移动时,节点的 hash 与 oldCap 进行 & 运算,若结果为 0,表示在新数组中位置不变,若不为 0,表示在新数组中位置为 i + oldCap

3、在移动节点时,会使用一个 loHead/loTail 和 hiHead/hiTail 分别指向新数组中位置 i 和 i + oldCap 的链表的头尾节点, 用一个 next 指针指向当前正在移动节点的下一个节点,在 1.8 中,由于使用尾插法,每一次移动节点都会添加至 loTail/hiTail 之后,不会发生死链问题,而在 1.7 中,由于使用头插法,每一次移动节点都会添加至 head 之前,会发生扩容死链问题

4、1.7 扩容死链问题:t1 线程正在移动 A 节点,next 节点指向 A 节点的下一个节点 B,即 A -> B,此时 t2 线程完成了 A 和 B 的移动, 此时 B.next = A,在 t1 移动 A 到新数组中后,当前正在移动节点 e 指向 B,next 指向 B.next = A,此时就形成了链表中的环,最终导致 程序崩溃

红黑树

1、红黑树类似于 AVL 树,他的查找效率略差于 AVL 树,为树的深度 2log(N + 1),相比于 AVL 树,红黑树通过节点到叶子节点路径 上黑色节点的数目控制树的平衡,AVL 树通过比较两棵子树的高度差是否超过 1 决定是否平衡,因此红黑树对平衡性要求更低,并且 AVL 树 只能通过单旋转或双旋转重新平衡树,红黑树可以通过修改节点的颜色进行平衡,发生旋转的次数更少,插入删除的效率更高

2、特点

每个节点不是黑色就是红色,根节点是黑色

红色节点的子节点必须是黑色

从一个节点到每一个叶子节点的路径上的黑色节点数必须相同

3、HashMap 中什么时候树化/树退化

1、当链表长度达到 8 时进行树化 # 在 HashMap 源码注解中有解释为什么是 8,大概意思是,红黑树的节点大小大约是正常节点大小的两倍, 并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记,在理想情况下,使用 0.75 作为负载因子, 采用随机哈希算法,树化阈值与树化频率遵循泊松分布,选择 8 的概率是 千万分之 6,7 的概率约是 十万分之 1

2、当扩容后链表长度小于等于 6 进行树的退化 # 红黑树的节点大小大约是正常节点大小的两倍,并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记, 并且在插入和删除时维护红黑树的平衡性需要额外的开销

ConcurrentHashMap

通过分段锁 Segment 保证线程安全,Segment 继承自 ReentrantLock,每一个 Segment 中都包含一个 volatile 的 HashEntry 数组, 一个 volatile 的 count 表示当前 Segment 中存储的 K-V 节点数,一个 Threshold 表示扩容阈值

HashEntry 是基本存储单位,与 HashMap 中的Entry 基本一样,包含 Key,Value,next,hash,区别在于 HashEntry 的 Value 是 volatile 的,因此对 value 的修改对所有线程可见,并且 next 指针是 final 修饰,防止扩容时发生死链

ConcurrentHashMap 默认有一个长度为 16 的 Segment 数组,在进行增删改查时,会根据 Key 对 16 取余得到具体处于哪个 Segment, 对于 get 操作不加锁执行,对于 put 等修改操作,调用 Segment 的 lock 方法锁住当前段进行修改,不影响其他段的并发操作,在进行扩容 时,也仅是对单个 Segment 进行扩容

1.8 的 ConcurrentHashMap 摒弃了 Segment,采用 CAS 和类似于分段锁的方式保证线程安全

大体结构与 HashMap 一样,在 put 操作时,若 Node 数组对应下标处为空,使用 CAS 的方式不加锁添加节点,若数组中当前位置链表 头节点不为空,则对链表头节点加锁,在 Sychronized 同步代码块中执行与 HashMap 同样的逻辑

ConcurrentHashMap 在扩容时的移动原数组节点到新数组的操作,可以由多个线程并发完成,从而大大提高效率,在进行移动时, 会将当前线程正在移动的头节点包装为一个 ForwardNode,用来标识当前位置正在移动,当其他线程遍历到数组中的 ForwardNode 节点时,就会忽略并继续遍历,从而保证线程安全,并且在扩容时,仍然可以执行增删改查操作,这些操作通过头节点的 hash 判断 是否是一个 ForwardNode 节点,若是,则调用 helpTransfer 方法,并发的帮助完成扩容动作,完成后再回到循环中执行 put

get 方法也是通过 Unsafe 的 getObjectVolatile 进行读取,不加锁

TreeMap

底层是红黑树

LinkedHashMap

采用 HashMap 来存储节点,用一个双向链表存储 HashMap 的 Node 节点使其有序

HashTable

使用 Sychronized 锁住方法来保证线程安全,并且默认初始容量为 11,每一次扩容为 oldCap * 2 + 1

Iterator 迭代器

1、用来进行集合的遍历,不同的集合有不同的实现,例如 ArrayList 通过一个 cursor 指向下一个遍历的 元素的下标,用一个 lastRet 表示上一个遍历的元素的下标

2、Iterator 接口中主要包含三个基本方法,hasNext 判断是否还有下一个元素,next 表示遍历获取下一个 元素,remove 表示删除元素

3、常见的三种遍历方式,fori,foreach,Iterator,其中 fori 只能用于知道集合中具体元素数量时, fori 和 foreach 只能用于知道集合中元素具体类型时,foreach 底层就是 Iterator 的方式遍历

三种遍历方式的删除

fori

在 fori 进行删除时,问题在于删除当前下标会导致之后的元素前移, 比如 “A,B,B,C,C”,在 fori 中判断若元素等于 B 就删除,则会导致 i = 1 时,进行 删除后,i = 2 位置的 B 到达 1 的位置,即 “A,B,C,C”,而此时 i 已经到达 2 的位置, 即 i 指向 C,从而造成漏删,可以通过删除后让 i - 1,或者反向遍历删除解决

foreach

对于 ArrayList 等迭代器是 fail-fast 的集合,在遍历时底层是使用迭代器进行遍历, 但在删除元素时,由于没有显式的获取迭代器,因此调用的是 List 的 remove 方法,会触发 迭代器的 fail-fast 机制,抛出异常中断程序

Iterator

没有任何问题

fail-fast

迭代器实现了 fail-fast 机制的集合,在集合中都会维护一个 modCount 成员变量,用来表示对集合的修改次数, 在获取迭代器时,在迭代器中会为一个 ExpectedModCount 变量赋值为当前的 modCount,在执行 next,remove,hasnext 方法之前,会先对迭代器的 ExpectedModCount 与集合的 modCount 进行比较,若不相等直接抛出异常

fail-safe

Java 中实现 fail-safe 迭代器的集合主要都是通过 Copy-On-Write 方法实现的,例如 CopyOnWriteList,其内 部有一个 ReentrantLock 锁对象,在进行增删改操作时,先加锁,将原有的数组拷贝一份,在新的数组上进行修改,而获取 迭代器时,会用一个 final 变量指向当前的数组,在旧的数组上进行遍历

  • 本文标题:武功滞涩处(算法篇)
  • 本文作者:Nico Liao
  • 创建时间:2022-03-25 22:45:34
  • 本文链接:https://www.lzp.zone/2022/03/25/武功滞涩处(算法篇)/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论