jdk1.8 数组 + 链表 + 红黑树

jdk1.7 数组 + 链表

查找的效率：红黑树从根到叶子的最长的路径不多于最短的可能路径的两倍长

如果是链表——O(n)

升级为红黑树——O(log(n))

//桶中元素超过8 会使用红黑树
static final int TREEIFY_THRESHOLD = 8; //treeify_threshold

//可以对桶进行树化的最小表容量（当数组的长度超过64 就会使用红黑树）
static final int MIN_TREEIFY_CAPACITY = 64; //min_treeify_capacity

链表升级到红黑树的条件：
链表长度为8个
数组长度为64个

数组扩容的条件：（会重新计算所有的元素的hash）
链表长度为>8个
数组长度为<64个

---

扩容 重新分配

扩容，如何将元素重新分配到数组里面的？（数组大小都会扩大到原来的两倍）

• jdk1.7，数组长度 ×2 ，会取模新数组的长度 rehash

• jdk1.8，数组长度 ×2 ，进行高低位运算——将之前元素的hash值 通过 运算符&（与）老数组的长度

  • (e.hash & oldCap) == 0

  • 如果 != 0 代表当前元素是一个高位元素，会将原来的下标12+扩容出来的大小16，放在你的高位28位置

  • 如果 = 0 会任务这个元素是个低位元素，会保留原来的下标位置，依然会放在原位置

1.8肯定没有1.7直接rehash分布的更分散一点，1.8有可能会出现当前元素均为高位or均为低位的情况

位置计算原理（高位or低位）

1. 位置计算原理

• 在HashMap中，元素的位置是通过**index = (n - 1) & hash**计算的，其中n是数组长度，hash是键的哈希值。

• 扩容后，新数组的长度是2 * n，因此新位置的计算公式变为：

  newIndex = (2 * n - 1) & hash;

• 由于n是2的幂次方，(2 * n - 1)的二进制表示比(n - 1)多了一个1。例如：

  • 如果n = 16，则n - 1 = 00001111。
  • 如果newCapacity = 32，则2 * n - 1 = 00011111。

---

2. 判断是否需要移动

• 通过(e.hash & oldCapacity) == 0可以判断元素是否需要移动：
  • 如果结果为0，说明元素的哈希值在新增的高位上为0，因此元素在新数组中的位置与旧数组中的位置相同（newIndex = oldIndex）。
  • 如果结果不为0，说明元素的哈希值在新增的高位上为1，因此元素在新数组中的位置为**oldIndex + oldCapacity**。

---

3. 示例

& 同为1时才是1

假设当前容量n = 16，扩容后容量newCapacity = 32。

• 元素1：hash = 5（二进制00000101）
  • 旧位置：(16 - 1) & 5 = 00001111 & 00000101 = 00000101（即5）。
  • 新位置：(32 - 1) & 5 = 00011111 & 00000101 = 00000101（即5）。
  • 判断：hash & 老长度 5 & 16 = 00000101 & 00010000 = 0，因此元素不需要移动。
• 元素2：hash = 21（二进制00010101）
  • 旧位置：(16 - 1) & 21 = 00001111 & 00010101 = 00000101（即5）。
  • 新位置：(32 - 1) & 21 = 00011111 & 00010101 = 00010101（即21）。
  • 判断：hash & 老长度 21 & 16 = 00010101 & 00010000 = 00010000（即16），因此元素需要移动到oldIndex + oldCapacity = 5 + 16 = 21。

---

jdk1.8 put 描述

在jdk1.8 put一个新元素时，会根据元素的key进行一个hash运算，以及取模定位到你数组的下标位置，如果出现了hash冲突，它会通过链表进行连接，
如果当前链表达到了8个，后面会走两个条件：
一个是升级为红黑树，
另一个是进行扩容，
到底是升级为红黑树还是扩容，是根据数组的长度决定的，如果你的数组的长度<64，会扩容，>64会升级（如果红黑树的节点数小于某个阈值（默认是6），红黑树会退化为链表。）。

扩容的过程呢，会将老数组的长度×2，将链表中的元素进行低位和高位运算，重新分配到数组中去，这个过程肯定是非常消耗性能的

