В уездном городе N проводился конкурсный отбор и было дано задание: "реализовать хеш-таблицу". Задание, вроде, несложное, но я не прошёл. Комментариев никаких дано не было, но очень хотелось бы получить обратную связь. Буду рад абсолютно любым комментариям по любому поводу, занудствовать разрешается!
// Реализация хеш-таблицы через остаток от деления
// Добавление и поиск элементов осуществлятся через имя (name). В реальных условиях
// такая таблица будет иметь много коллизий, но, поскольку задание является тестовым,
// я избрал самый простой, быстрый и наглядный метод реализации.
#include
#define PRIME_SIZE 29 // Использовано просто число
using namespace std;
class Person // Класс, который содержит немного информации о человеке.
{
public:
Person *next; // При возникновении коллизии элементы будут помещены в односвязный список.
string name;
string surname;
int age;
Person()
{
this->next = NULL;
}
Person (string name, string surname, int age = 0)
{
this->name = name;
this->surname = surname;
this->age = age;
this->next = NULL;
}
~Person()
{
//cout << "Delete " << this->name << endl;
if ( this->next != NULL )
{
delete this->next;
}
}
};
class HashTable // Хеш-таблица, представленная в виде массива элементов (которые в свою очередь представляют список).
{
Person *table[PRIME_SIZE];
// Самая простоя хеш-функция. Считает сумму ASCII кодов, делит на константу и
// получает остаток от деления.
static int hash ( string str )
{
int asciisum = 0;
for ( int i = 0; i < str.length(); i++ )
{
asciisum += str[i];
}
return asciisum % PRIME_SIZE;
}
public:
HashTable()
{
for ( int i = 0; i < PRIME_SIZE; i++ )
{
table[i] = NULL;
}
}
~HashTable()
{
//cout << "Delete table
";
for ( int i = 0; i < PRIME_SIZE; i++ )
{
delete table[i];
}
}
// Вставляет элемент в таблицу
void push ( string name, string surname, int age )
{
int hashNumber = hash(name);
Person *pers = new Person(name, surname, age);
Person *place = table[hashNumber];
if ( place == NULL )
{
table[hashNumber] = pers;
return;
}
while ( place->next != NULL )
{
place = place->next;
}
place->next = pers;
}
// Получает элемент из таблицы по его имени.
Person* find ( string name )
{
int hashNumber = hash ( name );
Person *result = table[hashNumber];
if ( !result )
{
cout << "Element not found" << endl;
return NULL;
}
while ( result->name != name )
{
if ( !result->next )
{
cout << "Element not found" << endl;
break;
}
result = result->next;
}
return result;
}
};
int main()
{
HashTable newTable;
newTable.push("Artyom", "Devyatov", 20);
newTable.push("Vasya", "Petrov", 23);
newTable.push("Ilja", "Saveljev", 28);
newTable.push("Ilaj", "Savanna", 43); // Имеет коллизию с Ilja
newTable.push("Dmitry", "Kuzychev", 31);
Person * search = newTable.find("Ilaj");
if ( search )
{
cout << search->surname << endl;
}
return 0;
}
Ответ
Допустим, что задание было сделать хэширование именно объектов Person. Причем эти объекты являются неотъемлимой частью таблицы, что следует из рассмотрения метода push(). Именно там они создаются из аргументов метода. Более того, деструктор четко показывает на это. Тогда отставим разговоры об общности программы и наличии ссылки для списка синонимов (next) в Person
Сначала все-таки о "мелочах". Константный размер таблицы мне не нравится. Пожалуй, стоило бы предусмотреть конструктор, который позволяет задавать ее размер.
Используемая функция хэширования не выдерживает никакой критики. В простейшем случае для строк используют все же что-то вроде
int hash (char k[]) {
int hashsum, i;
for (hashsum = i = 0; k[i]; i++)
hashsum = (hashsum * 31) ^ k[i]; // иногда берут 37
которая хоть как-то пытается перемешивать биты ключа.
Нет методов для удаления Person (но, тогда и его деструктор, надо менять) и траверса всей таблицы.
Теперь рассмотрим реальные ошибки.
Первая - метод hash() может возращать отрицательные числа. Результат очевиден, портим память, индекс массива table ошибочный. Можно написать
return (hashsum & 0x7fffffff) % tablesize;
Вторая - скорее логическая. В методе push() не проверяется, что такого ключа (name в Person) уже нет в списке синонимов.
Если предполагалась реализация "multimap", то тогдаfind() должен возвращать, например, список Person с одинаковым ключом. Или надо добавить метод find_next(Person), возвращающий следующий элемент с тем же ключом.
Третья - в методе find() если заданный ключ не найден в списке синонимов, то возвращается адрес последнего Person. Очевидно, в
if ( !result->next )
{
cout << "Element not found" << endl;
break;
}
вместо break; надо return NULL;
Больше сходу не увидел.
Комментариев нет:
Отправить комментарий