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.
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.
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:
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.
Roger Sayle gives an example of eliminating a multiway branch caused by a switch statement:
inline bool HasOnly30Days(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 HasOnly30Days(int m) { static const bool T[] = { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 }; return T[m-1]; }
This article uses material from the Wikipedia English article Index mapping, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Content is available under CC BY-SA 4.0 unless otherwise noted. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki English (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.