如果你的HashMap数据量很大，我们通常会通过new HashMap的时候指定初始数组的大小，以及数组扩容的加载因子，通过扩容可以提升内存的利用率，随着你的元素增多，动态的增加你的内存的使用

—————-面试必问—————-

关于HashMap,你知道多少？你知道HashMap的工作原理吗？

包含了非常多数据结构的概念

1. 该问题很有深度
2. 能答出多少决定岗位和薪资
3. 问题的方式多种多样,怎么办？好慌

1.你用过HashMap吗?什么是HashMap?你为什么用到它?

1. 你用过HashMap吗？
   是的，我在多个项目中使用过HashMap。

2. 什么是HashMap？
   HashMap是Java集合框架中的一种数据结构，基于哈希表实现。它存储键值对（key-value pairs），允许通过键（key）快速查找对应的值（value）。HashMap的特点包括：

   • 键唯一性：每个键只能对应一个值，重复的键会覆盖旧值。
   • 无序性：HashMap不保证元素的顺序。
   • 允许null键和null值：HashMap允许一个null键和多个null值。
   • 非线程安全：HashMap不是线程安全的，多线程环境下需要额外同步。

3. 你为什么用到它？
   我使用HashMap的主要原因是它的高效查找和插入操作。在以下场景中，HashMap非常有用：

   • 快速查找：当需要通过键快速查找值时，HashMap的平均时间复杂度为O(1)。
   • 缓存数据：HashMap常用于缓存数据，避免重复计算或查询。
   • 统计频率：在统计元素出现频率时，HashMap可以方便地存储元素及其对应的计数。
   • 映射关系：当需要维护键值对的映射关系时，HashMap是一个简单且高效的选择。

例如，在一个项目中，我需要统计一段文本中每个单词出现的频率，使用HashMap可以轻松实现这一功能：

Map<String, Integer> wordCountMap = new HashMap<>();
for (String word : words) {
    wordCountMap.put(word, wordCountMap.getOrDefault(word, 0) + 1);
}

总之，HashMap因其高效的查找和插入操作，成为处理键值对数据的常用工具。

2.你知道HashMap的工作原理吗?

回答：

HashMap是Java中最常用的数据结构之一，它基于哈希表实现，用于存储键值对（key-value pairs）。以下是HashMap的工作原理：

---

1. 核心数据结构

• 数组 + 链表/红黑树：
  HashMap内部维护了一个数组（称为桶数组），每个数组元素是一个链表或红黑树的头节点。链表或红黑树用于解决哈希冲突。
• Node类：
  每个键值对被封装为一个Node对象，包含key、value、hash值和指向下一个节点的指针（next）。

---

2. 存储过程（put操作）

当调用put(key, value)方法时，HashMap会执行以下步骤：

1. 计算哈希值：
   通过key.hashCode()计算键的哈希值，然后通过扰动函数（JDK 1.8中的hash()方法）进一步优化哈希值，以减少哈希冲突。
2. 计算数组索引：
   通过(n - 1) & hash计算键值对在数组中的存储位置（n是数组长度）。
3. 插入或更新：
   • 如果该位置为空，直接插入新节点。
   • 如果该位置不为空，遍历链表或红黑树：
     • 如果找到相同的key（通过equals()方法判断），则更新对应的value。
     • 如果没有找到相同的key，则将新节点插入链表或红黑树。
4. 扩容检查：
   如果元素数量超过容量 * 负载因子，则触发扩容。

---

3. 查找过程（get操作）

当调用get(key)方法时，HashMap会执行以下步骤：

1. 计算哈希值：
   通过key.hashCode()和扰动函数计算哈希值。
2. 计算数组索引：
   通过(n - 1) & hash定位到数组中的位置。
3. 遍历链表或红黑树：
   • 如果该位置为空，返回null。
   • 如果该位置不为空，遍历链表或红黑树，通过equals()方法比较key，找到匹配的节点并返回其value。

---

4. 哈希冲突解决

• 链表：
  当多个键值对被映射到同一个数组位置时，它们会以链表的形式存储。
