HashMap的实现原理

￡神魔★判官ぃ 2024-04-24 23:01 77阅读 0赞

`HashMap` 是 Java 中的一个集合类，用于存储键值对。它是基于哈希表的 Map 接口的非同步实现。下面我将详细解释其实现原理，包括源码中的关键部分，并且通过代码演示来揭示其工作细节。

#### 实现原理： ####

1.  **数据结构**:  
    `HashMap` 在 Java 中使用数组+链表+红黑树的复合数据结构。数组用于快速访问，链表用于解决哈希冲突，红黑树用于优化链表过长时的查找效率。
2.  **哈希函数**:  
    当我们向 `HashMap` 添加一个键值对时，它首先会使用 `hash()` 方法计算键的哈希码，这个哈希码决定了该键值对在数组中的存储位置。
3.  **哈希冲突解决**:  
    如果两个不同的键有相同的哈希码（哈希冲突），`HashMap` 会使用链表来存储这些键值对。如果链表中的元素个数超过一定的阈值（默认为8），链表会被转换为红黑树，以减少搜索时间。
4.  **动态扩容**:  
    当 `HashMap` 中的元素超过容量与加载因子的乘积时，会发生扩容，即创建一个新的更大的数组，并将所有现有的数据迁移到新数组中。

#### 源码分析： ####

以下是基于Java 8的 `HashMap` 的简化代码，以展示其核心实现：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
        
    
        // 默认的初始容量是16
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 
    
        // 最大容量
        static final int MAXIMUM_CAPACITY = 1 << 30;
    
        // 默认的填充因子
        static final float DEFAULT_LOAD_FACTOR = 0.75f;
    
        // 存储元素的数组
        transient Node<K,V>[] table;
    
        // 存储元素的个数
        transient int size;
    
        // 下一次扩容的大小
        int threshold;
    
        // 填充因子
        final float loadFactor;
    
        // 内部类 Node，用于实现链表
        static class Node<K,V> implements Map.Entry<K,V> {
        
            final int hash;
            final K key;
            V value;
            Node<K,V> next;
    
            Node(int hash, K key, V value, Node<K,V> next) {
        
                this.hash = hash;
                this.key = key;
                this.value = value;
                this.next = next;
            }
    
            // ... 还有 Getter 和 Setter 方法
        }
    
        // 构造方法
        public HashMap(int initialCapacity, float loadFactor) {
        
            this.loadFactor = loadFactor;
            this.threshold = tableSizeFor(initialCapacity);
        }
    
        // ... 其他方法
    
        // 添加键值对的方法
        public V put(K key, V value) {
        
            return putVal(hash(key), key, value, false, true);
        }
    
        // 根据键计算哈希值的方法
        static final int hash(Object key) {
        
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        }
    
        // 核心的 put 方法
        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);
            else {
        
                Node<K,V> e; K k;
                if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
        
                    for (int binCount = 0; ; ++binCount) {
        
                        if ((e = p.next) == null) {
        
                            p.next = newNode(hash, key, value, null);
                            if (binCount >= TREEIFY_THRESHOLD - 1)
                                treeifyBin(tab, hash);
                            break;
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;
                        p = e;
                    }
                }
                if (e != null) {
         // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++size;
            if (size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }
    
        // ... 更多方法，如 resize、treeifyBin 等
    }

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

HashMap<Integer, String> map = new HashMap<>();
    map.put(1, "a"); // 将键值对(1, "a")放入HashMap中
    map.put(2, "b"); // 将键值对(2, "b")放入HashMap中
    map.put(1, "c"); // 更新键1的值，现在键值对为(1, "c")
    
    String value = map.get(1); // 得到键1对应的值 "c"

在上面的代码中，当我们调用 `put` 方法时，它首先计算键的哈希值，在数组中找到存储的位置，然后根据情况插入新节点或者更新现有节点的值。当数组的大小超过阈值时，`resize` 方法会被调用，以此来保证 `HashMap` 的性能。

需要注意的是，以上的代码和解释是简化的版本，真实的 `HashMap` 实现要复杂得多，包括许多细节处理，例如如何确保并发访问的安全性（在 `ConcurrentHashMap` 中），如何减少哈希碰撞的可能性，以及如何优化性能等。