HashMap的结构

在 JDK 1.7 版本之前， HashMap 数据结构是数组和链表，HashMap通过哈希算法将元素的键（Key）映射到数组中的槽位（Bucket）。如果多个键映射到同一个槽位，它们会以链表的形式存储在同一个槽位上，因为链表的查询时间是O(n)，所以冲突很严重，一个索引上的链表非常长，效率就很低了。 

所以在 JDK 1.8 版本的时候做了优化，当一个链表的长度超过8的时候就转换数据结构，不再使用链表存储，而是使用红黑树，查找时使用红黑树，时间复杂度O（log n），可以提高查询性能，但是在数量较少时，即数量小于6时，会将红黑树转换回链表。

HashMap底层是链表，但是当链表的长度大于8时，并且数组的长度大于64，此时会将链表转化为红黑树来提高查询效率。（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）

image.png

为什么HashMap链表转红黑树的阈值为8呢？

红黑树节点的大小大概是普通节点大小的两倍，所以转红黑树，牺牲了空间换时间，更多的是一种兜底的策略，保证极端情况下的查找效率。

阈值为什么要选8呢？和统计学有关。理想情况下，使用随机哈希码，链表里的节点符合泊松分布，出现节点个数的概率是递减的，对于HashMap来说，通过统计分析，如果负载因子为 0.75（这是HashMap默认的负载因子），哈希桶中元素个数为 8 的概率约为 **6*10 -6**（这个概率非常小）。这意味着在正常情况下，链表长度达到 8 是比较少见的情况，一旦达到这个长度，说明哈希冲突比较严重，将其转换为红黑树可以更好地处理后续的插入和查找操作。

至于红黑树转回链表的阈值为什么是6，而不是8？是因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费。

HashMap中的key和value是怎么存的？

HashMap 使用数组加链表或红黑树的结构来存储键值对。

  1. 数组：
  • 数组的每个元素可以指向一个链表的头节点或者红黑树的根节点。
  • 数组的长度在创建 HashMap 时确定，或者随着存储元素的增加而动态调整。
  1. 链表：
  • 当多个不同的 key 经过哈希计算后得到相同的数组下标时，这些键值对就会以链表的形式存储在该下标对应的位置。
  • 链表中的每个节点包含 key、value 和指向下一个节点的引用。
  1. 红黑树：
  • 当链表的长度超过一定阈值时，链表会被转换为红黑树，以提高查找、插入和删除的效率。
  • 红黑树中的每个节点也包含 key、value 和指向其他节点的引用，同时满足红黑树的性质。

在 HashMap 中，数组通常不直接存放完整的元素本身（键值对），而是存到链表或红黑树头结点的引用。

如果经过哈希计算后，某个索引处只有一个元素，这个元素也不是直接存放在数组中，而是以节点的形式存放在链表中，即使此时链表中只有一个节点。

了解的哈希冲突解决方法有哪些？

  • 链接法：使用链表或其他数据结构来存储冲突的键值对，将它们链接在同一个哈希桶中。
  • 开放寻址法：在哈希表中找到另一个可用的位置来存储冲突的键值对，而不是存储在链表中。常见的开放寻址方法包括线性探测、二次探测和双重散列。
  • 再哈希法（Rehashing）：当发生冲突时，使用另一个哈希函数再次计算键的哈希值，直到找到一个空槽来存储键值对。
  • 哈希桶扩容：当哈希冲突过多时，可以动态地扩大哈希桶的数量，重新分配键值对，以减少冲突的概率。

HashMap 和 HashTable 的区别

HashMap

  • 线程安全性：HashMap 不是线程安全的。这意味着在多线程环境中直接使用 HashMap 可能会导致数据不一致的问题。如果需要线程安全的行为，可以使用 Collections.synchronizedMap() 方法来包装 HashMap。
  • null 键和值：HashMap 允许使用 null 键和 null 值。但是，只能有一个 null 键，而 null 值的数量则取决于 put() 方法被调用的次数。
  • 性能：由于 HashMap 不是线程安全的，因此在大多数情况下它的性能比 Hashtable 更好。
  • 初始容量和加载因子：HashMap 允许指定初始容量和加载因子，这有助于优化内存使用和性能。
  • 扩容： 默认初始容量为16，每次扩充变为原来2倍。创建时如果给定了初始容量，则扩充为2的幂次方大小