• 红黑树：
  在JDK 1.8中，当链表长度超过阈值（默认是8）时，链表会转换为红黑树，以提高查找效率（从O(n)提升到O(log n)）。

---

5. 扩容机制

• 当元素数量超过容量 * 负载因子时，HashMap会将数组长度扩大为原来的2倍。
• 扩容后，所有元素会重新计算哈希值并放入新数组的对应位置。

---

6. 关键参数

• 初始容量（Initial Capacity）：默认是16。
• 负载因子（Load Factor）：默认是0.75。
• 扩容阈值（Threshold）：容量 * 负载因子。

---

7. 总结

HashMap的工作原理可以概括为：

• 通过哈希函数计算键的存储位置。
• 使用链表或红黑树解决哈希冲突。
• 在元素数量超过阈值时进行扩容。
• 通过高效的查找和插入操作，提供O(1)的平均时间复杂度。

理解HashMap的工作原理对于优化代码性能和解决相关问题非常重要。

3.你知道HashMap的get()方法的工作原理吗?

回答：

HashMap的get()方法用于根据键（key）查找对应的值（value）。它的工作原理可以分为以下几个步骤：

---

1. 计算键的哈希值

• 首先，HashMap会调用键的hashCode()方法，计算键的哈希值。
• 然后，通过扰动函数（JDK 1.8中的hash()方法）进一步优化哈希值，以减少哈希冲突。

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

• 如果键为null，哈希值固定为0（HashMap允许一个null键）。

---

2. 计算数组索引

• 通过哈希值和数组长度计算键值对在数组中的存储位置：

  index = (n - 1) & hash;

  其中，n是数组的长度（必须是2的幂次方），&操作相当于取模运算（hash % n），但效率更高。

---

3. 查找链表或红黑树

• 根据计算出的索引，定位到数组中的对应位置。
• 如果该位置为空，说明键不存在，返回null。
• 如果该位置不为空，遍历链表或红黑树：
  • 比较节点的哈希值和键：
    • 如果哈希值相同且键相等（通过equals()方法判断），则返回对应的值。
    • 如果哈希值相同但键不相等，继续遍历下一个节点。
  • 在JDK 1.8中，如果链表长度超过阈值（默认是8），链表会转换为红黑树，此时查找时间复杂度为O(log n)。

---

4. 返回结果

• 如果找到匹配的键，返回对应的值。
• 如果遍历完链表或红黑树仍未找到匹配的键，返回null。

---

5. 总结

HashMap的get()方法的工作原理可以概括为：

1. 计算键的哈希值。
2. 通过哈希值和数组长度计算索引。
3. 在数组的对应位置查找链表或红黑树。
4. 遍历链表或红黑树，通过equals()方法比较键，找到匹配的值。
5. 返回找到的值，如果未找到则返回null。

get()方法的平均时间复杂度是O(1)，在哈希冲突较多的情况下（链表或红黑树），时间复杂度会退化为O(n)或O(log n)。

4.当两个对象的hashcode相同会发生什么?

在HashMap中，当两个对象的hashCode相同时，会发生哈希冲突。
HashMap通过链表或红黑树来处理这种冲突，具体过程如下：

1. 哈希冲突的发生

   • 当两个不同的对象具有相同的hashCode时，它们会被映射到HashMap的同一个桶（bucket）中。
   • 这是因为HashMap通过hashCode确定键的存储位置（即桶的索引）。

2. 冲突的解决方式

   • 链表：在JDK 8之前，HashMap使用链表来解决冲突。当多个键被映射到同一个桶时，它们会以链表的形式存储在该桶中。
   • 红黑树：在JDK 8及之后，当链表的长度超过一定阈值（默认是8）时，HashMap会将链表转换为红黑树，以提高查找效率（从O(n)提升到O(log n)）。

3. 查找过程

   • 当根据键查找值时，HashMap会先通过hashCode定位到对应的桶。
   • 如果桶中有多个元素（即发生了冲突），HashMap会依次调用equals()方法比较键的内容，直到找到匹配的键。

假设有两个对象A和B，它们的hashCode相同但内容不同：

Map<MyKey, String> map = new HashMap<>();
MyKey key1 = new MyKey("A");
MyKey key2 = new MyKey("B");

