c++ - 打开哈希，添加元素，使用迭代器查找元素

Question

我有一个使用 STL 的开放哈希表。

typedef std::list<int> LIST;
typedef std::vector<LIST> HASH_TABLE;

我通过用空列表填充来初始化哈希表。

LIST mt_list;
HASH_TABLE hTable;
hTable.assign(7, mt_list);

现在，如果我想根据以下条件将一个 int 添加到我的表中:

hKey = (value*value) % 7;

我用

hTable[hKey].push_back(value);

应该可以吧？我无法让它工作。

void addValue(int value){
    if(val_find(value)){
        std::cout << "WARNING: duplicate input: " << value << std::endl;
    }
    else{
        calc_hash_bucket(value);        //set hKey
        hTable[hKey].push_back(value);  //push value into list
    }
}

上面的代码没有将元素添加到 vector 中的任何列表中。

此外，当我想使用迭代器遍历 vector 和 vector 中的列表时，我如何一次从列表中获取一个元素，以便我可以找到可能已经存在或可能不存在的特定值名单？

这是我在哈希表中查找值的方法:

bool val_find(int value){
    if(mt_hash()){
        return false;
    }
    else{
        for(HASH_ITER h_iter = hTable.begin(); h_iter != hTable.end(); ++h_iter){
            for(LIST_ITER l_iter = h_iter->begin(); l_iter != h_iter->end(); ++l_iter){
                if(*l_iter == value){
                    return true;
                }
            }
        }
    }
    return false;
}

我被难住了。我不明白为什么它不会将值添加到任何列表中。

我觉得我应该提到这一切都在一个头文件中，并且是我创建的类的一部分。 (我不知道这是否重要)

编辑:不打印警告语句。为了回答问题，mt_hash() 函数检查哈希表是否为空，我检查了几次以确保它正确输出。我修复了 hTable_1 与 hTable 的区别，它们是同一回事。我只是在把它放入问题中时忘记更改它。

bool mt_hash(void){    //is hash table empty?
    for(unsigned int i = 0; i < hTable.size(); ++i){
        if(!hTable.at(i).empty()){ //if not empty return false
            return false;
        }
    }
    return true;    //else return true
}

谢谢，扎克

Answer 1

正如 Pradhan 指出的那样，有相当多的缺失。 mt_hash() 的实现是什么？ hTable_1 和hTable 是同一个对象吗？

在下面，我采用了上面的代码，并将它们放在一个包含隐含功能的结构中。注意三个变化: hTable 替换了 val_find() 中的 hTable_1； addValue() 使用局部变量来存储散列键； mt_hash() 是通过保持简单的元素计数来实现的。

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

struct open_hash {
    typedef std::list<int> LIST;
    typedef std::vector<LIST> HASH_TABLE;

    typedef LIST::const_iterator LIST_ITER;
    typedef HASH_TABLE::const_iterator HASH_ITER;

    HASH_TABLE hTable;
    int nbins;
    int elem_count;

    explicit open_hash(int nbins_): nbins(nbins_), elem_count(0) {
        init_hash();
    }

    void init_hash() {
        LIST mt_list;
        hTable.assign(nbins, mt_list);
    }

    int hash_bucket(int value) const {
        return (value*value)%nbins;
    }

    bool mt_hash() const {
        return elem_count==0;
    }

    bool val_find(int value) const {
        if (mt_hash()) {
            return false;
        }
        for (HASH_ITER h_iter = hTable.begin(); h_iter != hTable.end(); ++h_iter){
            for (LIST_ITER l_iter = h_iter->begin(); l_iter != h_iter->end(); ++l_iter){
                if (*l_iter == value) {
                    return true;
                }
            }
        }
        return false;
    }

    void addValue(int value) {
        if (val_find(value)) {
            std::cout << "WARNING: duplicate input: " << value << std::endl;
        }
        else {
            int hKey=hash_bucket(value);
            hTable[hKey].push_back(value);  //push value into list
            ++elem_count;
        }
    }
};

int main() {
    open_hash H(7);
    std::vector<int> vals={3,1,9,2,10,4,3};

    for (int v: vals) {
        H.addValue(v);
    }

    for (int i=1; i<=10; ++i) {
        std::cout << "val_find(" << i << "):\t" << std::boolalpha << H.val_find(i) << "\n";
    }
}

这会产生预期的输出:

WARNING: duplicate input: 3
val_find(1):    true
val_find(2):    true
val_find(3):    true
val_find(4):    true
val_find(5):    false
val_find(6):    false
val_find(7):    false
val_find(8):    false
val_find(9):    true
val_find(10):   true

我怀疑原来的问题出在 addValue() 和 val_find() 引用不同的哈希对象，或者是 mt_hash() 中的问题> 误报该表是空的，而实际上它不是。