Эффективная структура данных для сопоставления целочисленного целочисленного с find и insert, без распределений и фиксированной верхней границы

Question

Я ищу информацию о ассоциативной структуре данных, которая может воспользоваться конкретными критериями моего использования.

В настоящее время я использую красное/черное дерево для реализации словаря, который сопоставляет ключи значениям (в моем случае целые числа по адресам).

В моем случае использования максимальное количество элементов известно в начале (1024), и я буду только вставлять и искать. Поиск происходит в двадцать раз чаще, чем вставка. В конце процесса я очищаю структуру и повторяю снова. Во время использования не может быть никаких ассигнований - только начальный фронт. К сожалению, STL и последние версии C++ недоступны.

Любое понимание?

Answer 1

В результате я создал простой линейный зонд HashTable из примера here. Я использовал функцию хеша MurmurHash3, так как мои данные рандомизированы.

Я изменил хэш-таблицу следующим образом:

1. Размер параметр шаблона. Внутренне размер удваивается. Для реализации требуется мощность 2-х размеров и традиционно изменяется на 75%. Поскольку я знаю, что собираюсь заполнять хэш-таблицу, я упреждающе удваиваю емкость, чтобы сохранить ее достаточно разреженной. Это может быть менее эффективным при добавлении небольшого количества объектов, но оно более эффективно, когда емкость начинает заполняться. Поскольку я не могу изменить размер, я решил начать его удвоение по размеру.
2. Я не разрешаю хранить ключи со значением нуля. Это нормально для моего приложения, и он сохраняет код простым.
3. Все изменения размера и удаления удаляются, заменяется на одну операцию очистки, которая выполняет функцию memset.
4. Я выбрал встроенные функции вставки и поиска, так как они довольно малы.

Это быстрее, чем мое красное/черное дерево. Единственное изменение, которое я могу сделать, - это пересмотреть схему хэширования, чтобы увидеть, есть ли что-то в ключах источника, которые помогут сделать более дешевый хеш.

Billy ONeal предложил, учитывая небольшое количество элементов (1024), что простой линейный поиск в фиксированном массиве будет быстрее. Я следовал его совету и реализовал один для сравнения. На моем целевом оборудовании (примерно в первом поколении iPhone) хэш-таблица превзошла линейный поиск в два раза. При меньших размерах (256 элементов) хэш-таблица была еще выше. Конечно, эти значения зависят от оборудования. Размеры линии кэша и скорость доступа к памяти ужасны в моей среде. Тем не менее, другие, которые ищут решение этой проблемы, были бы умны, чтобы следовать его советам и сначала попытаться профилировать их.