Функция хеширования против поиска петли

Question

У меня есть массив структур, ~ 100 уникальных элементов, и структура не большая. Из-за устаревшего кода, чтобы найти элемент в этом массиве, я использую хеш-функцию, чтобы найти вероятную начальную точку, с которой начинается цикл, пока я не найду нужный элемент.

Мой вопрос таков: избыточная ли хеш-функция (и получающаяся хеш-таблица)?

Я знаю, что для больших таблиц хеширование важно для хорошего времени отклика, но для таблицы это размер?

Более кратко, есть ли размер таблицы, ниже которого запись хеш-функции не нужна?

Ответы, не зависящие от языка, пожалуйста.

Спасибо

Answer 1

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

Хотя я думаю, что из-за производительности карта хеш-функции для 100 элементов является излишней.

Answer 2

При создании (или после его создания) сортируйте «массив уникальных элементов» по ​​их «значению ключа». Затем используйте «бинарный поиск», а не хэш или линейный поиск. Теперь вы получаете простую реализацию, без лишнего использования памяти и хорошей производительности.

Answer 3

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

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

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