使用矢量c执行哈希表++

Question

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

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 
}

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

Answer 1

它可以有相同的散列值几个项目

你只需要像这样定义您的哈希表：

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]);
}

Answer 2

简单实现哈希表的使用指针，以实际条目的向量：

    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;   
}

Answer 3

在哈希表中每个单元配备了一些额外的包装。

如果你的散列允许删除您需要使得细胞可以被标记为“已删除”的状态。这使您的搜索继续寻找即使遇到这种电池，其中有没有实际价值。

因此，一个小区可以有3个状态，占用，空和删除。

您可能还希望将哈希值存储在单元格中。当你来到调整表格，你不需要老调重弹的所有条目这是有用的。

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

这些因素，如果这是一个锻炼，或者如果你发现std::unordered_map / std::unordered_set将不适合于你的目的，或者如果这些都不是提供给您。

对于实际的目的，至少尝试使用这些第一。