Отображение индекса - Index mapping
Отображение индекса (или прямая адресация , или тривиальная хеш-функция ) в информатике описывает использование массива , в котором каждая позиция соответствует ключу во вселенной возможных значений. Этот метод наиболее эффективен, когда совокупность ключей достаточно мала, так что можно выделить массив с одной позицией для каждого возможного ключа. Его эффективность заключается в том, что произвольную позицию в массиве можно исследовать за постоянное время .
Применимые массивы
Существует множество практических примеров данных, допустимые значения которых ограничены небольшим диапазоном. Тривиальная хеш-функция - подходящий выбор, когда такие данные должны выступать в качестве ключа поиска. Вот некоторые примеры:
- месяц в году (1–12)
- день месяца (1–31)
- день недели (1–7)
- возраст человека (0–130) - например, таблицы актуариев, срочная ипотека
- Символы ASCII (0–127), включая обычные символы математических операторов, цифры, знаки препинания и английский алфавит.
Примеры
Использование тривиальной хеш-функции в неитеративном поиске в таблице может полностью исключить условное тестирование и ветвление, уменьшая длину пути выполнения команд компьютерной программы.
Избегайте ветвления
Роджер Сэйл приводит пример исключения многосторонней ветки, вызванной оператором switch :
inline bool HasOnly30Days(int m)
{
switch (m) {
case 4: // April
case 6: // June
case 9: // September
case 11: // November
return true;
default:
return false;
}
}
Что можно заменить поиском по таблице:
inline bool HasOnly30Days(int m)
{
static const bool T[] = { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };
return T[m-1];
}