Можно ли это назвать хеш-таблицей. Если нет то почему ?

#data_structures #структуры_данных #алгоритм #хеширование #cpp

Почитал кормена и написал хеш-таблицу на основе сцепления элементов. Можно ли это
назвать хеш-таблицей и если нет то почему, какие ошибки есть логические ?
node.hpp
#ifndef NODE_HPP
#define NODE_HPP

template 
class list;

template 
class node
{
    private:
        friend class list;

    private:
        node* m_next;
        node* m_prev;
        T m_data;

    public:
        node() :  m_next(0)
                , m_prev(0)
                , m_data(0) {}

        explicit node(T d) :  m_next(0)
                            , m_prev(0)
                            , m_data(d) {}
        T get_data()
        {
            return m_data;
        }
};

#endif // NODE_HPP

list.hpp
#ifndef LIST_HPP
#define LIST_HPP

#include 
#include 

#include "node.hpp"

template 
class list
{
    private:
        node* m_head;
        node* m_tail;
        unsigned m_size;

    public:
        list() :   m_size(0) 
                 , m_head(0)
                 , m_tail(0){}

        node* get_new_node(T d) const;
        node* find(T data) const;
        void insert_at_front(T data);
        void insert_at_back(T data);
        void delete_at_front();
        void delete_at_back();
        bool is_empty() const;
        void print() const;
        node* get_begin() const
        {
            return m_head;
        }
        node* get_end() const
        {
            return m_tail;
        }
        unsigned get_size() const
        {
            return m_size;
        }
};

template 
node* list::get_new_node(T data) const 
{
    node* n = new node(data);
    assert(n != 0);
    return n;
}

template 
bool list::is_empty() const
{
    if(m_head == 0)
    {
        return true;
    }
    return false;
}

template 
void list::print() const 
{
    if(is_empty())
    {
        return;
    }
    node* t = m_head;
    while(t != 0)
    {
        std::cout << t->m_data << " ";
        t = t->m_next;
    }
}

template 
node* list::find(T data) const
{
    if(is_empty())
    {
        return 0;
    }
    node* t = m_head;
    while(t != 0 && t->m_data != data)
    {
        t = t->m_next;
    }
    return t;
}

template 
void list::insert_at_front(T data)
{
    node* n = get_new_node(data);
    if(m_head == 0)
    {
        m_head = m_tail = n;
        n->m_next = n->m_prev = 0;
        ++m_size;
    }
    else
    {
        n->m_next = m_head;
        if(m_head != 0)
        {
            m_head->m_prev = n;
        }
        m_head = n;
        n->m_prev = 0;
        ++m_size;
    }
}

template 
void list::insert_at_back(T data)
{
    node* n = get_new_node(data);
    if(m_tail == 0)
    {
        m_head = m_tail = n;
        n->m_next = n->m_prev = 0;
        ++m_size;
    }
    else
    {
        m_tail->m_next = n;
        n->m_prev = m_tail;
        m_tail = n;
        ++m_size;
    }

}

template 
void list::delete_at_front()
{
    if(is_empty())
    {
        return;
    }
    else
    {
        node* t = m_head->m_next;
        t->m_prev = 0;
        delete m_head;
        m_head = t;
        --m_size;
    }
}

template 
void list::delete_at_back()
{
    if(is_empty())
    {
        return;
    }
    else
    {
        node* t = m_tail->m_prev;
        t->m_next = 0;
        delete m_tail;
        m_tail = t;
        --m_size;
    }
}

#endif // LIST_HPP

hash_table.hpp
#ifndef HASH_TABLE_HPP
#define HASH_TABLE_HPP

#include "list.hpp"

template 
class hash_table
{
    private:
        list** m_table;
        unsigned m_size;

    private:
        int get_hash(int key);

    public:
        explicit hash_table(unsigned);
        T find(const T&, const T&); 
        void insert(const T&, unsigned);
        void remove(const T&);
};

template 
hash_table::hash_table(unsigned size)
{
    m_size = size;
    m_table = new list*[m_size];
    for(int i = 0; i < m_size; ++i)
    {
        m_table[i] = new list();
    }
}

template 
int hash_table::get_hash(int key)
{
    return (key % m_size);
}

template 
T hash_table::find(const T& d, const T& i)
{
    int h = get_hash(i);
    node* n = m_table[h]->find(d);
    assert(n != 0);
    return n->get_data();
}

template 
void hash_table::insert(const T& d, unsigned key)
{
    unsigned h = get_hash(key);
    m_table[h]->insert_at_front(d);
}

#endif // HASH_TABLE_HPP

Поправил код find(...)
template 
T hash_table::find(const T& i)
{
    int h = get_hash(i);
    if(m_table[h]->get_begin() != 0)
    {
        return m_table[h]->get_begin()->get_data();
    }
    return 0;
}

но так получается что функция всегда возвращает только голову списка а если есть
коллизия то этот случай не учитывается ... ?    

Ответы

Ответ 1

Есть несколько замечаний по реализации:




Непонятна сигнатура find(T, T). Почему не find(Key)?


Непонятно ваше разделение  для элементов хэш-таблицы. То есть, сигнатуры
методов должны выглядеть как insert(Key, Value) / find(Key) / remove(Key), либо как
insert(Value) / find(Value) / remove(Value) для случая, когда в хэш-таблице хранятся
не пары ключ-значение, а сами значения. Других вариантов нет.


Не предложена имплементация remove(T). Вместо траты времени на реализацию своего
std::list, лучше бы уж написали метод удаления элементов из хэш-таблицы.


Крайне странное решение, в котором вызов функции find() coredump'ится в случае отсутствующего
в хэш-таблице значения.


Вообще, предложенный код, за исключением последних пятнадцати строчек, не имеет к
хэш-таблицам никакого отношения, а просто предлагает какой-то неочевидный способ реализации
аналога std::list. Решение с наследованием node ← list, кстати, кажется очень
странным.




А так, ну да, обычная хэш-таблица с chaining'ом для резолвинга коллизий.


Ответ 2

Похоже, что да, это может быть хэш таблицей. Для начала читаем определение с википедии: 
Хеш-табли́ца — это структура данных, реализующая интерфейс ассоциативного массива,
а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию
добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Все эти три операции я  вижу. Правда было бы  не плохо перегрузить operator [] (что
бы реализовать интерфейс "массива").
Меня  только смущает порядок параметров в функции вставки. Я думаю, ключ должен идти
первым.
Обязательно напишите тестовые примеры и проверьте, что бы Ваша таблица работала как
нужно.