【声明】：https://www.nowcoder.com/feed/main/detail/a9721c8775dd44c29f90389107c31235

为了方便大家构建逻辑模型，文末附思维导图

第一章-目录：https://blog.nowcoder.net/n/cfd45372b1d245dc836c06aa5ef136e3

正文：

提纲：

基础八股知识🔥

  • CollectionList——有序可重复列表Set——不可重复列表Queue / DequeBlockQueue
  • MapHashMapConcrrentHashMapTreeMap、LinkedHashMap、HashTable
  • Iterator迭代器

面试八股真题🎈

  • 1、简述ArrayList和LinkedList的区别
  • 2、HashMap和HashTable的区别
  • 3、Collection包结构，与Collections的区别
  • 4、有没有可能两个不相等的对象有相同的hashcode
  • 5、说说List,Set,Map三者的区别？
  • 6、HashMap 中的 key 我们可以使用任何类作为 key 吗？
  • 7、HashMap 的长度为什么是 2 的 N 次方呢？
  • 8、HashMap 与 ConcurrentHashMap 的异同
  • 9、红黑树有哪几个特征？
  • 10、equals与==的区别
  • 11、HashMap树化条件？退化条件？

一、基础八股知识点

方便你看的思维导图：链接

1. Collection

1.1 List——有序可重复列表

  • ArraylistArrayList是Java集合框架中的一个重要的类，它继承于AbstractList，实现了List接口，是一个长度可变的集合，提供了增删改查的功能。集合中允许null的存在。ArrayList类还是实现了① 底层是用数组实现的，重要的成员有 元素数组、数组中元素数size、 modCount 修改次数② 进行 add 添加时，若没有指定添加位置，就会根据 size 确定添加的新元素在数组中的下标进行添加，若 size >= 数组长度，则需要扩容③ 在进行扩容时，会将 modCount++，并且会将原数组中的元素，拷贝至新数组中，新数组的大小是原数组的 1.5 倍，默认的初始容量是 0，且在第一次添加元素时，设置数组大小为 10④ 若指定 i 为添加元素的位置，会调用 System.ArrayCopy 方法对 i 下标以后的元素进行拷贝，拷贝完成后再把添加的元素放在 i 位置⑤ 调用 get 方法时，由于ArrayList 底层基于数组，因此实现了一个 RandomAccess 标识接口，表示按下标读取数据速度很快，主要是由于数组在内存中是连续存储，可以通过第一个元素的存储地址和偏移量offset直接计算得到访问的元素的存储地址⑥ 若 contains 方法是通过元素的值进行查找，则需要遍历数组
  • LinkedListLinkedList同时实现了List接口和Deque对口，也就是收它既可以看作一个顺序容器，又可以看作一个队列（Queue），同时又可以看作一个栈（stack）① LinkedList 是基于链表存储的，链表中节点 Node 重要包含存储的元素的引用 E，指向前驱节点指针prev 和指向后继节点的指针 next，LinkedList 中重要成员主要有 size/头节点 first/尾节点 last② LinkedList 由于 Node 在内存中是分散存储的，因此没有对 size 限制，在执行 add 方法时，默认添加在链表的尾部③ 若指定添加元素在链表中的位置，LinkedList 需要调用 node 方法，传入参数 Index 找到对应的节点，在查找对应的节点时，若 Index < size / 2，从头节点向后遍历，若 Index > size / 2，从尾节点向前遍历，因此即使添加元素只需要改变节点的指针，但查找添加的位置的耗时仍然不小，开销不比 ArrayList 少④ 调用 get 方法时，若按下标查找，也需要进行同样的遍历，性能比 ArrayList 差很多，按 contains 进行查找时，也需要进行遍历，与 ArrayList 相比半斤八两⑤ 链表节点除了元素值，还需要维护两个指针，导致 LinkedList 存储的内存开销远大于 ArrayList
  • Vector & Stack① Vector 也是基于数组进行存储，其原理与 ArrayList 类似，区别在于，Vector 中会维护一个 CapacityIncrement变量，每一次进行扩容时，只增加一个 CapacityIncrement 变量的大小，若没有指定 CapacityInc，默认为 0，且在扩容时，若 CapacityInc 为 0，则将数组大小翻倍；② Vector 中的所有增删改查方法，包括 get 方法，都通过在方法上加 Sychronized 锁方式锁住 Vector 对象，实现线程安全，性能较差。

