Реализация хеш-таблицы (с использованием массивов) - PullRequest
Новая
       37

Реализация хеш-таблицы (с использованием массивов)

0 голосов
/ 10 декабря 2018

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

Для всех моих вызовов функций я создаю "int hi".И используя это для хеширования любых ключей, которые я делаю.Это правильный способ настроить хеш-таблицу?Я не могу найти много руководств, объясняющих, как правильно настроить хеш-таблицу и правильно сопоставить ключи.

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

Ниже приведен код, над которым я работаю. 

#include <iostream>
using namespace std;

class HashTable
{
    struct Element
    {
        string key;
        int mark;
    };
    Element** table;
    int size;

private:
    int hash(string);
    public:
    HashTable(int);
    ~HashTable();
    void insert(string);
    void remove(string);
    bool isFull();
    bool isEmpty();
    void clear();
    void print();
    bool find(string);
};

int HashTable::hash(string s)
{
    return 0;
}

HashTable::HashTable(int s)
{
    int hi;
    table = new Element *[s];
    for (int i = 0; i < size; i++)
    {
        table[hi] = NULL;
    }
}

HashTable::~HashTable()
{
    int hi;
    for (int i = 0; i < size; i++)
    {
        if (table[hi])
        delete table[hi];
    }
    delete[]table;
}

void HashTable::insert(string s)
{
    string key;
    int hi;
    if (!isFull)
    {
        hi = hash(key);
        while (table[hi]->mark == 1)
        {
            hi = (hi + 1) % size;
        }
        table[hi]->key = key;
        table[hi]->mark = 1;
    }
}

void HashTable::remove(string s)
{
    string key;
    int i;
    int hi;
    if (!isEmpty)
    {
        hi = hash(key);
        i = 0;
    }
    while (i < size && table[hi]->mark != 0)
    {
        if (table[hi]->key == key)
        {
            table[hi]->mark = 2;
            break;
        }
        i = i + 1;
        hi = (hi + 1) % size;
    }
}

bool HashTable::isFull()
{
int hi;
if (table[hi] >= size)
{
    return true;
}
}

bool HashTable::isEmpty()
{
    int hi;
    if (table[hi] >= size)
    {
        return true;
    }
}

void HashTable::clear()
{
    int hi;
    for (int i = 0; i < size; i++)
    {
        delete table[hi];
        table[hi] = nullptr;
    }
}

void HashTable::print()
{
    int hi;
    string key;
    for (int i = 0; i < size; ++i)
    {
        if (table[hi]->mark == 2)
        {
            printf("test \n", table[hi]->key);
        }
    }
}

bool HashTable::find(string s)
{
    string key;
    int i;
    int found;
    int hi;
    if (!isEmpty)
    {
        hi = hash(key);
        found = false;
    }
    i = 0;
    while (table[hi]->mark != 0 && (!found) && i < size)
    {
        if (table[hi]->mark == 1 && table[hi]->key == key)
        {
            found = true;
        }
        hi = (hi + 1) % size;
        i = i + 1;
    }
    return found;
}

1 Ответ

0 голосов
/ 10 декабря 2018

Во-первых, давайте исправим ваш конструктор: 

HashTable::HashTable(int s)
{
    table = new Element*[s];
    size = s;                      // you forgot this line
    for (int i = 0; i < size; i++)
    {
        table[i] = NULL;           // "i", not "hi"
    }
}

Вы хотите, чтобы ваша операция хеширования отображала любую уникальную строку в число (по модулю размера массива вашей хеш-таблицы):

Выможет сделать это: 

size_t HashTable::hash(const string& s)
{
    size_t hashvalue = 0;
    for (char ch : s)
    {
        hashvalue += (unsigned)ch;
    }
    return (hashvalue % size);
}

Сам C ++ имеет встроенный алгоритм хеширования, который, вероятно, имеет лучшую диффузию и распределение: 

size_t HashTable::hash(const string& s)
{
    std::hash<string> hasher;
    size_t hi = hasher(s) % size;
    return hi;
}

Это ближе к тому, что вы хотите для элементатип: 

struct Element
{
    string key;
    Element* next;
};

Следовательно, вставка может быть просто такой: 

void insert(const string& key)
{
     size_t hi = hash(key);
     Element* e = Lookup(key);
     if (e == nullptr)
     {
         e = new Element();
         e->key = key;
         e->value = value;
         e->next = table[hi];
         table[hi] = e;
     }
     else
     {
         // item already exists
     }
}

И поиск: 

Element* Lookup(const string& key)
{
    Element* e = nullptr;
    size_t hi = hash(key);
    e = table[hi];
    while (e && e->key != key)
    {
        e = e->next;
    }
    return e;
}

И удаление аналогично операции поиска 

 void HashTable::remove(const string& key)
 {
    size_t hi = hash(key);
    Element* e = table[hi];
    Element* prev = nullptr;
    while (e && e->key != key)
    {
        prev = e;
        e = e->next;
    }
    if (e && prev)
    {
        prev->next = e->next;
        delete e;
    }
    else if (e)
    {
        table[hi] = e->next;
        delete e;
    }      
 }

Я оставлю остальные методы вашего класса в качестве упражнения для вас.

...