固定大小散列映射的实现

Question

我试图仔细研究我的算法和数据结构，并编写了一个固定大小的散列图，假设键和值都是整数。这是对实际情况的重大简化，应该是这样的。任何关于bug、最佳实践、风格的评论都很受欢迎。

#include <vector>
#include <iostream>
#include <exception>
#include <stdexcept>
#include <assert.h>
#define SIZE 10

class HashEntry {
public:
    int _k;
    int _v;
    HashEntry(int k, int v) : _k(k), _v(v) {};
};

class HashMap {
private:
    std::vector<HashEntry> buckets[SIZE];
    int hashFunc(int key);
    std::vector<HashEntry>& getBucket(int key);

public:
    bool keyExists(int k);
    HashEntry get(int k);
    bool put(int k, int v);
    bool remove(int k);
};

int HashMap::hashFunc(int key) {
    return key % SIZE;
}

std::vector<HashEntry>& HashMap::getBucket(int key) {
    if (key < 0) {
        throw std::runtime_error("key should be >= 0");
    }
    return buckets[hashFunc(key)];
}

HashEntry HashMap::get(int k) {
    std::vector<HashEntry>& bucket = getBucket(k);
    for (HashEntry entry : bucket) {
        if (entry._k == k) {
            return entry;
        }
    }
    throw std::runtime_error("Key not found");
}
bool HashMap::keyExists(int k) {
    std::vector<HashEntry>& bucket = getBucket(k);
    for (HashEntry entry : bucket) {
        if (entry._k == k) {

            // key already exists
            return true;
        }
    }
    return false;
}

bool HashMap::put(int k, int v) {
    std::vector<HashEntry>& bucket = getBucket(k);
    if (keyExists(k)) return false;
    bucket.push_back(HashEntry(k, v));
    return true;
}

bool HashMap::remove(int k) {
    std::vector<HashEntry>& bucket = getBucket(k);
    if (!(keyExists(k))) return false;
    for (auto itr = bucket.begin(); itr != bucket.end(); ++itr) {
        HashEntry entry = static_cast<HashEntry>(*itr);
        if (entry._k == k) {
            bucket.erase(itr);
            return true;
            break;
        }
    }
    return false;
}

int main() {
    HashMap map;
    for (int i=0; i < 10; ++i) {
        assert(map.put(i, i*10));
    }
    for (int i=0; i < 10; ++i) {
        assert(map.keyExists(i) == true);
    }
    assert(map.keyExists(0) == true);
    assert(map.get(0)._v == 0);
    assert(map.remove(0) == true);
    assert(map.remove(0) == false);
    assert(map.keyExists(0) == false);

    bool exceptionThrown = false;
    try {
        map.get(0);
    } catch (std::exception &e) {
        exceptionThrown = true;
    };
    assert(exceptionThrown);
    return 1;
}

Answer 1

科尔宾给出了一个相当全面的答案。

不过，我立即注意到的部分是可访问的HashEntry类，以及它是如何通过使用get()方法泄漏的。

散列是键到值的映射。您的put方法是bool put(int,int)，对称的是，get应该是int get(int)

get返回不应该释放的HashEntry。因为你这样做，人们可能会搞砸你的条目，因为_k和_v也是公开的。

get应该返回int，并且您应该建立一个协议，允许您确定密钥是否不存在(返回0?)或者它是否存在( keyExists(int)可以是一个双重检查)。