Отображение индекса (или прямая адресация , или тривиальная хеш-функция ) в информатике описывает использование массива , в котором каждая позиция соответствует ключу во вселенной возможных значений. [1] Этот метод наиболее эффективен, когда совокупность ключей достаточно мала, так что можно выделить массив с одной позицией для каждого возможного ключа. Его эффективность заключается в том, что произвольную позицию в массиве можно исследовать за постоянное время .
Применимые массивы [ править ]
Существует множество практических примеров данных, допустимые значения которых ограничены небольшим диапазоном. Тривиальная хеш-функция - подходящий выбор, когда такие данные должны выступать в качестве ключа поиска. Вот некоторые примеры:
- месяц в году (1–12)
- день месяца (1–31)
- день недели (1–7)
- возраст человека (0–130) - например, таблицы актуариев, срочная ипотека
- Символы ASCII (0–127), включая обычные символы математических операторов, цифры, знаки препинания и английский алфавит.
Примеры [ править ]
Использование тривиальной хеш-функции в неитеративном поиске по таблице может полностью исключить условное тестирование и ветвление, уменьшая длину пути выполнения команд компьютерной программы.
Избегайте ветвления [ править ]
Роджер Сэйл приводит пример [2] исключения многосторонней ветки, вызванной оператором switch :
inline bool HasOnly30Days ( int m ) { switch ( m ) { case 4 : // April case 6 : // June case 9 : // September case 11 : // November return true ; по умолчанию : вернуть false ; } }Что можно заменить поиском по таблице:
встроенный bool HasOnly30Days ( int m ) { static const bool T [] = { 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 , 1 , 0 }; return T [ m -1 ]; }См. Также [ править ]
Ссылки [ править ]
- ^ Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. С. 253–255. ISBN 9780262033848. Проверено 26 ноября 2015 года . CS1 maint: обескураженный параметр ( ссылка )
- ^ Сейл, Роджер Энтони (17 июня 2008). «Анализ супероптимизатора генерации кода с множественными ветвями» (PDF) . Труды Саммита разработчиков GCC : 103–116 . Проверено 26 ноября 2015 года . CS1 maint: обескураженный параметр ( ссылка )
