c++实现hashmap

C++标准库中已经提供了`std::unordered_map`实现哈希表，但是我们也可以手动实现一个简单的哈希表。

#include <iostream>
#include <vector>
#include <list>

class HashMap {
public:
    HashMap(int capacity) : capacity_(capacity) {
        table_.resize(capacity_);
    }

    void put(int key, int value) {
        int index = hash(key);
        for (auto it = table_[index].begin(); it != table_[index].end(); ++it) {
            if (it->first == key) {
                it->second = value;
                return;
            }
        }
        table_[index].push_back({key, value});
    }

    int get(int key) {
        int index = hash(key);
        for (auto it = table_[index].begin(); it != table_[index].end(); ++it) {
            if (it->first == key) {
                return it->second;
            }
        }
        return -1;
    }

    void remove(int key) {
        int index = hash(key);
        for (auto it = table_[index].begin(); it != table_[index].end(); ++it) {
            if (it->first == key) {
                table_[index].erase(it);
                return;
            }
        }
    }

private:
    int hash(int key) {
        return key % capacity_;
    }

    int capacity_;
    std::vector<std::list<std::pair<int, int>>> table_;
};

int main() {
    HashMap map(10);
    map.put(1, 2);
    map.put(11, 22);
    std::cout << map.get(1) << std::endl; // expected output: 2
    std::cout << map.get(11) << std::endl; // expected output: 22
    map.remove(1);
    std::cout << map.get(1) << std::endl; // expected output: -1
    return 0;
}

这里我们使用`std::vector`和`std::list`来存储哈希表，实现了`put()`、`get()`和`remove()`操作。`put()`和`get()`的时间复杂度为$O(1)$，而`remove()`的时间复杂度为$O(k)$，其中$k$为哈希桶中元素的个数。