Почитал кормена и написал хеш-таблицу на основе сцепления элементов. Можно ли это назвать хеш-таблицей и если нет то почему, какие ошибки есть логические ?
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;
}
но так получается что функция всегда возвращает только голову списка а если есть коллизия то этот случай не учитывается ... ?
Ответ
Есть несколько замечаний по реализации:
Непонятна сигнатура 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'ом для резолвинга коллизий.
Комментариев нет:
Отправить комментарий