HashTable

  • 线程安全性：Hashtable 是线程安全的。每个方法使用synchronized修饰来保证线程安全。所有的读写操作都是同步的，因此可以在多线程环境中直接使用 Hashtable。
  • null 键和值：Hashtable 不允许使用 null 键或 null 值。如果尝试添加 null 键或 null 值，将会抛出 NullPointerException。
  • 性能：由于 Hashtable 的所有方法都是同步的，因此在多线程环境下的性能可能不如 HashMap。
  • 扩容： HashTable不指定大小时默认大小为11，每次扩容变为原来大小的2n+1.

  • 线程是否安全：HashMap是线程不安全的，HashTable是线程安全的

  • 效率：HashMap因为其是线程不安全的，所以效率要比HashTable效率要高

  • 扩容：HashMap不指定大小时默认大小为16，每次扩容变为原来大小的2的n次幂；HashTable不指定大小时默认大小为11，每次扩容变为原来大小的2n+1.

  • 数据结构：HashMap底层是链表，但是当链表的长度大于8时，并且数组的长度大于64，此时会将链表转化为红黑树来提高查询效率。（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）

HashMap和HashSet

HashSet是基于HashMap实现的。

image.png

HashSet 是 Java 中的一个常用集合类，它实现了 Set 接口，用于存储不重复的元素。下面详细介绍 HashSet 的底层结构和工作原理：

底层结构

HashSet 的底层实际上使用了一个 HashMap 来存储元素。这是因为 HashSet 需要保证元素的唯一性，而 HashMap 的键恰好也是唯一的。**HashSet 将每个元素作为 HashMap 的键，并将所有值设置为同一个静态对象 PRESENT**。这样，HashSet 可以利用 HashMap 的高效性来实现元素的添加、删除和查找操作。

工作原理

  1. 添加元素：
  • 当向 HashSet 添加一个元素时，该元素会被当作 HashMap 的键。
  • HashMap 会计算该元素的哈希码，并将其与 PRESENT 关联起来。
  • 如果元素的哈希码对应的位置已经有其他元素，那么会发生哈希冲突，这时会使用链表或红黑树（当链表达到一定长度时）来存储具有相同哈希码的元素。
  1. 查找元素：
  • 查找元素时，HashSet 会计算该元素的哈希码，并查找相应的桶。
  • 如果桶为空，则说明该元素不存在。
  • 如果桶不为空，则遍历桶中的链表或红黑树，使用 .equals() 方法来比较元素是否相等。
  • 如果找到匹配的元素，则返回 true，否则返回 false。
  1. 删除元素：
  • 删除元素的过程与查找过程类似，首先计算哈希码，然后在相应的桶中查找该元素。
  • 找到后，从链表或红黑树中移除该元素。

特点

  • 线程不安全性：HashSet 本身不是线程安全的。如果多个线程同时修改 HashSet，则需要采取外部同步措施，如使用 Collections.synchronizedSet(new HashSet<>()) 或 ConcurrentSkipListSet。
  • 不允许 null 元素：HashSet 不允许添加 null 元素，尝试添加 null 会抛出 NullPointerException。
  • 无序性：HashSet 中的元素是无序的，也就是说，它们不会按照插入顺序或任何其他特定顺序排序。
  • 性能：由于 HashSet 的底层是 HashMap，因此它提供了平均时间复杂度为 O(1) 的添加、删除和查找操作。

总结

HashSet 是一个不包含重复元素的集合，它利用 HashMap 的高效性来实现元素的添加、删除和查找操作。由于其线程不安全性，通常适用于单线程环境或者需要外部同步的情况。如果需要线程安全的集合，可以考虑使用 ConcurrentSkipListSet 或者通过 Collections.synchronizedSet() 包装 HashSet

