Оцените реализацию хеш-таблицы

#cpp #хеширование

В уездном городе N проводился конкурсный отбор и было дано задание: "реализовать
хеш-таблицу". Задание, вроде, несложное, но я не прошёл. Комментариев никаких дано
не было, но очень хотелось бы получить обратную связь. Буду рад абсолютно любым комментариям
по любому поводу, занудствовать разрешается!

// Реализация хеш-таблицы через остаток от деления
// Добавление и поиск элементов осуществлятся через имя (name). В реальных условиях
// такая таблица будет иметь много коллизий, но, поскольку задание является тестовым,
// я избрал самый простой, быстрый и наглядный метод реализации.

#include 
#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\n";
        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;
}

    

Ответы

Ответ 1

Допустим, что задание было сделать хэширование именно объектов 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;
Больше сходу не увидел.


Ответ 2

Для начала: у вас Person содержит в себе сразу инфраструктуру для хеш-таблицы: поле
next. Это неправильно:

зачем расходовать память на next для объектов, которые не лежат ни в какой хеш-таблице? 
что, если один объект лежит сразу в нескольких хеш-таблицах?

Затем: у вас размер table фиксированный. Это неправильно, при такой реализации поиск
будут О(<к-во элементов в таблице> / PRIME_SIZE), то есть линейно расти. Вам нужно
динамически расширять таблицу при увеличении количества элементов, чтобы выдержать
асимптотику амортизированного O(1).
Затем, если уж пишете на C++, почему не сделать хэш-таблицу темплейтом по типу элемента?


Ответ 3

Идея хранения списка объектов Person в самом объекте персон очень не удачная. Person
- это объект для хранения данных о человеке, откуда там взяться ещё и списку других
людей? Если нужен список, то можно взять готовый / написать свой и класть туда объекты
Person.
По самому коду вот набросал замечания
http://pastebin.com/kSWkfumS


Ответ 4

А в чем задание конкретно состояло? По мне так негоже такие велосипеды писать, ведь
есть std::map в конце концов. А по коду, в классе Person присвоения лучше в блок инициализации
конструктора вынести чтобы пустые конструкторы string не вызывались лишний раз.