Index mapping
 | This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these messages)
|
Index mapping (or direct addressing, or a trivial hash function) in computer science describes using an array, in which each position corresponds to a key in the universe of possible values[1]. The technique is most effective when the universe of keys is reasonably small, such that allocating an array with one position for every possible key is affordable. Its effectiveness comes from the fact that an arbitrary position in an array can be examined in constant time.
Applicable arrays
In practice there are many examples of data exhibiting a small range of valid values all of which are suitable for processing[clarification needed] using a trivial hash function including:
- month in the year (1–12) – see C examples below
- day in the month (1–31)
- day of the week (1–7)
- human lifespan[clarification needed] (0–130) – e.g. lifecover actuary tables, fixed term mortgage
- ASCII characters [clarification needed] (0–127), encompassing common mathematical operator symbols, digits, punctuation marks and English language alphabet
- EBCDIC characters [clarification needed] (0–255)
Examples
The following two examples demonstrate how a simple non-iterative table lookup, using a trivial hash function, can eliminate conditional testing & branching completely thereby reducing instruction path length significantly. Although both examples are shown here as functions, the required code would be better inlined to avoid function call overhead in view of their obvious simplicity.
C example 1
This example[2] of a C function – returning TRUE if a month (x) contains 30 days (otherwise FALSE), illustrates the concept succinctly
if (((unsigned)x > 12) || ((unsigned)x <= 0) return 0; /*x>12 or x<=0?*/
static const int T[12] ={0,0,0,1,0,1,0,0,1,0,1,0}; /* 0-based table 'if 30 days =1,else 0' */
return T[x - 1]; /* return with boolean 1 = true, 0=false */
C example 2
Example of another C function – incrementing a month number (x) by 1 and automatically resetting if greater than 12
static const int M[12] ={2,3,4,5,6,7,8,9,10,11,12,1}; /* 0-based table to increment x */
return M[x - 1]; /* return with new month number */
See also
References
- ^ Cormen, Thomas H. (2009). Introduction to algorithms (3rd ed.). Cambridge, Mass.: MIT Press. pp. 253–255. ISBN 9780262033848. Retrieved 26 November 2015.
- ^ "A Superoptimizer Analysis of Multiway Branch Code Generation" by Roger Anthony Sayle[dead link]