HashSet如何检查是否存在相同元素？

是基于hashCode和equals方法

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功

HashMap 和 TreeMap 区别

HashMap

  • 数据结构：HashMap 使用哈希表实现，通过哈希函数将键映射到数组中的位置。这使得 HashMap 提供了平均时间复杂度为 O(1) 的插入、删除和查找操作。
  • 键的顺序：HashMap 不保证键的任何特定顺序。每次迭代的顺序可能不同，除非使用了 LinkedHashMap（它按照插入顺序或访问顺序保持键）。
  • 线程安全性：HashMap 不是线程安全的。如果多个线程并发地修改 HashMap，则需要外部同步。
  • null 键和值：HashMap 允许使用 null 键和 null 值。但是，只能有一个 null 键，而 null 值的数量则取决于 put() 方法被调用的次数。
  • 性能：由于 HashMap 不需要同步，因此在大多数情况下它的性能非常好。

TreeMap

  • 数据结构：TreeMap 使用红黑树实现，这是一种自平衡的二叉搜索树。这使得 TreeMap 的插入、删除和查找操作的时间复杂度为 O(log n)。
  • 键的顺序：TreeMap 保证键的自然排序或根据提供的 Comparator 排序。因此，当你遍历 TreeMap 时，键总是按升序排列。
  • 线程安全性：TreeMap 同样不是线程安全的，需要外部同步才能在多线程环境中安全使用。
  • null 键和值：TreeMap 不允许使用 null 键，但可以使用 null 值。
  • 性能：虽然 TreeMap 的性能通常略低于 HashMap，但它提供了有序的键值对，这对于某些应用场景非常重要。

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

NavigableMap 接口提供了丰富的方法来探索和操作键值对:

  1. 定向搜索: ceilingEntry(), floorEntry(), higherEntry()和 lowerEntry() 等方法可以用于定位大于、小于、大于等于、小于等于给定键的最接近的键值对。
  2. 子集操作: subMap(), headMap()和 tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。
  3. 逆序视图:descendingMap() 方法返回一个逆序的 NavigableMap 视图，使得可以反向迭代整个 TreeMap。
  4. 边界操作: firstEntry(), lastEntry(), pollFirstEntry()和 pollLastEntry() 等方法可以方便地访问和移除元素。

这些方法都是基于红黑树数据结构的属性实现的，红黑树保持平衡状态，从而保证了搜索操作的时间复杂度为 O(log n)，这让 TreeMap 成为了处理有序集合搜索问题的强大工具。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

综上，相比于HashMap来说， TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力

总结

  • 使用场景：
  • 如果你需要快速地进行键值对的查找、插入和删除操作，并且键的顺序不重要，那么 HashMap 是一个很好的选择。
  • 如果你还需要键按照某种顺序排序，并且可以接受稍微慢一些的操作时间，那么 TreeMap 更适合。

HashMap put元素的过程

image.png

在Java中，HashMap的put方法的实现原理可以分为以下几个步骤：

1.首先会调用键对象的 hashCode() 方法来计算键的哈希码。HashMap使用键的哈希码来确定键值对在哈希表中的存储位置。

2.接下来，通过哈希码计算出键值对在哈希表中的索引位置。HashMap使用一个称为“哈希函数”的算法来计算索引位置。常用的哈希函数是将哈希码与哈希表的容量进行取模运算，得到索引位置。 也就是（Hash % len）

3.如果该索引位置上没有其他键值对，则直接将键值对存储在该位置上。如果该索引位置上已经存在其他键值对，则发生了“哈希冲突”。

4.当发生哈希冲突时，HashMap使用链表或红黑树来解决冲突。如果桶中已经有键值对存在，HashMap 会遍历链表来查找是否存在相同的键。如果找到了相同的键，就更新对应的值；如果没有找到，则在链表的头部添加一个新的键值对节点

