为什么jdk1.8之前HashMap是由List+链表组成？

贺公子之数据科学与艺术

发布于 2025-08-29 16:09:50

2080

在jdk1.8之前，Java中的HashMap实现是由数组+链表的方式组成的。这样的设计是为了解决冲突问题，即当两个不同的键值映射到数组的同一个位置时，需要通过链表将它们连接起来。

优点：

实现简单：使用链表的方式可以方便地处理冲突问题，实现相对简单。
空间利用率高：链表的插入和删除操作相对高效，可以更好地利用内存空间。

缺点：

查找效率低：由于链表只能顺序查找，当需要查找特定键值对时，需要遍历整个链表，效率较低。
遇到长链表时性能下降：如果链表过长，会导致插入和查找操作的性能下降，因为需要遍历整个链表。

链表是由一系列节点组成的数据结构，每个节点包含一个数据元素和一个指向下一个节点的指针。链表的特点是插入和删除操作比较高效，但是查找操作需要遍历整个链表。

代码实现

在JDK1.8之前，HashMap是由数组+链表的形式实现的。下面是一个简单的代码示例：

import java.util.LinkedList;

public class HashMapBeforeJDK1_8<K, V> {
    private LinkedList<Pair<K, V>>[] buckets;
    private int capacity;
    
    public HashMapBeforeJDK1_8(int capacity) {
        this.capacity = capacity;
        buckets = new LinkedList[capacity];
    }
    
    public void put(K key, V value) {
        int index = indexForKey(key);
        if (buckets[index] == null) {
            buckets[index] = new LinkedList<>();
        }
        
        LinkedList<Pair<K, V>> bucket = buckets[index];
        
        Pair<K, V> newPair = new Pair<>(key, value);
        for (Pair<K, V> pair : bucket) {
            if (pair.getKey().equals(key)) {
                pair.setValue(value);
                return;
            }
        }
        
        bucket.add(newPair);
    }
    
    public V get(K key) {
        int index = indexForKey(key);
        LinkedList<Pair<K, V>> bucket = buckets[index];
        
        if (bucket != null) {
            for (Pair<K, V> pair : bucket) {
                if (pair.getKey().equals(key)) {
                    return pair.getValue();
                }
            }
        }
        
        return null;
    }
    
    private int indexForKey(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }
    
    private static class Pair<K, V> {
        private K key;
        private V value;
        
        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }
        
        public K getKey() {
            return key;
        }
        
        public V getValue() {
            return value;
        }
        
        public void setValue(V value) {
            this.value = value;
        }
    }
}

在这个示例中，HashMapBeforeJDK1_8类使用一个数组来表示HashMap的桶，每个桶是一个LinkedList<Pair<K, V>>类型的链表。put()方法用于向HashMap中添加键值对，get()方法用于根据键获取对应的值。indexForKey()方法用于计算键的哈希值并映射到对应的桶。Pair<K, V>是一个简单的键值对类，用于存储键值对的数据。