Отображение индекса - Index mapping

Не путать с Индексная карта, пособие по картографии.

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

Применимые массивы

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

  • месяц в год (1–12)
  • день в месяц (1–31)
  • день недели (1–7)
  • человеческий возраст (0–130) - например, актуарные таблицы, срочная ипотека
  • ASCII символы (0–127), включая обычные символы математических операторов, цифры, знаки препинания и английский алфавит

Примеры

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

Избегайте ветвления

Роджер Сэйл приводит пример[2] устранения разветвленная ветка вызвано оператор переключения:

в соответствии bool HasOnly30Days(int м){	выключатель (м) {	дело 4:  // Апреля	дело 6:  // Июнь	дело 9:  // Сентябрь	дело 11: // ноябрь		возвращаться истинный;	дефолт:		возвращаться ложный;	}}

Что можно заменить поиском по таблице:

в соответствии bool HasOnly30Days(int м){	статический const bool Т[] = { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };	возвращаться Т[м-1];}

Смотрите также

Рекомендации

  1. ^ Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. С. 253–255. ISBN  9780262033848. Получено 26 ноября 2015.
  2. ^ Сэйл, Роджер Энтони (17 июня 2008 г.). «Супероптимизаторный анализ генерации кода с несколькими ветвями» (PDF). Материалы саммита разработчиков GCC: 103–116. Получено 26 ноября 2015.