1.2 Set——不可重复列表

  • HashSetHashSet类，是存在于java.util包中的类 。同时也被称为集合，该容器中只能存储不重复的对象。内部有一个成员变量的 HashMap，实际上就是使用的 HashMap 的方法
  • TreeSetTreeSet 是一个有序的集合，它的作用是提供有序的Set集合。它继承于AbstractSet抽象类，实现了NavigableSet<E>, Cloneable, java.io.Serializable接口。内部有一个成员变量的 TreeMap，底层就是 TreeMap
  • LinkedHashSet底层调用的 HashSet 的方法，LinkedHashSet是 HashSet的子类LinkedHashSet根据元素的hashCode值来决定元素的存储位置，但它同时使用双向链表维护元素的次序，这使得元素看起来是以插入顺序保存的。 LinkedHashSet插入性能略低于 HashSet，但在迭代访问Set里的全部元素时有很好的性能。LinkedHashSet不允许集合元素重复。

1.3 Queue / Dequeue

  • LinkedList 实现 Queue 和 Deque不论是Queue 还是 Deque，每一种操作对应的方法都以两种形式存在：一种在操作失败时抛出异常，另一种返回特殊值（ null或false ，具体取决于操作）。LinkedList 中使用 first 和 last 两个节点的指针用来标记链表的头/尾节点，根据源码，pop应该返回first节点，pop和poll对返回节点为空处理不同，poll直接返回null，pop抛出异常QueueDeque
  • 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 使用场景：

2 MAP

