[Include] hashmap.inc - реализация хеш-карты в Pawn [Архив] - Pro Pawn

Просмотр полной версии : [Include] hashmap.inc - реализация хеш-карты в Pawn

Anve

02.02.2018, 00:53

hashmap.inc
github (https://github.com/AnveSamp/HashMap)
Что это?
Инклуд, позволяющий создавать и работать с хеш-картой. Подробнее о хеш-карте вы можете прочитать здесь (https://ru.wikipedia.org/wiki/%D0%A5%D0%B5%D1%88-%D1%82%D0%B0%D0%B1%D0%BB%D0%B8%D1%86%D0%B0).

Преимущества:

Легко в использовании
Нет зависимостей
Много функций

Как это работает?
Создаётся массив с размером 256(MAX_HASHMAP_SIZE) ячеек. При добавлении строка(ключ) хешируется и этот хеш является индексом массива. Во всех последующих операциях(поиск/удаление и т.д.) со строкой происходит тоже самое, однако размер массива довольной маленький, из-за чего могут возникнуть коллизии. Решением данной проблемы является увеличение макроса MAX_HASHMAP_SIZE.

Возможные предупреждения, выводимые в консоль & Ошибки
Ошибки
Инклуд имеет следующие замакросенные ошибки:

HASHMAP_ERROR_OK
Описание: Обозначает, что ошибок нет, и всё выполнено успешно.

HASHMAP_ERROR_OCCUPIED
Описание: Обозначает, что в ячейке массива уже записано значение, ошибка возможна при возникновении коллизии.

HASHMAP_ERROR_NOT_FOUND
Описание: Обозначает, что значение не было найдено.

Предупреждения
Если консоле вы заметили следующее предупреждение: "[HashMap] Element "%s" already registered", то это говорит о следующем:

Произошла коллизия при добавлении, и значение не было записано
Вы указали строку, с помощью которой уже было записано ранее значение, и произойдёт выше написанное

Конфигурационные макросы

Название
По умолчанию
Описание

MAX_HASHMAP_SIZE
256
Максимальный размер массива хеш-карты

Callbacks & Функции
Callbacks

OnHashMapFind
Определяется как: OnHashMapFind(error, value)
Описание: Вызывается после поиска значения.
Параметры:

error - передается в виде одной из вышеприведённых ошибок
value - найденное(или нет) значение

Пример использования

public OnHashMapFind(error, value)
{
switch(error)
{
case HASHMAP_ERROR_OK: printf("Value: %d",value);
}
}

Функции & Операции

HashMap_Emplace - Добавление нового элемента в хеш-карту
Параметры:

Хеш-карта
Ключ
Значение

Возвращаемое значение: одна из вышеприведённых ошибок.

Пример использования

public OnGameModeInit()
{
new HashMap:Map<>;
HashMap_Emplace(Map,"key",10); // Добавит новый элемент с ключом "key" и значением 10
}

HashMap_Find - Поиск элемента по ключу
Параметры:

Хеш-карта
Ключ

Возвращаемое значение: значение элемента / ошибку HASHMAP_ERROR_NOT_FOUND.

Пример использования

public OnGameModeInit()
{
new HashMap:Map<>;
HashMap_Emplace(Map,"key",10);
new value = HashMap_Find(Map,"key");
printf("Value: %d",value);
}

HashMap_Erase - Удаление элемента из хеш-карты
Параметры:

Хеш-карта
Ключ

Возвращаемое значение: одна из вышеприведённых ошибок.

Пример использования

public OnGameModeInit()
{
new HashMap:Map<>;
HashMap_Emplace(Map,"key",10);
HashMap_Erase(Map,"key"); // Удалит элемент с ключом "key"
}

HashMap_Count - Получение кол-ва записанных в хеш-карту элементов
Параметры:

Хеш-карта

Возвращаемое значение: кол-во элементов записанных в хеш-карту.

Пример использования

public OnGameModeInit()
{
new HashMap:Map<>;
HashMap_Emplace(Map,"key",10);
HashMap_Count(Map); // Вернёт 1
}

HashMap_Size - Получение размера хеш-карты
Параметры:

-

Возвращаемое значение: MAX_HASHMAP_SIZE (вернёт в любом случае, ниже показан пример).

Пример использования

public OnGameModeInit()
{
new size = HashMap_Size();
printf("%d",size);
}

HashMap_Clear - Очищение хеш-карты
Параметры:

Хеш-карта

Возвращаемое значение: HASHMAP_ERROR_OK.

Пример использования

public OnGameModeInit()
{
new HashMap:Map<>;
HashMap_Emplace(Map,"key",10);
HashMap_Clear(Map); // Очистит все созданные раннее элементы
}

HashMap_Empty - Проверить, пуста ли хеш-карта
Параметры:

Хеш-карта

Возвращаемое значение: true или false.

Пример использования

public OnGameModeInit()
{
new HashMap:Map<>;
HashMap_Emplace(Map,"key",10);
HashMap_Empty(Map); // Вернёт 0, т.к. мы только что создали элемент
HashMap_Clear(Map);
HashMap_Empty(Map); // Вернёт 1, т.к. мы очистили хеш-карту
}

Change Log

Первая версия
01/02/2018

Версия 1.1
02/02/2018

Добавлены функции HashMap_Clear и HashMap_Empty

Daniel_Cortez

02.02.2018, 02:43

Anve

02.02.2018, 14:21

https://github.com/AnveSamp/HashMap/blob/adccb736b8c12f38aa97d928c09fd3ac33fe5b87/hashmap.inc#L40

#define HashMap_Hash(%1,%8new%2) \
new%2; \
for(new i@HM = 0; %1[i@HM]; i@HM++) %2 = (%2 * 37) ^ %1[i@HM]; \
%2 = %2 % MAX_HASHMAP_SIZE

И вместо хеш-функции опять (http://pro-pawn.ru/showthread.php?15849&p=88993&viewfull=1#post88993) самоделка с частыми коллизиями. Уже не смешно.

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

Anve

02.02.2018, 15:39

Версия 1.1 - добавлены новые функции
Добавлены функции HashMap_Clear и HashMap_Empty.
Подробнее об этих функциях вы можете узнать в первом посте.

VVWVV

02.02.2018, 16:50

Все же лучше делать хеш-таблицы в Pawn через плагины.

Anve

02.02.2018, 17:14

Все же лучше делать хеш-таблицы в Pawn через плагины.

Конечно ты прав, но тем не менее я попытался сделать что-то подобное не в виде костыля.
Кстати на моём гите лежит хеш-таблица в виде плагина.

Geebrox

02.02.2018, 19:03

Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется коллизией. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50%

То есть при использование этого инклюда есть вероятность, что каждый второй элемент может быть коллизией?

И ещё можно было бы переименовать HashMap_Empty на HashMap_IsEmpty, было бы логичнее, ибо такое название больше подходит для очисти, а не проверки. Ну это просто предложение.

Anve

02.02.2018, 19:18

То есть при использование этого инклюда есть вероятность, что каждый второй элемент может быть коллизией?

Всё зависит от кол-ва уже записанных элементов и размера.

Решением данной проблемы является увеличение макроса MAX_HASHMAP_SIZE.

И ещё можно было бы переименовать HashMap_Empty на HashMap_IsEmpty, было бы логичнее, ибо такое название больше подходит для очисти, а не проверки. Ну это просто предложение.

Переименую в следующей версии.

Daniel_Cortez

02.02.2018, 21:59

Действительно, не смешно брать пример из юмористического командного процессора
Хорошая попытка перевести стрелки.

Даже не смотря на то, что это не супер-мега хеш-функция
Так я и не говорю, что эта функция должна быть какой-то "супер-мега". Всякие "мегасложные" функции типа MurmurHash2, CityHash etc. сделаны так, чтобы обрабатывать данные блоками по 4 или 8 байт за итерацию, чтобы максимально эффективно использовать ресурсы ЦП.
Однако, в Pawn своя VM, свой набор инструкций, да и строки по умолчанию кодируются по 1 символу на ячейку (4 байта), поэтому понты с обработкой по 4 символа из строки вместо 1 за раз ничего хорошего не принесут. Самыми эффективными в Pawn будут хеш-функции, которые в то же время и самые простые, обрабатывающие по 1 символу за итерацию, вроде хеша Дженкинса (one-at-a-time) или FNV1a - кстати говоря, именно эти функции и были реализованы в y_stringhash.

коллизия может возникнуть лишь из-за последней операции, и в топике написано по какой причине и как её решить.
Дело не в "урезании" хеша под размер таблицы, а в том, что функция сама по себе выдаёт много коллизий, даже без вычисления остатка от деления в конце.

Если же вы считаете, что я ошибаюсь, я предлагаю вам показать пример строк, из-за которых может возникнуть коллизия, дабы не быть пустословом
Получите, распишитесь: https://github.com/Daniel-Cortez/hash-collision-test

Loading the dictionary from file "../words_alpha.txt"...
Loaded 370099 words

Testing: std::unordered_map hash function...
Found 14 collisions

Testing: MurmurHash2A...
Found 15 collisions

Testing: MurmurHash3_x86_32...
Found 13 collisions

Testing: lookup3...
Found 15 collisions

Testing: one-at-a-time...
Found 25 collisions

Testing: FNV1a_32...
Found 13 collisions

Testing: AnveCMD_Hash...
Found 248222 collisions

Testing: AnveHashMap_Hash...
Found 97932 collisions

Я использовал этот фреймворк для выбора хеш-функции в одной из последних версий DC_CMD; даже не думал, что он мне ещё когда-нибудь пригодится.
Как можно увидеть из лога, я использовал словарь из 370 тыс. слов на английском. Скажете, слишком много? Взгляните на результаты - у всех нормальных функций из этих 370 тысяч слов нашлось всего 13-25 пар с одинаковыми хешами. Ожидаемо отличились только ваши хеш-функции из "шуточного" AnveCMD и hashmap.inc - 248 и 98 тыс. коллизий соответственно. Конечно, в hashmap.inc наблюдается прогресс по сравнению с AnveCMD, но совпадающих хешей всё ещё очень много.

Конечно ты прав, но тем не менее я попытался сделать что-то подобное не в виде костыля.
Кстати на моём гите лежит хеш-таблица в виде плагина.
Плагин с потенциалом предоставления возможностей C/C++ в Pawn - костыль.
Инклуд на Pawn с ограниченным размером таблицы - хорошее решение.
Л - логика.

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

Тема закрыта.

P.S.: Мне пришлось потратить полтора часа личного времени на подготовку к публикации исходников и написание этого поста. Можете собой гордиться.