map.put(key1, "Value1");
map.put(key2, "Value2");

// 查找时，HashMap会先通过hashCode定位到桶，然后通过equals方法比较键
String value1 = map.get(key1); // 返回"Value1"
String value2 = map.get(key2); // 返回"Value2"

总结：
当两个对象的hashCode相同时，HashMap会将它们存储在同一个桶中，并通过链表或红黑树来解决冲突。查找时，HashMap会先通过hashCode定位到桶，然后通过equals()方法比较键的内容，直到找到匹配的键。这种机制确保了HashMap在发生哈希冲突时仍能高效地存储和检索数据。

5.如果两个键的hashcode相同，你如何获取值对象?

查找过程

• 当根据键查找值时，HashMap会先通过hashCode定位到对应的桶。
• 如果桶中有多个元素（即发生了冲突），HashMap会依次调用equals()方法比较键的内容，直到找到匹配的键。

6.如果HashMap的大小超过了加载因子(load factor)定义的容量，怎么办?

扩容：

1. 创建一个新数组，大小为原数组的2倍。
2. jdk1.7，将原数组中的元素重新计算哈希值，并放入新数组的对应位置。
3. 在JDK 1.8中，通过链表拆分优化减少了重新哈希的计算量。

7.你了解重新调整HashMap大小存在什么问题吗?

jdk1.7一旦扩容，整个链表需要全部从新进行一轮运算，所有结点需要全部重新计算哈希值

扩容

jdk1.8可能计算同时是地位，不够分散

8.为什么string,Interger这样的wrapper类（包装类）适合作为键?

String、Integer等包装类适合作为HashMap的键，主要是因为它们具有以下特性：

1. 不可变性（Immutable）

   • String和Integer都是不可变类，即一旦创建，它们的值就不能被修改。
   • 不可变性确保了键的哈希值在存入HashMap后不会改变。如果键是可变的，修改键的值会导致哈希值变化，从而导致HashMap无法正确定位到原来的值，破坏数据的完整性。

2. 重写了equals()和hashCode()方法

   • HashMap依赖equals()方法来判断键是否相等，依赖hashCode()方法来确定键的存储位置。
   • String和Integer都重写了equals()和hashCode()方法，确保：
     • 相等的对象具有相同的哈希值（满足hashCode契约）。
     • equals()方法能够正确比较对象的内容，而不是比较对象的引用。
   • 例如，两个内容相同的String对象（如"abc"）会返回相同的哈希值，并且equals()会返回true。

3. 良好的哈希分布

   • String和Integer的哈希算法设计良好，能够有效减少哈希冲突。
   • 例如，String的哈希算法通过对每个字符进行计算，生成一个分布均匀的哈希值。

4. 线程安全性

   • 由于String和Integer是不可变的，它们天然是线程安全的，适合在多线程环境中作为HashMap的键使用。

示例说明：

Map<String, Integer> map = new HashMap<>();
map.put("key1", 1);
map.put("key2", 2);

// 查找时，HashMap会根据"key1"的哈希值快速定位到对应的值
Integer value = map.get("key1"); // 返回1

总结：
String和Integer等包装类适合作为HashMap的键，主要是因为它们的不可变性、良好的哈希算法设计以及对**equals()和hashCode()**方法的正确实现。这些特性确保了HashMap能够高效、准确地存储和检索键值对。

9.我们可以使用自定义的对象作为键吗?

可以（对象需要重写equals和hashCode方法）

回答：

是的，我们可以使用自定义对象作为HashMap的键，但需要满足以下条件：

1. 重写equals()方法

   • HashMap依赖equals()方法来判断两个键是否相等。如果自定义对象没有重写equals()方法，默认会使用Object类的equals()方法，该方法比较的是对象的内存地址（即引用相等），而不是对象的内容。
   • 重写equals()方法时，需要确保逻辑正确，能够比较对象的内容是否相等。

