Открытая адресация

Поскольку в условии задачи было сказано "написать хэш-таблицу, при добавлении элементов к которой в большинстве случаев не происходит динамическое создание новых объектов (не используется оператор new)", то разрешение коллизий было реализовано именно методом открытой адресации. Метод пробирования - квадратичный с коэффициентами c1 = 0.5 и c2 = 0.5, потому что именно при этих коэффициентах можно вычислять последовательность пробирования реккурентно, а также при этих коэффициентах будут просмотренны все пустые ячейки массива, содержащего данные.

Хэш функции

Принимаются в параметрах шаблона класса, по умолчанию - функтор DefaultHash<Key>. На данный момент реализованны 2 явные специализации функтора - для std::string и int.

Операция вставки

Операция вставки реализована с помощью метода insert

• Если коэффициент заполнения таблицы (load factor) превышает максимально заданный (по умолчанию 3/4), перехэшируем таблицу
• Вычисляется хэш ключа
• Если находим в последовательности проб EMPTY ячейку, то значит такого ключа в таблице нет. Если до неё встретились DELETED ячейки, то вставляем ключ в первый попавшийся DELETED, иначе вставляем в эту EMPTY ячейку.
• Иначе мы нашли этот ключ (если нет, то это логическая ошибка, т.к этого произойти не должно).

Операция поиска

Реализована с помощью метода find

• Вычисляем хэш
• Ячейка помечена EMPTY => ключа в таблице нет. Иначе если помечена BUSY, проверяем равенство ключей. Вычисляем следующую ячейку для проверки.

Операция удаления

Реализована с помощью метода erase

• Ищем ключ
• Если нашли, то помечаем ячейку как DELETED для того, чтобы в алгоритме поиска продолжать искать в случае встречи этой ячейки в последовательности проб.

Тестирование и оптимизационные правки

Тестирование работоспособности выполнено с помощью сравнения поведения хэш таблицы со стандартной std::unordered_map. Также сравнивались время выполнения операций.
Сначала, все было не очень. Последовательность проб вычислялась как pos(k, i) = hash(k) + 0.5*i + 0.5 * i * i. Написание функтора, позволяющего вычислять последовательность реккурентно увеличило производительность вставки примерно на 15%.
Но на ключах-строках все равно все было очень грустно, сложность вставки и поиска была похожа квадратичную. Дело оказалось в хэширующей функции. Суть функции в вычислении суммы полинома s[0] + s[1]p + s[2]p^2 ... + s[len - 1]p^{len - 1}. Далее берется модуль от размера таблицы m, которая является степенью двойки. Требовалось подобрать параметр p, изначально он брался как m - 1. Потом взял рекомендуемое значение 53 и показатели эффективности увеличились в разы. Результаты тестирования, полученные для рандомных 1 млн элементов таблицы при ключах-строках:

INSERT std runtime: 2.320069s
INSERT my runtime: 2.844449s
FIND std runtime: 2.103303s
FIND my runtime: 1.822054s
DELETE std runtime: 1.502174s
DELETE my runtime: 1.203505s

Видно, что моя таблица немного проигрывает при вставке, но выигрывает по поиску и удалению. В планах улучшить вставку.

Результаты при ключах-интах:

INSERT std runtime: 2.082287s
INSERT my runtime: 1.612655s
FIND std runtime: 2.010270s
FIND my runtime: 1.514997s
DELETE std runtime: 1.304627s
DELETE my runtime: 0.884580s

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

Используемое железо

• Компиляция:

$ g++ --std=c++17 tester.cpp HashTableUtils.cpp -o hashTester

• Компилятор:

$ gcc --version                                
Configured with: --prefix=/Applications/Xcode.app/Contents/Developer/usr --with-gxx-include-dir=/Applications/Xcode.app/Contents/Developer/Platforms/MacOSX.platform
/Developer/SDKs/MacOSX10.14.sdk/usr/include/c++/4.2.1
Apple LLVM version 10.0.1 (clang-1001.0.46.4)
Target: x86_64-apple-darwin18.2.0
Thread model: posix
InstalledDir: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin

• ОС:

macOS Mojave 10.14.2

• Процессор:

2,3 GHz Intel Core i7