1.7使用头插法，因为他认为先最近插入的最容易被访问，但是在并发，扩容数组的时候可能会出现死循环。因为并发扩容reHash一张新的表。扩容的时候会出现两个数组。使用头插法，且插入时不是原子性的，因此可能会出现死循环。

因此1.8又变为了尾插法

通过以上步骤，HashMap的put方法成功将键值对存储在哈希表中。需要注意的是，当哈希表的负载因子（即存储的键值对数量与容量的比值）超过一定阈值时，HashMap会进行扩容操作，以保持哈希表的性能。

计算索引位置

  • 哈希函数：HashMap 使用一个哈希函数来将键的哈希码转换为一个索引值。这个索引值指示了键值对在内部数组中的位置。
  • 取模运算：常用的哈希函数是通过将哈希码与 HashMap 的容量（通常是2的幂）进行取模运算来计算索引位置的。例如，如果 HashMap 的容量为 16（2^4），那么哈希码 h 与容量取模的结果就是 h % 16。

索引位置与桶

  • 桶：HashMap 的内部是一个数组，数组中的每个位置称为一个“桶”。每个桶可以存储一个键值对或者一个键值对的链表（如果发生了哈希冲突）。
  • 哈希冲突：当两个不同的键的哈希值映射到同一个索引位置时，就会发生哈希冲突。HashMap 通过链表或红黑树来解决哈希冲突，将冲突的键值对存储在同一个桶中。

HashMap 的键是一个对象，现在修改对象的一个属性，还能根据对象获取到对应的值吗？

在Java中，HashMap是通过键（key）来存储和检索值（value）的。键值对（key-value pair）是基于键的哈希码（hashCode）以及equals方法来确定唯一性的。如果你使用一个对象作为键，并且之后修改了该对象的状态（例如，修改了对象中的某个属性），是否会影响HashMap中的键值对关联性？

这取决于对象的hashCode或equals方法：

  1. 如果该对象没有重写hashCode或equals方法，则依据对象的内存地址获取对应的值，此时修改对象的属性并不会影响键值对的映射关系，因为对象的地址并没有变
  2. 如果如果该对象重写了hashCode或equals方法，但是在hashCode或equals方法依赖于其他字段，当我们修改另一个字段的值时并不会影响hashCode或equals方法的结果
  3. 如果如果该对象重写了hashCode或equals方法，并且在hashCode或equals方法中依赖了对象的所有字段，这时候当我们修改属性的值时就会产生影响

示例代码：

1.如果重写hashCode和equals方法

假设我们有一个Person类，其hashCode和equals方法依赖于name属性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 Objects.equals(name, person.name);
    }

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

// Getters and Setters...
}

在这种情况下，如果你修改了Person对象的name属性，那么这个对象将无法在HashMap中找到对应的条目。如果对age属性进行修改，则仍然能够在HashMap中找到对应的值。

为了保持一致性，hashCode和equals方法应该只依赖于那些不变的属性，或者你必须确保在修改这些属性之前不再使用该对象作为键。

2.如果不重写hashCode和equals方法

如果不重写hashCode和equals方法，默认情况下，Object类提供的方法会被使用。默认的hashCode方法返回的是对象的内存地址经过某种算法计算得到的哈希值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Book {
    private String isbn;
    private String title;
    private String author;

    public Book(String isbn, String title, String author) {
        this.isbn = isbn;
        this.title = title;
        this.author = author;
    }
}

public class Main {
    public static void main(String[] args) {
        HashMap<Book, String> library = new HashMap<>();

        Book book1 = new Book("978-3-16-148410-0", "The Great Gatsby", "F. Scott Fitzgerald");
        library.put(book1, "This is the description of The Great Gatsby.");

	// 创建另一个具有相同内容的新Book对象
        Book book2 = new Book("978-3-16-148410-0", "The Great Gatsby", "F. Scott Fitzgerald");

	// 尽管book1和book2具有相同的属性，但由于它们是不同的对象引用，
	// 默认的equals方法将返回false，因此下面的get将返回null。
        String description = library.get(book2);
        System.out.println(description);  // 输出: null

		// 修改book1的title和author
        book1.setTitle("The Great Gatsby - New Edition");
        book1.setAuthor("F. Scott Fitzgerald - Updated");

		// 由于book1的引用没有改变，所以仍然可以从map中获取描述
        description = library.get(book1);
        System.out.println(description);  // 输出: This is the description of The Great Gatsby.
    }
}

