Index mapping

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Not to be confused with Index map, a finding aid in cartography.

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[edit]

There are many practical examples of data whose valid values are restricted within a small range. A trivial hash function is a suitable choice when such data needs to act as a lookup key. Some examples include:

  • month in the year (1–12)
  • day in the month (1–31)
  • day of the week (1–7)
  • human age (0–130) – e.g. lifecover actuary tables, fixed term mortgage
  • ASCII characters (0–127), encompassing common mathematical operator symbols, digits, punctuation marks and English language alphabet

Examples[edit]

Using a trivial hash function, in a non-iterative table lookup, can eliminate conditional testing and branching completely, reducing the instruction path length of a computer program.

Avoid branching[edit]

Roger Sayle gives an example[2] of eliminating a multiway branch caused by a switch statement:

inline bool Has30Days(int m) {
  switch (m) {
    case 4:  // April
    case 6:  // June
    case 9:  // September
    case 11: // November
      return true;
    default:
      return false;
  }
}

Which can be replaced with a table lookup:

inline bool Has30Days(int m) {
  static const bool T[] = { 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };
  return T[m];
}

See also[edit]

References[edit]

  1. ^ Cormen, Thomas H. (2009). Introduction to algorithms (3rd ed.). Cambridge, Mass.: MIT Press. pp. 253–255. ISBN 9780262033848. Retrieved 26 November 2015. 
  2. ^ Sayle, Roger Anthony (June 17, 2008). "A Superoptimizer Analysis of Multiway Branch Code Generation" (PDF). Proceedings of the GCC Developers’ Summit: 103–116. Retrieved 26 November 2015.