Mapeo de índices

El mapeo de índices (o direccionamiento directo , o una función hash trivial ) en informática describe el uso de una matriz , en la que cada posición corresponde a una clave en el universo de valores posibles. ^[1] La técnica es más efectiva cuando el universo de claves es razonablemente pequeño, de modo que la asignación de una matriz con una posición para cada clave posible es asequible. Su efectividad proviene del hecho de que una posición arbitraria en una matriz se puede examinar en tiempo constante .

Existen muchos ejemplos prácticos de datos cuyos valores válidos están restringidos a un rango pequeño. Una función hash trivial es una opción adecuada cuando dichos datos deben actuar como una clave de búsqueda. Algunos ejemplos incluyen:

• mes del año (1–12)
• día del mes (1–31)
• Día de la semana (1–7)
• Edad humana (0-130) – p. ej., tablas actuariales de seguros de vida, hipotecas a plazo fijo
• Caracteres ASCII (0–127), que abarcan símbolos de operadores matemáticos comunes, dígitos, signos de puntuación y el alfabeto del idioma inglés

El uso de una función hash trivial, en una búsqueda de tabla no iterativa, puede eliminar por completo las pruebas condicionales y las ramificaciones, reduciendo la longitud de la ruta de instrucciones de un programa de computadora.

Roger Sayle da un ejemplo ^[2] de eliminación de una rama multidireccional causada por una declaración switch :

inline bool HasOnly30Days ( int m ) { switch ( m ) { caso 4 : // abril caso 6 : // junio caso 9 : // septiembre caso 11 : // noviembre return true ; predeterminado : return false ; } }               

Que se puede reemplazar con una búsqueda en la tabla:

bool en línea HasOnly30Days ( int m ) { constante estática bool T [ ] = { 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 } ; devolver T [ m -1 ] ; }