🚩DS - 数据结构

树

🌟比较不同的树

• 二叉查找树(BST) ：解决了排序的基本问题，但是由于无法保证平衡，可能退化为链表；
• 平衡二叉树(AVL) ：通过旋转解决了平衡的问题，但是旋转操作效率太低；
• 🌟红黑树 ：通过舍弃严格的平衡和引入红黑节点，解决了 平衡二叉树旋转效率过低的问题，但是在磁盘等场景下，树仍然太高，IO 次数太多；
• B 树 ：通过将二叉树改为多路平衡查找树，解决了树过高的问题；
• B+树 ：在 B 树的基础上
  • 将非叶节点改造为不存储数据的纯索引节点，适合放入内存中；
  • 进一步降低了树的高度，查询性能好；
  • 叶节点使用指针连接成链表，范围查询更加高效。
• 跳表：用于 Redis 的 zset，解决了链表查询效率低下的问题。

红黑树

什么是红黑树？

自平衡的二叉查找树，在进行插入和删除等可能会破坏树的平衡的操作时，需要重新自处理达到平衡状态。

1. 根和叶子节点是黑色的，插入的节点是红色的。
2. 叶子节点是空节点。
3. 每个红色节点必有黑色子节点。
4. 任意一结点到每个叶子结点的路径都包含数量相同的黑结点。

通过左旋、右旋和变色来实现自平衡：

左旋只影响旋转结点和其右子树的结构，把右子树的结点往左子树挪了。右旋只影响旋转结点和其左子树的结构，把左子树的结点往右子树挪了。

红黑树有什么好处？

• 红黑树是效率相对较高的当我们插入和删除数据相对频繁的时候
  • 查询性能略微逊色于AVL树
• 红黑树是自我平衡的所有操作的复杂度最多是O(logn)
• 不管怎么变化，只有红黑两个常数，任何不平衡都会在三次旋转之内解决

红黑树场景

TreeSet、TreeMap、HashMap

前缀树

Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。

请你实现 Trie 类：

• Trie() 初始化前缀树对象。
• void insert(String word) 向前缀树中插入字符串 word 。
• boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
• boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

JDK 源码

Queue 有哪些？

• BlockingQueue：提供了线程安全的队列访问方式
• PriorityQueue：优先级队列是一个可以排序的队列
• Deque：一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。

Set 有哪些结构？

• HashSet：哈希表，无序
• LinkedHashSet：底层数据结构是双向链表和哈希表，有序。由链表保证元素有序，由哈希表保证元素唯一。
• TreeSet：底层数据结构是红黑树，内部实现排序，也可以自定义排序规则。

🌟ArrayList 源码分析

1. 默认大小为 10（初始为 0，第一次添加变为 10）
2. 每次扩容 1.5 倍：0 -> 10 -> 15 -> 22 -> 33 -> 49 …
3. 数组 -> list：Arrays.asList() 是浅拷贝，修改数组会影响 list，因为指向同一个内存地址
4. list -> 数组：list.toArray() 是深拷贝，调用 Arrays.copyOf(data,size)
5. ArrayList 是动态数组，LinkedList 是双向链表，都不是线程安全的，除非 Collections.synchronizedList()

🌟HashMap 源码分析

put 方法：

1. table 为空或 ++size > *threshold(默认 12 = 数组长度（默认 16） 0.75) **时触发扩容机制 resize()
   1. 每次扩容 «1 （即*2）
   2. jdk8 之前头插法会导致死循环，jdk8 采用尾插法，避免扩容 resize() 迁移时的死循环
2. hash(key) 得到数组索引
   1. 扰动算法 (hash^hash»>16)异或操作使 hash 值更均匀，减少 hash 冲突
   2. hash&(n-1), n 为 2n ，等价于 hash%n ，位运算性能更好
3. key 存在则修改，不存在则添加

HashMap 1.7和1.8的区别？

JDK8 引入了红黑树：

