Сопоставление индексов

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

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

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

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

Примеры

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

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

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

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];
}

Ссылки

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

[cormen-1] Кормен, Томас Х. (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс: MIT Press. стр. 253–255. ISBN 9780262033848 . Проверено 26 ноября 2015 г.

[2] Сэйл, Роджер Энтони (17 июня 2008 г.). «Анализ супероптимизатора генерации кода многопутевого ветвления» (PDF) . Материалы саммита разработчиков GCC : 103–116 . Проверено 26 ноября 2015 г.

[1]

[2]