Java基础：为什么hashmap的长度要设置为2的倍数？

╰半橙微兮° 2023-10-12 08:28 10阅读 0赞

HashMap 的长度（capacity）通常被设置为 2 的倍数（2^n 的形式，其中 n 是非负整数）是为了提高哈希表的性能和减少冲突。

HashMap 使用哈希函数将键映射到哈希表的槽位（bucket）中。槽位的数量决定了哈希表的容量。在哈希冲突的情况下，即不同的键映射到相同的槽位，会使用链表或红黑树等数据结构来解决冲突。

下面是设置 HashMap 长度为 2 的倍数的几个原因：

1.  散列函数计算索引：HashMap 使用键的散列码（hash code）和位运算来计算键的索引。当长度为 2 的倍数时，通过位运算可以用更高效的方式计算索引，即 `(n - 1) & hash`，其中 `n` 是容量，`hash` 是键的散列码。这样可以避免取模运算，提高计算效率。
2.  平均分布：当长度为 2 的倍数时，哈希表中的槽位可以更均匀地分布键值对，减少碰撞的可能性。如果容量不是 2 的倍数，通过取模运算来计算索引时，可能会导致部分槽位无法被充分利用，使得冲突的几率增加。
3.  扩容效率：当哈希表需要扩容时，新的容量通常会设置为当前容量的两倍。这样，当容量为 2 的倍数时，扩容时只需要进行简单的位运算，而不需要重新计算每个键的索引，提高了扩容的效率。

需要注意的是，尽管设置长度为 2 的倍数可以提高性能，但在极端情况下，如果哈希表的容量过大而实际的键值对数量较少，可能会导致内存浪费。因此，在选择 HashMap 的容量时，需要根据实际情况进行权衡，考虑到预期的键值对数量和性能需求。

## 代码说明 ##

以下是一个简单的示例代码来说明哈希表容量为 2 的倍数时，键值对更均匀地分布的情况：

import java.util.HashMap;
    
    public class HashMapDistributionExample {
        
        public static void main(String[] args) {
        
            int capacity = 16;  // 容量为 2 的倍数
            HashMap<Integer, String> hashMap = new HashMap<>(capacity);
    
            // 添加一系列键值对
            for (int i = 0; i < 100; i++) {
        
                hashMap.put(i, "Value " + i);
            }
    
            // 打印每个槽位中的键值对数量
            for (int i = 0; i < capacity; i++) {
        
                int count = countKeyValuePairsInSlot(hashMap, i);
                System.out.println("Slot " + i + ": " + count + " key-value pairs");
            }
        }
    
        public static int countKeyValuePairsInSlot(HashMap<Integer, String> hashMap, int slotIndex) {
        
            int count = 0;
            for (Integer key : hashMap.keySet()) {
        
                int hashCode = key.hashCode();
                int slot = (hashMap.size() - 1) & hashCode;
                if (slot == slotIndex) {
        
                    count++;
                }
            }
            return count;
        }
    }

**`这段代码的目的是计算给定键的哈希码并确定它在哈希表中的槽位索引——`**

int hashCode = key.hashCode();
    int slot = (hashMap.size() - 1) & hashCode;
    if (slot == slotIndex) {
        
        count++;
    }

> 1.  `int hashCode = key.hashCode();`：这行代码获取给定键 `key` 的哈希码。`hashCode` 是一个整数值，由键对象的 `hashCode()` 方法返回。哈希码用于唯一标识键对象，并且在哈希表中确定键的存储位置。
> 2.  `int slot = (hashMap.size() - 1) & hashCode;`：这行代码使用位运算将哈希码映射到哈希表的槽位索引。`(hashMap.size() - 1)`  
>     用于获取哈希表的最大索引，然后与哈希码进行按位与操作。这样可以确保索引值在合法范围内（0 到 `hashMap.size() - 1`），并且可以更均匀地分布键值对。
> 3.  `if (slot == slotIndex) { count++; }`：这段代码用于统计特定槽位索引 `slotIndex` 中的键值对数量。如果计算得到的槽位索引与给定的 `slotIndex` 相等，则说明该键值对位于该槽位中，因此 `count` 值加一。
> 
> 通过这段代码，可以了解到如何计算键的哈希码并将其映射到哈希表的槽位索引。在哈希表中，每个槽位存储一定数量的键值对，可以通过计算槽位索引来定位和操作特定的键值对。

在这个示例中，我们创建了一个容量为 16 的 HashMap，并向其中添加了 100 个键值对。然后，我们通过 `countKeyValuePairsInSlot` 方法来计算每个槽位中的键值对数量。

根据上述代码运行的结果，你会发现在容量为 16 的情况下，大多数槽位中都有键值对分布，而不是只有少数几个槽位集中拥有。这样的分布可以帮助减少哈希冲突，并提高查找和插入操作的性能。

请注意，实际的分布情况受多种因素影响，包括键的散列码分布、哈希函数的质量以及键的数量等。示例代码仅用于说明当容量为 2 的倍数时，哈希表中键值对更均匀分布的可能性，具体分布情况还取决于实际的数据和哈希函数的特性。