Mapeamento de índice - Index mapping
O mapeamento de índice (ou endereçamento direto , ou uma função hash trivial ) em ciência da computação descreve o uso de um array , no qual cada posição corresponde a uma chave no universo de valores possíveis. A técnica é mais eficaz quando o universo de chaves é razoavelmente pequeno, de forma que alocar um array com uma posição para cada chave possível é acessível. Sua eficácia vem do fato de que uma posição arbitrária em uma matriz pode ser examinada em tempo constante .
Matrizes aplicáveis
Existem muitos exemplos práticos de dados cujos valores válidos são restritos a um pequeno intervalo. Uma função hash trivial é uma escolha adequada quando esses dados precisam atuar como uma chave de pesquisa. Alguns exemplos incluem:
- mês do ano (1–12)
- dia do mês (1–31)
- dia da semana (1–7)
- idade humana (0-130) - por exemplo, tábuas do atuário vitalícias, hipoteca a prazo fixo
- Caracteres ASCII (0-127), abrangendo símbolos de operadores matemáticos comuns, dígitos, sinais de pontuação e alfabeto do idioma inglês
Exemplos
Usar uma função hash trivial, em uma pesquisa de tabela não iterativa, pode eliminar o teste condicional e a ramificação completamente, reduzindo o comprimento do caminho de instrução de um programa de computador.
Evite ramificação
Roger Sayle dá um exemplo de eliminação de um branch multiway causado por uma instrução 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;
}
}
Que pode ser substituído por uma consulta de tabela:
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];
}