Index mapping: Difference between revisions

Revision as of 02:01, 23 August 2011

Revision as of 14:46, 11 January 2012

Line 1:

{{multiple issues |one source=January 2012 |essay-like=January 2012}}

'''Index mapping''' is a [[computer science]] term (also known as a "'''trivial [[hash function]]'''"<ref>http://en.wikipedia.org/wiki/Hash_function#Trivial_hash_function</ref>) that is used to describe the mapping{{clarification needed|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{{clarification needed|date=January 2012}}. If the array encompasses all combinations of input, a range check is not required.

==Applicable arrays==

In practisepractice there are many examples of data exhibiting a small range of valid values all of which are suitable for processing{{clarification needed|date=January 2012}} using a trivial hash function including:

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

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

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

* human lifespan{{clarification needed|date=January 2012}} (0-1300–130) -– eg. lifecover actuary tables, fixed term mortgage

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

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

:* common mathematical operator symbols (+-/*^)

:* common punctuation symbols (,.;:")

:* english uppercase language alphabet (A-Z)

:* english lowercase language alphabet (a-z)

:* numeric digits (0-9)

:* etc

* [[EBCDIC]] characters (0-255)

==Examples==

Line 20 ⟶ 16:

===C example 1===

This example<ref>[http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf "A Superoptimizer Analysis of Multiway Branch Code Generation"] by Roger Anthony Sayle</ref> of a C function -– returning TRUE if a month (x) contains 30 days (otherwise FALSE), illustrates the concept succinctly

<source lang="c">

if ((unsigned)x > 11) return 0; /*x>12?*/

Line 28 ⟶ 24:

===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}; /* 1-based table to increment x */

Line 47 ⟶ 43:

[[Category:Hashing|*]]

[[Category:Search algorithms]]

<!-- do interwikis exist? -->