lukaliou123
commented
2 years ago 4. HashMap 和 Hashtable 的区别
- 线程安全：HashMap是非线程安全的，HashTable线程安全，因为内置了synchronized.(不过效率还是concurrenHashMap高)
- 效率：线程安全问题，HashMap效率高，HashTable基本被淘汰了
- 对null key 和 value的支持：HashMap可以存储null的key和value，但null key只能有一个，HashTable不支持
- 初始容量大小和每次扩充容量大小：1.Hashtable默认初始11.每次扩充比为原来的2n+1,HashMap初始为16，每次扩容会变成原来的2倍。2.如果给了初始值，HashMap会将其扩充为2的敏次方大小，也就是说HashMap总是使用2的幂作为大小
- 底层数据结构：JDK1.8以后，HashMap在解决哈希冲突时，当链表长度大于阈值（默认为8），将链表转为红黑树以减少搜索时间，HashTable没有这种机制
HashMap为什么每次扩容都是扩大两倍，
这是因为它利用了位运算来计算哈希值。扩容两倍后，旧的元素在新数组中的位置要么保持不变，要么是在原位置基础上加上旧数组长度。这样，旧元素的位置只需要计算一次哈希值就能得到，这样能够提高扩容的效率
5. 什么是红黑树。
首先，红黑树是一种自平衡的二叉搜索树，每个节点包含两个子节点和一个颜色属性（可以是红色或黑色）。这种数据结构主要被应用于关联数组和Java等语言的内置库，例如TreeMap和TreeSet。
红黑树的基本结构特性如下：
1.每个节点或是红色，或是黑色。 2.根节点是黑色。 3.每个叶节点（NIL或空节点）是黑色。 4.若节点是红色，则它的子节点必须是黑色（也就是不能有两个连续的红色节点）。 5.从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点，即黑色平衡(重要！）
对红黑树的常见操作（如插入、删除和查找）的时间复杂度都是O(log n)，因为树的高度始终是对数级别的。这是红黑树与普通二叉搜索树最主要的区别，二叉搜索树在最坏情况下会退化为链表，时间复杂度变为O(n)。
为何选择红黑树？ 我们选择红黑树而不是其他树，如AVL树，主要是因为红黑树在实际应用中更加高效。相比于AVL树，红黑树的平衡条件更宽松，因此在进行插入和删除操作时，需要进行的旋转次数较少，从而使得在实际应用中的效率更高。此外，红黑树的结构相对简单，易于理解和实现。 https://zhuanlan.zhihu.com/p/143585797
为什么一个节点到其每个叶子结点的黑色节点数量一样（黑色平衡）是优点？
这是因为它能保证最长的可能路径不会超过最短的可能路径的两倍长度。换句话说，红黑树是近似平衡的，这种平衡性质保证了红黑树的查找、插入、删除操作的时间复杂度为O(log n)，避免了最坏的情况（即退化成链表）。
补充：Hashmap和treeMap
1.实现：HashMap基于哈希表（数组+链表+红黑树）实现，而TreeMap基于红黑树实现。
2.排序：HashMap不保证任何特定的元素顺序，而TreeMap则根据key的自然顺序或者指定的Comparator进行排序。
3.性能：HashMap在大多数操作（get和put等）中提供常数时间的性能，因为它是基于哈希表的。但是，TreeMap提供log(n)时间的性能，因为它是基于树的。
线程安全：这两种都是非线程安全的，如果需要线程安全的话，可以考虑使用Collections.synchronizedMap()方法或者ConcurrentHashMap。
拉链法：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可
前置顶：容器的关系
Java 集合， 也叫作容器，主要是由两大接口派生而来： 一个是 Collection接口，主要用于存放单一元素； 另一个是 Map 接口，主要用于存放键值对。 对于Collection 接口，下面又有三个主要的子接口：List、Set 和 Queue。
1. 说说 List, Set, Queue, Map 四者的区别？
List(对付顺序的好帮手)：存储的元素是有序的、可重复的 Set(注重独一无二的性质)：存储的元素是无序的、不可重复的 Queue（实现排队功能的叫号机）：按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的 Map(用key来搜索的专家)：使用键值对（key-value）存储，类似于数学上的函数，“x”代表key, “y”代表value，key是无序的，不可重复的，value是无序的，可重复的，每个键最多映射到一个值。
2. Arraylist 与 LinkedList 区别?
2.1.ArrayList 插入和删除元素的时间复杂度？
插入和删除尾部都是O（1), 但是操作中间的或头部的节点会导致数组移动，要变为O（n)
2.2.LinkedList 插入和删除元素的时间复杂度？
头尾都是O（1），但是中间的因为涉及到搜索所以O（n)
2.补充：使用场景？
1.使用数组的场合：如果你需要快速访问数据或者知道数据的索引，那么数组是一个很好的选择。因为数组提供了 O(1) 的随机访问性能。比如你正在处理一些数学问题，或者你需要将数据存储到硬盘上，然后再次读取它们，数组可能是一个更好的选择。
2.使用链表的场合：如果你经常需要在列表的中间位置插入或删除元素，那么链表可能是一个更好的选择。链表的插入和删除操作都是 O(1) 的时间复杂度，而数组的这些操作则需要 O(n) 的时间复杂度。比如你在实现一个缓存策略，例如 LRU (Least Recently Used)，这样的策略经常需要删除中间的元素，并且插入新的元素，这时候使用链表会很方便。
3. ArrayList 与 Vector 区别呢?为什么要用Arraylist取代Vector呢？
3.补充：为什么现在vector少了？
首先，Vector的所有公共方法都是同步的，这就意味着如果你在一个线程中访问一个Vector，而在另一个线程中也尝试访问同一个Vector，那么后一个线程就需要等待第一个线程完成操作。这会导致性能问题，尤其是在多线程的环境中。
其次，现在我们有了更多的选择。如果你需要一个线程安全的集合，Java的并发库提供了许多更好的选择，比如CopyOnWriteArrayList等。
补充：CopyOnWriteArrayList
至于CopyOnWriteArrayList，你的记忆没错，它确实是通过克隆数组实现线程安全的。每当我们对CopyOnWriteArrayList进行修改操作（如add或者set等）的时候，它都会创建一个新的数组，并将原数组的内容复制到新数组中，然后再进行修改。这种方法叫做“写时复制”。
这种方式的优点是对CopyOnWriteArrayList的读操作可以完全不需要加锁，因为它们总是操作的是不会被修改的数组。这对于读操作远远多于写操作的应用场景非常有用，比如在事件监听器的列表中。
但是，它的缺点也是很明显的。因为每次修改都会复制整个数组，所以如果数组非常大，或者修改操作非常频繁，那么这将导致大量的内存开销和性能开销。
所以，CopyOnWriteArrayList是一种特殊的工具，只有在特定的场景下，比如读多写少的情况，才更适合使用。
补充：链表的升级版--跳表
跳表是通过添加多级索引的方式来提高链表的查找效率的。你可以把跳表理解为一个对链表的“升级版”。在原有的链表结构之上，跳表增加了多级索引，每一级索引都是原链表的一个子集，每一级的索引节点数都比上一级的少。这样的话，当我们进行查找操作时，可以先在较高级别的索引中进行，快速定位到一个区间，然后再逐级降低，精确查找，大大减少了查找的步骤，提高了效率。
具体实现上，我们可以设定链表的每个节点都可能成为上一级索引的节点，规定比如每2个或者3个节点抽取一个到上一级，如此类推，形成多级索引。跳表的查找、插入、删除等操作的时间复杂度都可以达到O(logn)，所以其效率是相当高的。
Redis中就使用了跳表来实现有序集合（zset)数据类型，这样即保证了有序性，又可以快速地进行查找和插入操作。
例子：
在这个跳表中，我们依然保留了原来的链表，这是最底层(level0)。然后，我们在原链表的基础上，建立了一个新的层次 (level1)，这个层次中只包含部分数字。然后，我们又在level1的基础上，建立了level2。每一层的元素都是其下一层的子集。
这样，当我们查找一个数字时，例如我们仍然要查找8。首先我们在level2层开始查找。我们发现7是最接近8且小于8的数字，于是我们在level2层向后查找，但发现后面的数字比8大，所以我们退回到level1层，从7开始查找，又发现10比8大，所以再退回到level0层，从7开始查找，最后找到了8。