Посмотрите таблицу с битовыми массивами фиксированного размера в качестве ключей

Question

У меня есть серия массивов фиксированных размеров двоичных значений (индивидов из генетического алгоритма), которые я хотел бы связать со значением с плавающей запятой (значением пригодности).Такая справочная таблица будет иметь довольно большой размер, ограниченный доступной памятью.Из-за природы ключей существует ли хеш-функция, которая гарантирует отсутствие коллизий?Я попробовал несколько вещей, но они приводят к столкновениям.Какую другую структуру данных я мог бы использовать для построения этой поисковой системы?

Answer 1

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

Ответ на вопрос о сжатии массива битов в C здесь: Сжатие массива разреженных битов

Поскольку большинство битов установлено в ноль, самым простым решением было бы просто написать функцию, которая преобразует ваш битовый массив в целочисленный массив, который отслеживает позиции битов, которые установлены в «1». Затем напишите функцию, которая делает обратное, если вам снова понадобится битовый массив. Вы можете сохранить в hashmap только закодированный массив.

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