HashMap 的长度为什么是 2 的幂次方

1、可以转换成位运算，效率高

“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length == hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 & 相对于 % 能够提高运算效率，这是一部分原因，还有就是扩容的原因。

2、扩容更高效

在JDK1.7中，HashMap 整个扩容过程就是分别取出数组元素，取出的这个数组元素一般是最后一个放入链表中的元素，然后遍历以该元素为头的单向链表元素，依据每个被遍历元素的hash值计算其在新数组中的下标，然后进行交换。这样的扩容方式会将原来哈希冲突的单向链表尾部变成扩容后单向链表的头部（这也是造成死循环的根本原因）。

而在JDK1.8中，HashMap对扩容操作做了优化。由于扩容数组的长度是2倍关系，所以对于假设初始tableSize=4要扩容到8来说就是0100到1000的变化（左移一位就是2倍），在扩容中只用判断原来的hash 值和左移动的一位（newtable 的值）按位与操作是0或1就行，0的话索引不变，1的话索引变成原索引加上扩容前数组。

之所以能通过这种”与运算”来重新分配索引，是因为hash值本来就是随机的，而hash按位与上newTable得到的0（扩容前的索引位置）和1（扩容前索引位置加上扩容前数组长度的数值索引处）就是随机的，所以扩容的过程就能把之前哈希冲突的元素再随机分布到不同的索引中去。

如果初始化HashMap，传一个17的值，它会怎么处理

简单来说，就是初始化时，传的不是2的倍数时，HashMap会向上寻找离得最近的2的倍数，所以传入17，但HashMap的实际容量是32。

  • 对于传入的初始容量 17，HashMap会通过一系列计算来确定实际容量。具体来说，它会调用tableSizeFor(int cap)方法来计算合适的容量。
  • 该方法的主要目的是找到大于等于cap的最小的 2 的幂次方。例如，对于传入的 17，计算过程如下：
    • 首先，tableSizeFor方法会将传入的初始容量 17 转换为二进制形式，即10001。
    • 然后，它会通过不断的左移和或运算，将最高位的 1 之后的所有位都设置为 1。对于 17，经过这些操作后得到的值是 32（二进制为100000）。
  • 这个 32 就是大于等于 17 的最小的 2 的幂次方，所以HashMap实际初始化时内部数组的容量为 32
1
2
3
4
5
6
7
8
9
static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

  • 计算过程是向右移位1、2、4、8、16，和原来的数做|运算，这主要是为了把⼆进制的各个位置都填上1，当⼆进制的各个位置都是1以后，就是⼀个标准的2的倍数减1了，最后把结果加1再返回即可。
  • 当传入cap = 17时，首先n = cap - 1 = 16（二进制为10000）。然后通过一系列的右移和或运算，最后返回的值是 32，这就是HashMap最终使用的容量。

以17为例，看一下初始化计算table容量的过程：

image.png

HashMap扩容机制

当HashMap中的元素个数超过数组长度loadFactor(负载因子)时，就会进行数组扩容，loadFactor的默认值是0.75,这是一个折中的取值。也就是说，默认情况下，数组大小为16，那么当HashMap中的元素个数超过16×0.75=12(这个值就是阈值)的时候，就把数组的大小扩展为2×16=32，即扩大一倍，也就是左移一位。然后重新计算每个元素在数组中的位置，而这是一个非常耗性能的操作，所以如果我们已经预知HashMap中元素的个数，那么预知元素的个数能够有效的提高HashMap的性能。

