Создать хеш-таблицу, где каждое значение является вектором многих значений - PullRequest
Новая
       30

Создать хеш-таблицу, где каждое значение является вектором многих значений

0 голосов
/ 24 мая 2018

У меня есть следующий файл input.txt, который на самом деле имеет около 150 тыс. Идентификаторов. 

id    element
 0    1
 0    3
 1    0
 1    1
 1    3
 2    2
 2    4
 3    4
 4    1

Я хочу сохранить идентификаторы в виде ключей и значения в векторе, которые содержат значения для каждого идентификатора.Например, в конце я хочу получить хеш-таблицу, которая выглядит следующим образом. 

0 -> 1, 3
1 -> 0, 1, 3
2 -> 2, 4
3 -> 4
4 -> 1

Это мой код: 

#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;
const int TABLE_SIZE = 128;

class HashEntry
{
    public:
        int key;
        vector< int > values;
        HashEntry(int key, int value)
        {
            this->key = key;
            values.push_back(value);
        }
};

class HashMap
{
    private:
        HashEntry **table;
    public:
        HashMap()
        {
            table = new HashEntry * [TABLE_SIZE];
            for (int i = 0; i< TABLE_SIZE; i++)
            {
                table[i] = NULL;
            }
        }
        /*
         * Hash Function
         */
        int HashFunc(int key)
        {
            return key % TABLE_SIZE;
        }

    void Insert(int key, int value)
    {
            int hash = HashFunc(key);
            table[hash] = new HashEntry(key, value);
    }

    void Show(){

        for (int i=0;i<TABLE_SIZE;i++){
            if (table[i]!=NULL){
                cout << table[i]->key << " : ";
                for(int y = 0; y < table[i]->values.size(); y++) {
                    cout << table[i]->values[y];
                }
                cout << endl;
            }
        }
    }
};

int main()
{
    HashMap hash;
    int key, value;
    while (1)
    {
    cout<<"Enter element to be inserted: ";
    cin>>value;
    cout<<"Enter key at which element to be inserted: ";
    cin>>key;
    hash.Insert(key, value);
    hash.Show();
    }
    return 0;
}

В консоли отображается только последний элемент, который явведены и не все значения.Я думаю, что проблема в том, что объект HashEntry инициализируется каждый раз и что его члены инициализируются с самого начала каждый раз.Как я могу сохранить HashEntries "статичным"?

РЕДАКТИРОВАТЬ: Вот мой новый код после следования совету Давиде Спатаро.К сожалению, я не могу использовать C ++ 11, поэтому я немного его изменил.Теперь, что не так? 

void Insert(int key, int value)
    {
            int hash = HashFunc(key);
            //check if we already have an `HashEntry` for key
            HashEntry *p = find(key, table[hash]);
            // if yes simply push the value in that `HashEntry`
            if( p->key == -1 ){
                p->values.push_back(value);
                return;
            }
            else{
                //otherwise add an `HashEntry` to the hashtable for key and push a value in it.
                HashEntry *p = new HashEntry(key, value);
                p->values.push_back(value);
                table[hash] = p;
            }

    }

    HashEntry* find(int key, HashEntry *table)
    {
        for (int i=0;i<TABLE_SIZE;i++)
        {
            if (key == table[i].key)
                return &table[i];
            else return new HashEntry(-1,-1);
        }
    }

1 Ответ

0 голосов
/ 24 мая 2018

Проблема в основном в вашем Insert.Всякий раз, когда вы находите ключ, который хэширует до определенного значения, вы перезаписываете HashEntry, который может быть там, уже создавая новый!Это неправильно и также может привести к утечке памяти.

Вам также необходимо обрабатывать столкновения.В вашей хэш-таблице есть только 128 сегментов и 150k возможных значений ключа.По принципу голубя вы получите более одного HashEntry для одного и того же значения хеш-функции.Ваш код должен справиться с этим.

Что-то вроде следующего должно быть достаточно в качестве отправной точки. 

 void Insert(int key, int value)
    {
            int hash = HashFunc(key);
            //check if we already have an `HashEntry` for key 
            auto p = find(key, table[hash]);
            // if yes simply push the value in that `HashEntry` 
            if( p != nullptr){
                p->values.push_back(value);
                return;
            }else{
               //otherwise add an `HashEntry` to the hashtable for key and push a value in it.
              auto p = new HashEntry(key, value);
              p->values.push_back(value);
              table[hash] = p;
            }

    }

Есть и другие проблемы, такие как правило 3/5/0 упоминается в комментариях, так как вы управляете необработанными указателями.(Вам нужно освободить эту память в какой-то момент, не так ли?)

...