Index mapping (or direct addressing, or a trivial

hash function A hash function is any Function (mathematics), function that can be used to map data (computing), data of arbitrary size to fixed-size values, though there are some hash functions that support variable-length output. The values returned by a ...

) in

computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...

describes using an array, in which each position corresponds to a key in the

universe The universe is all of space and time and their contents. It comprises all of existence, any fundamental interaction, physical process and physical constant, and therefore all forms of matter and energy, and the structures they form, from s ...

of possible values. The technique is most effective when the universe of keys is reasonably small, such that 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

constant time In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations p ...

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 A month is a unit of time, used with calendars, that is approximately as long as a natural phase cycle of the Moon; the words ''month'' and ''Moon'' are cognates. The traditional concept of months arose with the cycle of Moon phases; such lunar mo ...

in the year (1–12) *

day A day is the time rotation period, period of a full Earth's rotation, rotation of the Earth with respect to the Sun. On average, this is 24 hours (86,400 seconds). As a day passes at a given location it experiences morning, afternoon, evening, ...

in the month (1–31) *

day of the week In a vast number of languages, the names given to the seven days of the week are derived from the names of the classical planets in Hellenistic astronomy, which were in turn named after contemporary deities, a system introduced by the Sume ...

(1–7) * human age (0–130) – e.g. lifecover actuary tables, fixed-term mortgage *

ASCII ASCII ( ), an acronym for American Standard Code for Information Interchange, is a character encoding standard for representing a particular set of 95 (English language focused) printable character, printable and 33 control character, control c ...

characters (0–127), encompassing common mathematical operator symbols, digits, punctuation marks, and English language alphabet

Examples

Using a trivial hash function, in a non-iterative table lookup, can eliminate conditional testing and branching completely, reducing the

instruction path length In computer performance, the instruction path length is the number of machine code instructions required to execute a section of a computer program. The total path length for the entire program could be deemed a measure of the algorithm's perfor ...

of a computer program.

Avoid branching

Roger Sayle gives an example of eliminating a

multiway branch Multiway branch is the change to a program's control flow based upon a value matching a selected criteria. It is a form of conditional statement. A multiway branch is often the most efficient method of passing control to one of a set of program ...

caused by a

switch statement In computer programming languages, a switch statement is a type of selection control mechanism used to allow the value of a variable or expression to change the control flow of program execution via search and map. Switch statements function ...

: inline bool HasOnly30Days(int m) Which can be replaced with a table lookup: inline bool HasOnly30Days(int m)

References

{{Reflist Arrays Associative arrays Articles with example C code Hashing Search algorithms