c++ - 在leetcode中设计哈希集，代码给出运行时错误

Question

我正在尝试解决有关设计 HashSet 的问题。

Design a HashSet without using any built-in hash table libraries.

To be specific, your design should include these two functions:

add(value): Insert a value into the HashSet.
contains(value) : Return whether the value exists in the HashSet or not.

remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Example:

MyHashSet hashSet = new MyHashSet(); hashSet.add(1);
hashSet.add(2); hashSet.contains(1); // returns true hashSet.contains(3); // returns false (not found) hashSet.add(2);
hashSet.contains(2); // returns true hashSet.remove(2);
hashSet.contains(2); // returns false (already removed)

Note:

All values will be in the range of [1, 1000000]. The number of operations will be in the range of [1, 10000]. Please do not use the built-in HashSet library.

下面的代码在本地运行正常，但是提交失败报错，

Runtime Error Message: reference binding to misaligned address 0x736c61662c657572 for type 'int', which requires 4 byte alignment

Last executed input: ["MyHashSet","add","remove","add","contains","add","remove","add","add","add","add"] [[],[6],[4],[17],[14],[14],[17],[14],[14],[18],[14]]

class MyHashSet { public:
vector<vector<int>> setHash;
MyHashSet() {
    setHash.reserve(10000);
}

void add(int key) {
    int bucket = key % 10000;
    vector<int>::iterator it;
    it = find(setHash[bucket].begin(),setHash[bucket].end(),key);
    if(it == setHash[bucket].end()){
        setHash[bucket].push_back(key);
    }
}

void remove(int key) {
    int bucket = key % 10000;
    vector<int>::iterator it1;
    it1 = find(setHash[bucket].begin(),setHash[bucket].end(),key);
    if(it1 != setHash[bucket].end()){
        int index = distance(it1,setHash[bucket].begin());
        setHash[bucket].erase(setHash[bucket].begin()+index);
    }

}

/** Returns true if this set did not already contain the specified element */
bool contains(int key) {
    int bucket = key % 10000;
    vector<int>::iterator it2;
    it2 = find(setHash[bucket].begin(),setHash[bucket].end(),key);
        if(it2 != setHash[bucket].end()){
            return true;
        }

    return false;
}

};

我怀疑是内存问题。但无法弄清楚，因为我仍在学习 C++ 的基础知识。

Answer 1

如果您的问题是如何修复您的实现，我会听取评论中的建议。

如果您想了解 C++ 并以最佳方式解决问题，我会使用 std::bitset .他们给你定义的输入范围 [1,1000000] 这一事实让我相信他们正在寻找这样的东西。

这可能属于内置哈希表库的范畴，所以 here is a potential implementation .

class MyHashSet {
public:
    void add(int key) {
        flags.set(key);
    }
    void remove(int key) {
        flags.reset(key);
    }
    bool contains(int key) const {
        return flags[key];
    }
private:
    bitset<1000000+1> flags;
};

在我的平台上，这占用了大约 16kB(相对于 10000 个 vector 占用 30kB+)。它还不需要动态内存分配。

如果您认为这是题外话或作弊，请提供 LeetCode 问题的标题/编号，以便我可以使用他们的测试用例来处理您的代码草稿。我现在也在研究哈希表，所以这是双赢的。