2. 重写hashCode()方法

   • HashMap依赖hashCode()方法来确定键的存储位置。如果自定义对象没有重写hashCode()方法，默认会使用Object类的hashCode()方法，该方法通常返回对象的内存地址的哈希值。
   • 重写hashCode()方法时，需要满足以下契约：
     • 如果两个对象通过equals()方法比较相等，那么它们的hashCode()必须相同。
     • 如果两个对象通过equals()方法比较不相等，它们的hashCode()可以相同，但为了减少哈希冲突，应尽量使不同的对象返回不同的哈希值。

3. 不可变性（推荐）

   • 虽然不是强制要求，但建议将自定义对象设计为不可变的。如果对象是可变的，修改对象的状态会导致其哈希值变化，从而导致HashMap无法正确定位到原来的值，破坏数据的完整性。

示例：

假设有一个自定义类Person，我们希望将其作为HashMap的键：

public class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    // Getters and setters (if mutable)
}

使用Person作为HashMap的键：

Map<Person, String> map = new HashMap<>();
Person person1 = new Person("Alice", 30);
Person person2 = new Person("Bob", 25);

map.put(person1, "Developer");
map.put(person2, "Designer");

// 查找时，HashMap会根据Person对象的哈希值和equals方法定位到对应的值
String job = map.get(new Person("Alice", 30)); // 返回"Developer"

总结：
可以使用自定义对象作为HashMap的键，但必须重写equals()和hashCode()方法，以确保HashMap能够正确存储和检索键值对。此外，建议将自定义对象设计为不可变的，以避免潜在的问题。

HashMap是线程安全的吗？

为什么不安全？

• 内部结构、操作不是线程安全的
• 非同步操作（没有加锁）在多个线程同时对HashMap操作可能会出现线程不一致的问题
• 非原子操作
  • put操作有多个步骤（包括计算哈希值、查找和插入多个元素等等）
  • 如果多个线程同时执行这一操作就可能出现数据不一致的情况
• 扩容（非原子操作）
  • 在扩容的时候需要重新计算哈希值，并重新分配存储位置（这个过程涉及对原数组进行复制和重新插入元素，如果在扩容期间，有其他线程对HashMap进行并发修改，就可能导致数据丢失或出现异常）

解决办法？

• 使用同步机制
• 使用并发容器ConcurrentHashMap
• 线程封闭
  • 将HashMap封闭到单个线程中，通过使用ThreadLocal，就是使用线程副本（每个线程操作的都是自己的副本，就不会对共享的这个数据产生影响），或者将这个HashMap作为局部变量，在每个线程中进行操作，

2.3 请说一下HashMap与HashTable的区别（享学）

HashMap 和 HashTable 是 Java 中常用的两种哈希表实现，它们的主要区别如下：

1. 线程安全性

• HashTable：是线程安全的，所有方法都使用 synchronized 修饰，适合多线程环境，但性能较低。
• HashMap：非线程安全，性能更高，适合单线程环境。多线程时需手动同步或使用 Collections.synchronizedMap 或 ConcurrentHashMap。

2. 是否允许 null 键和 null 值

• HashTable：不允许 null 键或 null 值，否则会抛出 NullPointerException。
• HashMap：允许一个 null 键和多个 null 值。

3. 性能

• HashTable：由于同步开销，性能较差。
• HashMap：无同步开销，性能更好。

4. 初始容量与扩容

• HashTable：默认初始容量为 11，扩容为 2n + 1。
• HashMap：默认初始容量为 16，扩容为 2n。

5. 哈希算法

• HashTable：直接使用对象的 hashCode。
• HashMap：对 hashCode 进行二次哈希以减少冲突。

6. 继承与实现

• HashTable：继承自 Dictionary 类。
• HashMap：继承自 AbstractMap 类。

7. 迭代器

• HashTable：使用 Enumeration 进行遍历，不支持快速失败机制。
• HashMap：使用 Iterator，支持快速失败机制，遍历时若结构被修改会抛出 ConcurrentModificationException。

2.6 请简述 LinkedHashMap 的工作原理和使用方式？（享学）

LinkedHashMap 是 Java 中 HashMap 的一个子类，它在 HashMap 的基础上维护了一个双向链表，用于记录元素的插入顺序或访问顺序。以下是 LinkedHashMap 的工作原理和使用方式的简要说明：

