реализация хэш-таблицы с использованием вектора 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 не подходит для вашей цели или если они недоступны для вас.

Для практических целей, по крайней мере, попробуйте использовать их в первую очередь.