2.1 HashMap

  • 重要成员变量① 负载因子：默认为 0.75，表示 HashMap 存储的元素数到达 HashMap 散列数组长度的 0.75 时就进行扩容负载因子越大，散列数组的内存利用率越高，但哈希冲突概率也越高，查询效率相对降低；负载因子越小，散列数组的内存利用率越低，但哈希冲突概率越低，查询效率相对较高② 散列数组：HashMap 通过分离链表法解决哈希冲突的问题，在散列数组中存储的就是链表中的一个个头节点③ K-V 键值对：K-V 键值对以 Node 节点的方式进行存储，Node 继承自 Map.Entry，包含 Next 指针，Key，Value 和 hash④ threshold 门限，就是 负载因子 * 数组容量⑤ size：HashMap 中当前存储的节点数
  • put方法流程：① 再哈希：首先通过key获取到hashCode值，再对hashCode值右移16位，最后再与原hashCode值做异或运算。#目的：在对散列数组长度取余时，高位通常不参与运算，再哈希让高位参与哈希运算，让低位尽量不同，使哈希分布更均匀② 检查散列数组是否为空，若为空，初始化散列数组，数组容量将会初始化为16③ 若 Key 的 HashCode 对应的散列数组位置上节点为空，则直接将新节点加入④ 若不为空，比较链表的头节点 Key 与 put Key 是否相等，先比较 hashcode，再比较（== || equals），若相等，进行更新，若不相等，顺着链表按同样的逻辑进行比较⑤ 若是 1.8 的HashMap，会先判断链表的头节点是否是 TreeNode，若是，则按照红黑树的逻辑进行插入⑥ 1.7 的 HashMap 中，若遍历完链表仍未找到 Key 相同的节点，则将新节点加入到链表头，会造成并发扩容的死链问题，1.8 中，将头插法改为了尾插法，解决了死链问题，但并发环境下的其他基本问题，如更新丢失等，仍然没有解决# 1.8 以前一直采用头插法的是由于计算机的局部性原理，主要是时间局部性原理，即一个最近被访问过的对象，很有可能很快会被再访问到，基于该假设，在头节点插入，可以有效的提高查询的效率，在发生并发问题时，完全可以使用 concurrent map来解决# HashMap的线程不安全带来了循环链表问题 可以使用Collections中的SynchronizedMap，concurrentHashMap，HashTable解决，推荐使用ConcurrentHashMap⑦ 若添加后 size >= threshold，就会进行扩容
  • 扩容流程① 首先 HashMap 的初始容量是 16，并且每次对原数组长度 * 2 进行扩容，当 size > threshold 时就会进行扩容# HashMap 每次 * 2 的原因：1）2 的幂次可以用 & 的方式进行取余运算，效率更高；2）在扩容移动链表节点时，节点在新数组中的位置只可能是原位置 i 或 i + oldCap 旧数组长度，扩容时效率更高② 创建新的散列数组，并将旧的散列数组中的链表的头节点拷贝至新数组中，在移动时，节点的 hash 与 oldCap进行 & 运算，若结果为 0，表示在新数组中位置不变，若不为 0，表示在新数组中位置为 i + oldCap③ 在移动节点时，会使用一个 loHead/loTail 和 hiHead/hiTail 分别指向新数组中位置 i 和 i + oldCap 的链表的头尾节点，用一个 next 指针指向当前正在移动节点的下一个节点，在 1.8 中，由于使用尾插法，每一次移动节点都会添加至 loTail/hiTail之后，不会发生死链问题，而在 1.7 中，由于使用头插法，每一次移动节点都会添加至 head 之前，会发生扩容死链问题④ 1.7 扩容死链问题：t1 线程正在移动 A 节点，next 节点指向 A 节点的下一个节点 B，即 A -> B，此时 t2 线程完成了 A 和 B 的移动，此时 B.next = A，在 t1 移动 A 到新数组中后，当前正在移动节点 e 指向 B，next 指向 B.next = A，此时就形成了链表中的环，最终导致程序崩溃
  • 红黑树① 与AVL树比较增删性能，红黑树较好； AVL 树通过节点的左右子树高度差是否大于 1 判断是否平衡，若不平衡，需要通过单/双旋转恢复平衡，而红黑树主要根据节点颜色和节点到子孙节点路径上黑节点数量判断平衡，可以通过改变节点颜色或者旋转恢复平衡，开销较小查询性能，AVL 树较好；AVL 树的最大高度为 1.44 * log(N + 2)，一般情况只比 log(N) 稍大，红黑树由于平衡判断更加宽松，由着色法则得到的最大高度为 2 * log(N + 1)，因此性能会稍微差于 AVL 树内存空间消耗，红黑树稍大；为什么不用跳表； ① 跳表的实现更加灵活简单，并且在范围查找上非常方便，Redis 中 ZSet 就使用跳表 + 散列的结构 ② 红黑树在空间复杂度上更胜一筹，通常发生了红黑树化的情况，都是数据量非常非常大时，此时红黑树空间占用小的优点将更加明显，并且 HashMap 的元素本身是无序的，即用不到跳表范围查找的优势② 特点每个节点不是黑色就是红色，根节点是黑色红色节点的子节点必须是黑色从一个节点到每一个子孙节点的路径上的黑色节点数必须相同③ HashMap 中什么时候树化/树退化当链表长度达到 8 时进行树化；在 HashMap 源码注解中有解释为什么是 8，大概意思是，红黑树的节点大小大约是正常节点大小的两倍，并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记，在理想情况下，使用 0.75 作为负载因子，采用随机哈希算法，树化阈值与树化概率遵循泊松分布，选择 8 的概率是千万分之 6，7 的概率约是十万分之 1当扩容后链表长度小于等于 6 进行树的退化；红黑树的节点大小大约是正常节点大小的两倍，并且当节点数较少时链表与红黑树的查找效率差距可以忽略不记，并且在插入和删除时维护红黑树的平衡性需要额外的开销