HashMap在进行扩容时使用 resize() 方法，计算 table 数组的新容量和 Node 在新数组中的新位置，将旧数组中的值复制到新数组中，从而实现自动扩容。因为每次扩容都是翻倍，与原来计算的 (n-1)&hash的结果相比，只是多了一个bit位，所以节点要么就在原来的位置，要么就被分配到”原位置+旧容量”这个位置。

因此，我们在扩充HashMap的时候，不需要重新计算hash，**只需要看看原来hash值新增的那个bit是1还是0就可以了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原位置+旧容量)**”。这里不再详细赘述，可以看看下图为16扩充为32的resize示意图：
image.png

HashMap死循环问题

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。并且在链表长度大于8，数组长度大于64时还会将链表转化为红黑树，降低成环的风险。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

1.7使用头插法，因为他认为先最近插入的最容易被访问，但是在并发，扩容数组的时候可能会出现死循环。因为并发扩容reHash一张新的表。扩容的时候会出现两个数组。使用头插法，且插入时不是原子性的，因此可能会出现死循环。

因此1.8又变为了尾插法

HashMap为什么线程不安全？

在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

举个例子：

  • 两个线程 1,2 同时进行 put 操作，并且发生了哈希冲突（hash 函数计算出的插入下标是相同的）。
  • 不同的线程可能在不同的时间片获得 CPU 执行的机会，当前线程 1 执行完哈希冲突判断后，由于时间片耗尽挂起。线程 2 先完成了插入操作。
  • 随后，线程 1 获得时间片，由于之前已经进行过 hash 碰撞的判断，所有此时会直接进行插入，这就导致线程 2 插入的数据被线程 1 覆盖了。

HashMap 负载因子

loadFactor 负载因子是控制数组存放数据的疏密程度，loadFactor 越趋近于 1，那么 数组中存放的数据(entry)也就越多，也就越密，也就是会让链表的长度增加，loadFactor 越小，也就是趋近于 0，数组中存放的数据(entry)也就越少，也就越稀疏。

loadFactor 太大导致查找元素效率低，太小导致数组的利用率低，存放的数据会很分散。loadFactor 的默认值为 0.75f 是官方给出的一个比较好的临界值。

给定的默认容量为 16，负载因子为 0.75。Map 在使用过程中不断的往里面存放数据，当数量超过了 16 * 0.75 = 12 就需要将当前 16 的容量进行扩容，而扩容这个过程涉及到 rehash、复制数据等操作，所以非常消耗性能。

HashMap的扰动函数

在 Java 中，HashMap 类使用了一种扰动函数来优化散列值的分布，以减少哈希冲突并提高性能。扰动函数通过将计算出的散列值进行一定的变换，使其在桶数组中更加均匀地分布，从而减少哈希冲突的可能性。

扰动函数的历史变化

1.Java 1.4 和早期版本：

  • 在 Java 1.4 和早期版本中，HashMap 使用了较为复杂的扰动函数，如下所示：
    1
    2
    3
    4
    5
    6
    7
    static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
    }
    这个扰动函数通过对原始散列值进行多次右移和异或操作来生成一个新的散列值，以提高散列值的随机性和均匀性。

2.Java 1.8：

  • 在 Java 1.8 中，扰动函数被简化了，主要是因为在现代 CPU 上，散列碰撞的性能影响相对较小，而且现代处理器具有更好的缓存一致性，所以不再需要这么复杂的扰动函数。
  • Java 1.8 中的 HashMap 使用了简化的扰动函数，如下所示：
    1
    2
    3
    4
    final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

扰动函数的作用：

扰动函数的主要作用是提高散列值的随机性和均匀性，从而减少哈希冲突。通过扰动函数，即使是那些散列码相似的键也能被映射到不同的桶中，从而减少桶中的链表长度，提高查找效率。

总结

扰动函数是 HashMap 用于优化散列值分布的一种机制，它通过简单的位运算来提高散列值的随机性和均匀性，从而减少哈希冲突。在 Java 1.8 中，扰动函数被简化，但仍保留了其基本的功能，即提高散列值的随机性和均匀性。扰动函数对于提高 HashMap 的性能至关重要，尤其是在处理大量数据时。