Index mapping: Difference between revisions

Revision as of 12:16, 7 January 2015

Revision as of 16:25, 26 November 2015

Line 4:

}}

'''Index mapping''' (or ''direct addressing'', or a ''trivial [[hash function]]'') in [[computer science]] describes using an [[array data structure|array]], in which each position corresponds to a key in the [[Universe (mathematics)|universe]] of possible values<ref name=cormen>{{cite book|last1=Cormen|first1=Thomas H.|title=Introduction to algorithms|date=2009|publisher=MIT Press|___location=Cambridge, Mass.|isbn=9780262033848|pages=253-255|edition=3rd|url=https://mitpress.mit.edu/books/introduction-algorithms|accessdate=26 November 2015}}</ref>.

'''Index mapping''' is a [[computer science]] term (also known as a "'''trivial [[hash function]]'''") that is used to describe the mapping{{clarify|date=January 2012}} of [[raw data]], used directly as in [[array index]], for an [[array data structure|array]]. The technique can be most effective for mapping data with a small range{{clarify|date=January 2012}}. If the array encompasses all combinations of input, a range check is not required.

The technique is most effective when the universe of keys is reasonably small, such that [[Memory allocation|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 [[Time_complexity#Constant_time|constant time]].

==Applicable arrays==