2.2 ConcurrentHashMap

  • 1.7之前① 通过分段锁 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④ 1.8 的 ConcurrentHashMap 摒弃了 Segment，采用 CAS 和类似于分段锁的方式保证线程安全；⑤ 大体结构与 HashMap 一样，在 put 操作时，若 Node 数组对应下标处为空，使用 CAS 的方式不加锁添加节点，若数组中当前位置链表头节点不为空，则对链表头节点加锁，在 Sychronized 同步代码块中执行与 HashMap 同样的逻辑；⑥ ConcurrentHashMap 在扩容时的移动原数组节点到新数组的操作，可以由多个线程并发完成，从而大大提高效率，在进行移动时，会将当前线程正在移动的头节点包装为一个 ForwardNode，用来标识当前位置正在移动，当其他线程遍历到数组中的 ForwardNode节点时，就会忽略并继续遍历，从而保证线程安全，并且在扩容时，仍然可以执行增删改查操作，这些操作通过头节点的 hash 判断是否是一个 ForwardNode 节点，若是，则调用 helpTransfer 方法，并发的帮助完成扩容动作，完成后再回到循环中执行 put；⑦ get 方法也是通过 Unsafe 的 getObjectVolatile 进行读取，不加锁

2.3 TreeMap

  • 底层是红黑树，不展开讲解

2.4 LinkedHashMap

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

2.5 HashTable

  • •    使用 Sychronized 锁住方法来保证线程安全，并且默认初始容量为 11，每一次扩容为 oldCap * 2 + 1，键和值都不允许为null，效率低

3. Iterator迭代器

  • ① 用来进行集合的遍历，不同的集合有不同的实现，例如 ArrayList 通过一个 cursor 指向下一个遍历的元素的下标，用一个 lastRet 表示上一个遍历的元素的下标；
  • ② Iterator 接口中主要包含三个基本方法，hasNext 判断是否还有下一个元素，next 表示遍历获取下一个元素，remove 表示删除元素；
  • ③ 常见的三种遍历方式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 变量指向当前的数组，在旧的数组上进行遍历

二、面试八股真题🎈🎈🎈

1、简述ArrayList和LinkedList的区别

① Array（数组）是基于索引(index)的数据结构，它使用索引在数组中搜索和读取数据是很快的。

Array获取数据的时间复杂度是O(1),但是要删除数据却是开销很大，因为这需要重排数组中的所有数据, (因为删除数据以后, 需要把后面所有的数据前移)

缺点: 数组初始化必须指定初始化的长度, 否则报错

例如

int[] a = new int[4]; //推荐使用int[] 这种方式进行初始化

int c[] = {12,34,56,78}; //长度：4，索引范围：[0,3]

② List—是一个有序的集合，可以包含重复的元素，提供了按索引访问的方式，它继承Collection。List有两个重要的实现类：ArrayList 和 LinkedList

  • ArrayList: 可以看作是能够自动增长容量的数组ArrayList的toArray方法返回一个数组ArrayList的asList方法返回一个列表ArrayList底层的实现是Array, 数组扩容实现
  • LinkedList是一个双链表,在添加和删除元素时具有比ArrayList更好的性能.但在get与set方面弱于 ArrayList.当然,这些对比都是指数据量很大或者操作很频繁。

③ 区别

  • ArrayList优点：ArrayList 是实现了基于动态数组的数据结构，因为地址连续，一旦数据存储好了，查询 操作效率会比较高（在内存里是连着放的）。缺点：因为地址连续，ArrayList 要移动数据，所以插入和删除操作效率比较低。
  • LinkedList优点：LinkedList 基于链表的数据结构，地址是任意的，所以在开辟内存空间的时候不需要等 一个连续的地址。对于新增和删除操作，LinkedList 比较占优势。LinkedList 适用于要头尾操 作或插入指定位置的场景。缺点：因为 LinkedList 要移动指针，所以查询操作性能比较低。