• 链表 -> 红黑树：链表长度 >= 8 && 数组长度 >= 64 时
• 红黑树 -> 链表：resize（）扩容时，树节点<=6

ConcurrentHashMap 源码分析

锁分段技术？/ HashMap 1.7和1.8的区别？

原理：把数据分成很多段储存，每一段都对应一把锁，读取数据不加锁，写操作时能够将锁的粒度保持尽量的小，不用对整个ConcurrentHashMap加锁。

• JDK7：Segment + HashEntry 来保证线程安全 【不可扩容】
  • Segment extends ReentrantLock（继承可重入锁）
  • HashEntry则用于存储键值对数据
  • 一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组中的数据进行修改时，必须先获得它对应的Segment锁
• JDK8：CAS + synchronized 来保证线程安全，减少了锁的粒度
  • 数组+链表：类似 HashMap，长度>8 变为红黑树【处理哈希冲突】
  • transient volatile int count：volatile的语义可以保证写操作在读操作之前，也就保证了写操作对后续的读操作都是可见的，这样后面get的后续操作就可以拿到完整的元素内容
  • 对每个数组元素Node加锁，锁的粒度更细，并发度更高（只要 hash 不冲突就无并发问题）。

【get】为什么读操作不加锁？

因为Node的元素和指针是用volatile修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。此外，volatile修饰数组对get操作没有效果，但可以在扩容的时候对其他线程具有可见性。 volatile关键字：通过禁止指令重排，保证可见性、有序性。但不保证原子性。使用volatile关键字会强制将修改的值立即写入主存，并导致缓存变量的缓存行无效。 但是，当节点是红黑树的时候，如果树正在变色旋转并且错查询的值不是红黑树的头节点，会加读写锁。

【put】如何保证插入数据线程安全？

首先判空，非空情况下使用**扰动函数（高16位与低16位做异或，再和Hash_bit做与运算）**计算key的hash值，

1. 初始化数组采用懒汉式（第一次put时才初始化），线程安全通过一个volatile修饰的变量sizeCtl结合CAS来实现
2. 当寻址后的数组位置没有被占用时，直接基于主内存地址，通过CAS将创建的Node节点插入到当前位置
3. 当寻址到的位置正在进行扩容/迁移操作时（hash=MOVED=-1），执行helpTransfer来协助其他线程进行扩容/迁移
   1. 当 sizeCtl 为负值(-(1+n))时，表示有 n 个线程正在扩容
   2. 迁移：先计算当前线程需要转移对节点范围，再进行数据迁移
4. 当出现hash冲突时，对单个数组元素加 synchronized 锁，确保线程安全地将节点插入到链表或红黑树（链表长>8时调用treeifyBin(tab,i）转红黑树)中，若key存在替换旧值，若key不存在将kv追加到链表尾部

ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？

迭代器iterator是弱一致性的，因为在迭代过程中可以向map中添加元素；而HashMap是强一致性的。

HashSet

1. 底层基于 HashMap 的 keySet 来实现
2. 如果添加的值相同，保留最新的，因为HashMap 的底层逻辑是：存在则修改，不存在则添加。

基础

排序算法比较

稳定排序算法的优点在于可以保持相等元素的相对顺序，这在某些应用场景下非常重要，例如按照年龄和姓名对学生名单排序时，如果年龄相同，则应该按照姓名的字母顺序排序，这就需要使用稳定排序算法。

贪心算法 vs 动态规划？

站在全局角度来看，对于每个可选项，贪心算法是只保留一种决策（要么最优，要么非最优） ，动态规划保留了它的一个决策集，从中取最优。 当然，算法有优势就有劣势，贪心算法虽然适用条件苛刻，但复杂度低，当可选集太大时，动态规划这种穷举策略会比较耗时，而贪心算法虽然并不一定能找到最优解，但也可以找到一个接近最优解的解。 综上，贪心算法选的是当前最优解，而动态规划是通过子问题的最优解推出当前的最优解。