使用矢量C++实现哈希表

我试着用矢量实现哈希表。我的表规模将在构造函数中定义，例如让说表的大小为31，创建哈希表我做如下：使用矢量C++实现哈希表

vector<string> entires; // it is filled with entries that I'll put into hash table; 
vector<string> hashtable; 
hashtable.resize(31); 
for(int i=0;i<entries.size();i++){ 
    int index=hashFunction(entries[i]); 
    // now I need to know whether I've already put an entry into hashtable[index] or not 
}

有没有人帮我，我怎么能做到这一点？

来源

2014-01-22 TheGost

这是你的真实密码？我可以发现至少2个错误（一个丢失的右括号和你拼错的条目） – Borgleader

@Borgleader nope我只是写了一些简单的一部分。对于错别字 – TheGost

@TheGost检查是否散列表[索引] .empty（）'？我不明白你是如何计划用矢量实现一个哈希表的。你会做什么2个不同的条目散列到相同的索引？ – Praetorian

有可能有相同的散列值

你只需要确定你的哈希表这样几项：

vector<vector<string>> hashtable; 
hashtable.resize(32); //0-31 

for(int i=0;i<entries.size();i++){ 
    int index=hashFunction(entries[i]); 
    hashtable[index].push_back(entries[i]); 
}

来源

2014-01-22 18:59:55 SHR

不，如果有条目，我将使用线性探测冲突解决策略，因此在同一位置不能有多个条目 – TheGost

因此看起来您需要使用默认值作为空值（如果为空字符串对此不好） – SHR

谢谢，我也决定这样做 – TheGost

简单实现哈希表的使用指针的向量实际项：

class hash_map { 
    public: 
    iterator find(const key_type& key); 
    //... 
    private: 
    struct Entry { // representation 
     key_type key; 
     mepped_type val; 
     Entry* next; // hash overflow link 
    }; 

    vector<Entry> v; // the actual entries 
    vector<Entry*> b; // the hash table, pointers into v 
    };

找到一个值运营商使用哈希函数查找在哈希表中的索引键：

mapped_type& hash_map::operator[](const key_type& k) { 
    size_type i = hash(k)%b.size(); // hash 
    for (Entry* p=b[i];p;p=p->next) // search among entries hashed to i 
    if (eq(k,p->key)) { // found 
     if (p->erased) { // re-insert 
     p->erased=false; 
     no_of_erased--; 
     return p->val=default_value; 
    } 
    // not found, resize if needed 
    return operator[](k); 
    v.push_back(Entry(k,default_value,b[i])); // add Entry 
    b[i]=&v.back(); // point to new element 

    return b[i]->val; 
}

来源

2014-01-22 19:07:20 4pie0

散列表中的每个单元格都带有一些额外的包装。

如果你的散列允许删除，你需要一个状态，使一个单元格可以被标记为“已删除”。这使您的搜索可以继续查找，即使它遇到没有实际值的单元格。

所以一个单元格可以有3个状态，占用，清空和删除。

您可能还希望将散列值存储在单元格中。当您调整表格的大小时，这很有用，因为您不需要重新扫描所有条目。

此外，它可以是一个最佳的第一比较，因为比较两个数字可能比比较两个对象更快。

这些是考虑事项，如果这是一个练习，或者如果您发现std::unordered_map/std::unordered_set是不适合您的目的或如果这些不提供给你。

出于实用目的，至少应该先尝试使用那些。

来源

2014-01-22 19:20:38 CashCow

使用矢量C++实现哈希表

回答

相关问题