④ 适用场景分析：

  • 当需要对数据进行对随机访问的时候，选用 ArrayList。
  • 当需要对数据进行多次增加删除修改时，采用 LinkedList。

2、HashMap和HashTable的区别

① 两者父类不同

  • HashMap是继承自AbstractMap类，
  • Hashtable是继承自Dictionary类。
  • 不过它们都实现了同时 实现了map、Cloneable（可复制）、Serializable（可序列化）这三个接口。

② 对外提供的接口不同

  • Hashtable比HashMap多提供了elments() 和contains() 两个方法。
  • elments() 方法继承自ashtable的父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。
  • contains()方法判断该Hashtable是否包含传入的value。它的作用与containsValue()一致。事实上，contansValue() 就只是调用了一下contains() 方法。

③ 对null的支持不同

  • Hashtable：key和value都不能为null。
  • HashMap：key可以为null，但是这样的key只能有一个，因为必须保证key的唯一性；可以有多个key值对应的value为null。

④ 安全性不同

  • HashMap是线程不安全的，在多线程并发的环境下，可能会产生死锁等问题，因此需要开发人员自 己处理多线程的安全问题。
  • Hashtable是线程安全的，它的每个方法上都有synchronized 关键字，因此可直接用于多线程中。
  • 虽然HashMap是线程不安全的，但是它的效率远远高于Hashtable，这样设计是合理的，因为大部 分的使用场景都是单线程。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。
  • ConcurrentHashMap虽然也是线程安全的，但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁，并不对整个数据进行锁定。

⑤ 初始容量大小和每次扩充容量大小不同

⑥ 计算hash值的方法不同

3、Collection包结构，与Collections的区别

  • Collection是集合类的上级接口，子接口有 Set、List、LinkedList、ArrayList、Vector、Stack、 Set；
  • Collections是集合类的一个帮助类， 它包含有各种有关集合操作的静态多态方法，用于实现对各种 集合的搜索、排序、线程安全化等操作。此类不能实例化，就像一个工具类，服务于Java的 Collection框架。

4、有没有可能两个不相等的对象有相同的hashcode

  • 有可能
  • 在产生hash冲突时,两个不相等的对象就会有相同的 hashcode 值.当hash冲突产生时,一般 有以下几种方式来处理：拉链法：每个哈希表节点都有一个next指针,多个哈希表节点可以用next指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表进行存储。开放定址法：一旦发生了冲突,就去寻找下一个空的散列地址,只要散列表足够大,空的散列地址总 能找到,并将记录存入 List iniData = new ArrayList<>()再哈希：又叫双哈希法,有多个不同的Hash函数.当发生冲突时,使用第二个,第三个….等哈希函数 计算地址,直到无冲突。

5、说说List,Set,Map三者的区别？

  • List(对付顺序的好帮手)： List接口存储一组不唯一（可以有多个元素引用相同的对象），有序 的对象
  • Set(注重独一无二的性质)： 不允许重复的集合。不会有多个元素引用相同的对象。
  • Map(用Key来搜索的专家)： 使用键值对存储。Map会维护与Key有关联的值。两个Key可以引 用相同的对象，但Key不能重复，典型的Key是String类型，但也可以是任何对象。

6、HashMap 中的 key 我们可以使用任何类作为 key 吗？

  • 平时可能大家使用的最多的就是使用 String 作为 HashMap 的 key，但是现在我们想使用某个自定 义类作为 HashMap 的 key，那就需要注意以下几点：如果类重写了 equals 方法，它也应该重写 hashCode 方法。类的所有实例需要遵循与 equals 和 hashCode 相关的规则。如果一个类没有使用 equals，你不应该在 hashCode 中使用它。咱们自定义 key 类的最佳实践是使之为不可变的，这样，hashCode 值可以被缓存起来，拥有更好的性能。不可变的类也可以确保 hashCode 和 equals 在未来不会改变，这样就会解决与 可变相关的问题了。

