Index mapping: Difference between revisions

Revision as of 17:56, 11 May 2020

Latest revision as of 19:41, 19 July 2024

(2 intermediate revisions by 2 users not shown)

Line 1:

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

'''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 [[Memorymemory 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 [[Timetime complexity#Constant time|constant time]].

==Applicable arrays==

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

Line 20 ⟶ 19:

<syntaxhighlight lang="c++">

inline bool HasOnly30Days(int m)

{

switch (m) {

Line 37 ⟶ 36:

<syntaxhighlight lang="c++">

inline bool HasOnly30Days(int m)

{

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

Line 43 ⟶ 42:

}

</syntaxhighlight>

==See also==

* [[Associative array]]

* [[Hash table]]

* [[Lookup table]]

==References==

Line 55 ⟶ 49:

[[Category:Associative arrays]]

[[Category:Articles with example C code]]

[[Category:Hashing|*]]

[[Category:Search algorithms]]