Index mapping: Difference between revisions

Revision as of 17:45, 26 November 2015

Revision as of 07:49, 27 November 2015

Line 1:

'''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-255253–255|edition=3rd|url=https://mitpress.mit.edu/books/introduction-algorithms|accessdate=26 November 2015}}</ref>.

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_complexityTime complexity#Constant_timeConstant time|constant time]].

==Applicable arrays==

Line 16:

===Avoid branching===

Roger Sayle gives an example<ref>{{cite journal|last1=Sayle|first1=Roger Anthony|title=A Superoptimizer Analysis of Multiway Branch Code Generation|journal=Proceedings of the GCC Developers’ Summit|date=June 17, 2008|pages=103-116103–116|url=https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf|accessdate=26 November 2015}}</ref> of eliminating a [[multiway branch]] caused by a switch statement:

<source lang="c++">