7、HashMap 的长度为什么是 2 的 N 次方呢？

  • 为了能让 HashMap 存数据和取数据的效率高，尽可能地减少 hash 值的碰撞，也就是说尽量把数据能均匀的分配，每个链表或者红黑树长度尽量相等。我们首先可能会想到 % 取模的操作来实现
  • 取余（%）操作中如果除数是 2 的幂次，则等价于与其除数减一的与（&）操作（也就是说 hash % length == hash &(length - 1) 的前提是 length 是 2 的 n 次方）。并且，采用二进 制位操作 & ，相对于 % 能够提高运算效率。

8、HashMap 与 ConcurrentHashMap 的异同

  • ① 都是 key-value 形式的存储数据；
  • ② HashMap 是线程不安全的，ConcurrentHashMap 是 JUC 下的线程安全的；
  • ③ HashMap 底层数据结构是数组 + 链表（JDK 1.8 之前）。JDK 1.8 之后是数组 + 链表 + 红黑 树。当链表中元素个数达到 8 的时候，链表的查询速度不如红黑树快，链表会转为红黑树，红 黑树查询速度快；
  • ④ HashMap 初始数组大小为 16（默认），当出现扩容的时候，以 0.75 * 数组大小的方式进行扩 容；
  • ⑤ ConcurrentHashMap 在 JDK 1.8 之前是采用分段锁来现实的 Segment + HashEntry， Segment 数组大小默认是 16，2 的 n 次方；JDK 1.8 之后，采用 Node + CAS + Synchronized 来保证并发安全进行实现。

9、红黑树有哪几个特征？

  • 每个节点都是黑色或者红色
  • 根节点是黑色
  • 每个叶子节点都是黑色（指向空的叶子节点）
  • 如果一个叶子节点是红色，那么其子节点必须都是黑色的
  • 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

10、equals与==的区别

  • equals：equals用来比较的是两个对象的内容是否相等，由于所有的类都是继承自java.lang.Object类的，所以适用于所有对象，如果没有对该方法进行覆盖的话，调用的仍然是Object类中的方法，而Object中的equals方法返回的却是==的判断。

  • == ：== 比较的是变量(栈)内存中存放的对象的(堆)内存地址，用来判断两个对象的地址是否相同，即是否是指相同一个对象。比较的是真正意义上的指针操作。1、比较的是操作符两端的操作数是否是同一个对象。 2、两边的操作数必须是同一类型的（可以是父子类之间）才能编译通过。 3、比较的是地址，如果是具体的阿拉伯数字的比较，值相等则为true。

  • 含义不同：==是一个比较运算符，基本数据类型比较的是值，引用数据类型比较的是地址值。（比较地址值即是指是否为同一个对象的引用）equals()是一个方法，只能比较引用数据类型。重写前比较的是地址值，重写后比一般是比较对象的属性。引用不同：值类型（int,char,long,bolean等）都是用=判断相等性。对象引用的话，=判断引用所指的对象是否是同一个。equals是Object的成员函数，有些类会覆盖（overide）这个方法，用于判断对象的等价性。方法不同：String里的方法，如果==号比较不相等，还会进行一下值的比较。所以equals方法具体的作用要看当前的那个类是如何实现重写父类中该方法的。如果没有重写该方法，那么他和==号等价。

11、HashMap树化条件？退化条件？

  • 树化条件：
  • 退化条件：

相关阅读：

  • 【Java八股—目录导读】：点击跳转

  • 【简历制作】：点击转跳
  • 【C++八股】：点击转跳