HashMap的寻址算法和数组长度为什么是2的n次方幂

我不是女神ヾ 2024-04-24 23:01 1阅读 0赞

HashMap的寻址算法以及数组长度选择为2的幂次方设计，都是为了实现快速定位元素和优化哈希碰撞的处理。下面将详细解释这两个方面。

#### 寻址算法： ####

HashMap的寻址算法使用键对象的`hashCode()`方法生成的哈希码，然后通过额外的哈希函数来处理这个原始哈希码，以减少碰撞。在Java 8及以后的实现中，该哈希函数通过将哈希码的高16位与低16位进行异或来实现，这样可以在数组索引计算中利用整个哈希码的位信息，从而提高键在数组中分布的均匀性。

#### 数组长度为2的n次方的原因： ####

1.  **均匀分布**:  
    使用2的幂次方作为数组长度，结合哈希码的高位和低位信息，可以帮助键更均匀地分布在数组中。如果数组长度不是2的幂次方，那么计算索引的时候就可能无法充分利用哈希码的所有位信息，从而导致不均匀的分布和更多的哈希碰撞。
2.  **寻址效率**:  
    当数组长度是2的幂次方时，计算索引的操作可以简化为一个位掩码操作。例如，如果数组长度是16（即2的4次方），那么只需要取哈希码的低4位即可。这通过哈希码与数组长度减一的值进行按位与操作来实现。位操作比取模操作要快得多，因此可以提高寻址效率。
3.  **扩容简化**:  
    在扩容过程中，如果数组长度是2的幂次方，存在一个很好的特性：一个元素在旧数组和新数组中的位置要么是一样的，要么是旧位置加上旧数组长度。这主要是因为新数组的长度是旧数组长度的两倍，因此新数组长度的二进制表示在旧数组长度的二进制表示的基础上多了一位1。

#### 源码解析： ####

以下是相关的源码片段，简化并注释以便理解：

// JDK 8 中 HashMap 的哈希函数，它通过异或其高位和低位来减少哈希碰撞
    static final int hash(Object key) {
        
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    
    // JDK 8 中 HashMap 的 put 方法，它通过与长度减一的值（这是一个全为1的位掩码）进行按位与运算来得出索引
    public V put(K key, V value) {
        
        return putVal(hash(key), key, value, false, true);
    }
    
    // putVal 方法中计算索引的部分，使用位掩码
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 通过位掩码来计算索引
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        // ..后续的代码处理已有元素的情况
    }
    
    // resize 方法中处理元素重新分配的部分
    Node<K,V>[] resize() {
        
        // ...
        if (oldTab != null) {
        
            for (int j = 0; j < oldCap; ++j) {
        
                // ...
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else {
        
                    // ...
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
        
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
        
                            // ...
                        }
                        else {
        
                            // ...
                        }
                    } while ((e = next) != null);
                    // ...
                }
            }
        }
        // ...
    }

#### 代码演示： ####

以下是一个简单的代码示例，演示了如何通过HashMap的put方法添加元素，并说明了数组长度为2的幂次方的好处。

import java.util.HashMap;
    import java.util.Map;
    
    public class HashMapExample {
        
        public static void main(String[] args) {
        
            HashMap<Integer, String> map = new HashMap<>();
    
            // 假设HashMap的当前容量为16（2的4次幂）
            map.put(3, "Three");
            map.put(19, "Nineteen");
    
            // 演示计算索引的过程
            for (Map.Entry<Integer, String> entry : map.entrySet()) {
        
                int hash = hash(entry.getKey());
                int index = (16 - 1) & hash;
                System.out.println("Key: " + entry.getKey() + " - Hash: " + hash + " - Index: " + index);
            }
        }
    
        static final int hash(Object key) {
        
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    }

在这个例子中，我们可以看到即使key的值是3和19，它们的索引是一样的，因为它们的哈希码的低4位相同。由于数组长度是2的幂次方，计算索引时只需要哈希码的低位。