Index mapping: Difference between revisions

Revision as of 17:15, 26 November 2015

Latest revision as of 19:41, 19 July 2024

(17 intermediate revisions by 13 users not shown)

Line 1:

{{distinguish|text=[[Index map]], a finding aid in cartography}}

{{Multiple issues|

'''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>.

{{one source|date=January 2012}}

The technique is most effective when the universe of keys is reasonably small, such that [[Memorymemory allocation|allocating]] an array with one position for every possible key is affordable.

{{essay-like|date=January 2012}}

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]].

}}

'''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>.

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==

In practice thereThere are many practical examples of data exhibitingwhose valid values are restricted within a small range. ofA validtrivial valueshash allfunction ofis which area suitable forchoice processing{{clarify|date=Januarywhen 2012}}such usingdata needs to act as a triviallookup hashkey. functionSome examples includinginclude:

* [[month]] in the year (1–12) – see [[#C example 1|C examples]] below

* [[month]] in the year (1–12) – see [[#C example 1|C examples]] below

* [[day]] in the month (1–31)

* [[day of the week]] (1–7)

* human lifespan{{clarify|date=January 2012}}age (0–130) – e.g. lifecover actuary tables, fixed -term mortgage

* [[ASCII]] characters {{clarify|date=January 2012}} (0–127), encompassing common mathematical operator symbols, digits, punctuation marks, and English language alphabet

* [[EBCDIC]] characters {{clarify|date=January 2012}} (0–255)

==Examples==

TheUsing followinga twotrivial exampleshash demonstratefunction, howin a simple non-iterative table lookup, using a trivial hash function, can eliminate conditional testing &and branching completely thereby, reducing the [[instruction path length]] significantly. Although both examples are shown here as functions, the required code would be better [[Inline expansion|inlined]] to avoid function call overhead in view of theira obviouscomputer simplicityprogram.

===CAvoid example 1branching===

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’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]]:

<sourcesyntaxhighlight lang="c++">

inline bool Has30DaysHasOnly30Days(int m) {

{

switch (m) {

case 4: // April

case 64: // JuneApril

case 6: // June
case 9: // September

case 11: // November

return true;

default:

return false;

}

}

</syntaxhighlight>

</source>

Which can be replaced with a table lookup:

<sourcesyntaxhighlight lang="c++">

inline bool Has30DaysHasOnly30Days(int m) {

{

static const bool T[] = { 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };

return T[m-1];

}

</syntaxhighlight>

</source>

===C example 2===

Example of another C function – incrementing a month number (x) by 1 and automatically resetting if greater than 12

<source lang="c">

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 */

</source>

==See also==

* [[Associative array]]

* [[Hash table]]

* [[Lookup table]]

* [[Multiway branch]]

==References==

Line 66 ⟶ 49:

[[Category:Associative arrays]]

[[Category:Articles with example C code]]

[[Category:Hashing|*]]

[[Category:Search algorithms]]