如何实现哈希表？

哈希表是一种存储键值对的数据结构,它通过把键映射到表中一个位置来进行快速检索。

我们可以使用链地址法实现一个哈希表:

public class HashTable {
    private int capacity;   // 哈希表容量
    private LinkedList<Node>[] table;  // 哈希表数组

    public HashTable(int capacity) {
        this.capacity = capacity;
        table = new LinkedList[capacity];
    }

    public void put(int key, int val) {
        int hash = key % capacity;   // 哈希函数
        if (table[hash] == null) table[hash] = new LinkedList<>();  // 链表为空则初始化

        Node node = search(key);     // 查找键是否已经存在
        if (node != null) node.val = val;    // 如果存在则更新值
        else table[hash].add(new Node(key, val)); // 若不存在则新增节点
    }

    public int get(int key) {
        int hash = key % capacity;
        if (table[hash] != null) {
            Node node = search(key);
            if (node != null) return node.val;
        }

        return -1;   // 如果不存在则返回-1
    }   

    private Node search(int key) {
        int hash = key % capacity;
        if (table[hash] != null) { 
            for (Node node : table[hash]) {
                if (node.key == key) return node;  // 遍历链表查找键
            }
        }

        return null;   // 如果不存在则返回null
    }
}

所以,哈希表的实现步骤为:

1. 确定哈希表的容量 capacity,默认为素数。
2. 使用链地址法,将键值对存储在链表数组 table 中。
3. 定义一个简单的哈希函数,比如取余法。
4. put 操作:先计算键的哈希值,如果对应链表为空则初始化。如果键已存在则更新值,否则新增节点。
5. get 操作:先计算键的哈希值,然后在对应链表中查找键。如果找到则返回值,否则返回 -1。
6. search 方法用于在链表中查找键,找到则返回节点,否则返回 null。
7. 链表在第一个节点插入时初始化,避免每次插入前都判断是否为空。