当前位置：首页 > article >正文

说说HashMap 的位操作以及HashSet的contains方法复杂度是多少？

article 2025/1/21 10:17:22

HashMap 是一种基于哈希表的集合实现，其内部使用一个数组来存储键值对。在 Java 中，位操作在 HashMap 的实现中扮演着重要的角色。以下是 HashMap 中涉及到的主要位操作：

Hash Code 计算：
- HashMap 使用对象的 hashCode() 方法来计算对象的哈希值。为了提高哈希冲突的处理效率，会对哈希值进行一系列位运算处理。
- HashMap 中会使用高位和低位的处理来混合哈希值，例如使用异或（^）操作。具体实现如下：
```
int hash = key.hashCode();
hash ^= (hash >>> 20) ^ (hash >>> 12);
hash ^= (hash << 7) ^ (hash << 4);
hash ^= (hash >>> 24);
return hash & (n - 1); // n 是当前的数组长度
```
数组索引计算：
- 在存储元素时，HashMap 需要根据计算出的哈希值来找到存储的数组索引，这使用了以下操作：
```
int index = hash % capacity; // capacity 是当前数组的容量
```
- 为了保持数组索引在合法范围内，通常会进行位运算，以确保性能更高且避免不必要的整除操作。HashMap 采用 index = hash & (n - 1)，这样可以利用 n 是 2 的幂次方的特性，使得求余操作更高效。
容量扩展：
- 当 HashMap 的元素数量超过阈值（负载因子与当前容量的乘积）时，会进行数组扩展和元素重新哈希（rehashing）。在这个过程中，原有的哈希值和计算的索引都会使用上述位运算来重新映射到新的数组。

HashSet 是基于 HashMap 实现的，它将每个元素作为 HashMap 的键，而值为一个常量。调用 HashSet 的 contains 方法时，实际上是通过 HashMap 的 containsKey 方法来实现的。

时间复杂度：
- 平均情况下，HashMap 的 containsKey() 方法具有 O(1) 的时间复杂度，因为它只需计算哈希值并查找索引。
- 在最坏情况下（例如：所有元素的哈希值冲突导致进入同一个链表），时间复杂度为 O(n)，其中 n 是当前 HashSet 中的元素数量。

总的来说：