---

工作原理

1. 数据结构：

   • LinkedHashMap 继承自 HashMap，底层使用哈希表存储数据。
   • 额外维护了一个双向链表，用于记录元素的顺序。这个链表可以是：
     • 插入顺序：按照元素插入的顺序排列。
     • 访问顺序：按照元素最近被访问的顺序排列（最近访问的元素会被移到链表末尾）。

2. 顺序维护：

   • 每次插入新元素时，除了将其放入哈希表中，还会将其添加到双向链表的末尾。
   • 如果是基于访问顺序的模式，当调用 get() 或 put() 方法访问某个元素时，该元素会被移动到链表的末尾。

3. LRU 缓存实现：

   • LinkedHashMap 可以通过重写 removeEldestEntry() 方法实现 LRU（Least Recently Used，最近最少使用）缓存。当容量达到上限时，最久未使用的元素会被自动移除。
     • 新数据插入到链表头部
     • 当缓存命中(即缓存数据被访问)，数据要移到表头
     • 当链表满的时候，将链表尾部的数据丢弃

---

使用方式

1. 基本用法：

   • LinkedHashMap 的使用方式与 HashMap 类似，支持 put()、get()、remove() 等操作。
   • 默认情况下，LinkedHashMap 按照插入顺序维护元素顺序。

   LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
   map.put("one", 1);
   map.put("two", 2);
   map.put("three", 3);
   
   // 输出顺序为插入顺序：one -> two -> three
   for (String key : map.keySet()) {
       System.out.println(key);
   }

2. 基于访问顺序的模式：

   • 通过构造函数设置 accessOrder 参数为 true，可以让 LinkedHashMap 按照访问顺序维护元素。

   LinkedHashMap<String, Integer> map = new LinkedHashMap<>(16, 0.75f, true);
   map.put("one", 1);
   map.put("two", 2);
   map.put("three", 3);
   
   map.get("one"); // 访问 "one"，将其移到链表末尾
   
   // 输出顺序为访问顺序：two -> three -> one
   for (String key : map.keySet()) {
       System.out.println(key);
   }

3. 实现 LRU 缓存：

   • 通过重写 removeEldestEntry() 方法，可以实现一个固定大小的 LRU 缓存。

   int cacheSize = 3;
   LinkedHashMap<String, Integer> lruCache = new LinkedHashMap<String, Integer>(16, 0.75f, true) {
       @Override
       protected boolean removeEldestEntry(Map.Entry<String, Integer> eldest) {
           return size() > cacheSize; // 当容量超过 cacheSize 时，移除最久未使用的元素
       }
   };
   
   lruCache.put("one", 1);
   lruCache.put("two", 2);
   lruCache.put("three", 3);
   lruCache.get("one"); // 访问 "one"，将其移到链表末尾
   lruCache.put("four", 4); // 插入新元素，移除最久未使用的 "two"
   
   // 输出顺序为：three -> one -> four
   for (String key : lruCache.keySet()) {
       System.out.println(key);
   }

---

总结

• LinkedHashMap 在 HashMap 的基础上增加了顺序维护功能，支持插入顺序或访问顺序。
• 它非常适合需要维护元素顺序的场景，例如实现 LRU 缓存。
• 如果需要线程安全的 LinkedHashMap，可以使用 Collections.synchronizedMap() 进行包装，或者使用 ConcurrentHashMap 结合其他方式实现类似功能。

---

红黑树是一种新的解决hash冲突的方式

JDK1.8之前用的链表

1.8之后用的红黑树

数组和链表如何组织工作？

int hash是什么?有什么作用

Hash的原理是什么？

Hash的put方法原理？

Hash的get方法原理？

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
//位运算的速度更快

/**
^异或操作——同0异1
增加哈希值的分散性
*/

加载因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

通过数组大小length的变化 可以解决哈希冲突的问题

什么时候扩容？

length = 16

加载因子=0.75

16×0.75 = 12

当存了12个位置之后，就需要扩容，扩容之后就可以减少冲突

---

Java8之后改为红黑树，

左边结点小，右边结点大

节点查找优先级由 O（n）->提高到了O（logn）

Donate