Java编程进阶：小白也能手写HashMap代码

前言

HashMap 是 Java 中常用的数据结构之一，它可以用于键值对存储和快速查找。虽然 Java 提供了 HashMap 的实现，但是手写 HashMap 算是 Java 编程基本功之一。本文将向大家介绍手写 HashMap 的完整攻略。

原理概述

Java 中 HashMap 是由数组和链表构成的，其主要原理是将 key 的 hashCode 计算出数组下标，如果该位置没有元素则直接插入，如果该位置已经有元素，则用链表的形式同步保存新的元素。

代码实现

下面我们来实现一个简单的 HashMap，代码清晰易懂。

public class MyHashMap<K, V> {

    private static final int INIT_CAPACITY = 16;

    private static final float LOAD_FACTOR = 0.75f;

    private int size;

    private int threshold;

    private Entry<K, V>[] table;

    public MyHashMap() {
        table = new Entry[INIT_CAPACITY];
        threshold = (int) (INIT_CAPACITY * LOAD_FACTOR);
    }

    static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public void put(K key, V value) {
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            if (e.key.equals(key)) {
                e.value = value;
                return;
            }
        }
        addEntry(key, value, hash, i);
    }

    public V get(K key) {
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K, V> e = table[i]; e != null; e = e.next) {
            if (e.key.equals(key)) {
                return e.value;
            }
        }
        return null;
    }

    private int indexFor(int h, int length) {
        return h & (length - 1);
    }

    private int hash(K key) {
        return key.hashCode();
    }

    private void addEntry(K key, V value, int hash, int bucketIndex) {
        Entry<K, V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(key, value);
        table[bucketIndex].next = e;
        size++;
        if (size >= threshold) {
            resize(table.length * 2);
        }
    }

    private void resize(int newCapacity) {
        Entry<K, V>[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity >= 1 << 30) {
            threshold = Integer.MAX_VALUE;
            return;
        }
        Entry<K, V>[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int) (newCapacity * LOAD_FACTOR);
    }

    @SuppressWarnings("unchecked")
    private void transfer(Entry<K, V>[] newTable) {
        Entry<K, V>[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K, V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K, V> next = e.next;
                    int i = indexFor(e.key.hashCode(), newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }
}

示例说明

下面我们利用前面的 HashMap 实现，进行两个操作进行说明：

1. 存放一个键为"name", 值为"张三"的元素
2. 根据 key "name" 获取相应的值

public class Test {
    public static void main(String[] args) {
        MyHashMap<String, String> map = new MyHashMap<>();
        map.put("name", "张三");
        String name = map.get("name");
        System.out.println(name); // 输出"张三"
    }
}

总结

手动实现 HashMap 需要对 HashMap 的实现原理熟悉，以及对数组和链表处理的掌握，本文大概介绍了 HashMap 的实现原理，并提供了一个 Java 实现示例供大家导入使用或对其进行学习、修改等操作。