Java手写HashMap及拓展实践

Java手写HashMap

思维导图

上述思维导图展示了Java手写HashMap的实现思路。HashMap是一种常用的数据结构，用于存储键值对。它的底层是由数组和链表组成的。数组用于存储数据，链表用于解决哈希冲突。在HashMap中，每个键值对通过哈希函数计算出一个哈希值，然后根据哈希值找到对应的数组位置，如果该位置已经有其他键值对存在，就使用链表将新的键值对添加到该位置的链表末尾。

实现步骤

1. 定义HashMap类

首先，我们需要定义一个HashMap类，用于存储键值对。

public class HashMap<K, V> {
    // 实现代码
}
1
2
3

2. 定义数组和链表

在HashMap类中，我们需要定义一个数组和一个链表。

private Node<K, V>[] table; // 数组
private static final int DEFAULT_CAPACITY = 16; // 默认数组大小

static class Node<K, V> {
    final K key;
    V value;
    Node<K, V> next;
    
    Node(K key, V value) {
        this.key = key;
        this.value = value;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

数组table用于存储键值对，链表Node用于解决哈希冲突。在链表中，每个节点包含一个键值对，以及指向下一个节点的指针。

3. 实现哈希函数

在HashMap中，我们需要实现一个哈希函数，用于计算键值对的哈希值。

private int hash(K key) {
    return key.hashCode() % table.length;
}
1
2
3

哈希函数使用hashCode()方法计算键值对的哈希值，然后使用取模运算将哈希值映射到数组的索引位置。

4. 实现put方法

接下来，我们需要实现put方法，用于向HashMap中添加键值对。

public void put(K key, V value) {
    int index = hash(key);
    Node<K, V> newNode = new Node<>(key, value);
    
    if (table[index] == null) {
        table[index] = newNode;
    } else {
        Node<K, V> current = table[index];
        while (current.next != null) {
            if (current.key.equals(key)) {
                current.value = value;
                return;
            }
            current = current.next;
        }
        current.next = newNode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

put方法首先计算键值对的哈希值，然后根据哈希值找到对应的数组位置。如果该位置为空，则直接将新的节点添加到该位置。如果该位置已经有其他节点存在，则遍历链表，查找是否有相同的键。如果有相同的键，则更新对应的值，否则将新的节点添加到链表的末尾。

5. 实现get方法

我们还需要实现get方法，用于根据键获取对应的值。

public V get(K key) {
    int index = hash(key);
    
    if (table[index] == null) {
        return null;
    } else {
        Node<K, V> current = table[index];
        while (current != null) {
            if (current.key.equals(key)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

get方法首先计算键的哈希值，然后根据哈希值找到对应的数组位置。如果该位置为空，则返回null。如果该位置有节点存在，则遍历链表，查找是否有相同的键。如果找到相同的键，则返回对应的值，否则返回null。

总结

通过手写HashMap的实现，我们加深了对HashMap的理解，并提高了编程能力。HashMap是一种常用的数据结构，它的底层是由数组和链表组成的，通过哈希函数将键值对映射到数组的索引位置，用链表解决哈希冲突。实现HashMap需要考虑哈希函数、数组和链表的操作，以及处理哈希冲突的方式。掌握HashMap的实现原理和实现步骤对于编程能力的提升是非常有帮助的。

拓展

除了基本的put和get操作，我们还可以实现其他功能，比如删除键值对、获取HashMap的大小等。删除键值对的操作比较简单，只需要找到对应的键，然后删除节点即可。获取HashMap的大小可以遍历数组，并统计每个位置的链表长度。另外，我们还可以实现自动扩容的功能，当HashMap中的键值对数量超过数组大小的75%时，自动扩容数组的大小。实现自动扩容需要创建一个新的更大的数组，并将原数组中的键值对重新计算哈希值，然后添加到新的数组中。

拓展实践

当HashMap中的键值对数量超过数组大小的75%时，我们可以通过自动扩容来提高HashMap的性能。下面是实现自动扩容的代码：

public void put(K key, V value) {
    int index = hash(key);
    Node<K, V> newNode = new Node<>(key, value);
    
    if (table[index] == null) {
        table[index] = newNode;
    } else {
        Node<K, V> current = table[index];
        while (current.next != null) {
            if (current.key.equals(key)) {
                current.value = value;
                return;
            }
            current = current.next;
        }
        current.next = newNode;
    }
    
    size++;
    
    if ((double) size / table.length > 0.75) {
        resize();
    }
}

private void resize() {
    int newCapacity = table.length * 2;
    Node<K, V>[] newTable = new Node[newCapacity];
    
    for (int i = 0; i < table.length; i++) {
        Node<K, V> current = table[i];
        while (current != null) {
            int newIndex = current.key.hashCode() % newCapacity;
            Node<K, V> newNode = new Node<>(current.key, current.value);
            
            if (newTable[newIndex] == null) {
                newTable[newIndex] = newNode;
            } else {
                Node<K, V> newCurrent = newTable[newIndex];
                while (newCurrent.next != null) {
                    newCurrent = newCurrent.next;
                }
                newCurrent.next = newNode;
            }
            
            current = current.next;
        }
    }
    
    table = newTable;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

在put方法中，我们首先判断当前HashMap的大小是否超过了数组大小的75%。如果是，则调用resize方法进行扩容。resize方法首先创建一个新的更大的数组newTable，然后遍历原数组table，将每个键值对重新计算哈希值，并添加到新的数组中。最后，将新的数组赋值给table。

通过自动扩容，我们可以保证HashMap的性能在一定范围内。当HashMap中的键值对数量超过数组大小的75%时，我们将数组的大小扩大一倍，从而减少哈希冲突的概率，提高查找效率。