使用矢量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++實現哈希表

回答

相關問題