Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
term (also known as a "trivial hash function") that is used to describe the mapping of raw data
Raw data
'\putang inaIn computing, it may have the following attributes: possibly containing errors, not validated; in sfferent formats; uncoded or unformatted; and suspect, requiring confirmation or citation. For example, a data input sheet might contain dates as raw data in many forms: "31st January...
, used directly as in array index, for an array. The technique can be most effective for mapping data with a small range. If the array encompasses all combinations of input, a range check is not required.
Applicable arrays
In practise there are many examples of data exhibiting a small range of valid values all of which are suitable for processing using a trivial hash function including:
month in the year (1-12) - see C example 1 and 2 below
day in the month (1-31)
day of the week (1-7)
human lifespan (0-130) - eg. lifecover actuary tables, fixed term mortgage
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
Extended Binary Coded Decimal Interchange Code is an 8-bit character encoding used mainly on IBM mainframe and IBM midrange computer operating systems....
characters (0-255)
Examples
The following two examples demonstrate how a simple non-iterative table lookup, using a trivial hash function, can eliminate conditional testing & branching completely thereby reducing instruction path length
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 performance on a particular computer hardware...
significantly. Although both examples are shown here as functions, the required code would be better inlined
Inline expansion
In computing, inline expansion, or inlining, is a manual or compiler optimization that replaces a function call site with the body of the callee. This optimization may improve time and space usage at runtime, at the possible cost of increasing the final size of the program In computing, inline...
to avoid function call overhead in view of their obvious simplicity.
C example 1
This example of a C function - returning TRUE if a month (x) contains 30 days (otherwise FALSE), illustrates the concept succinctly
if ((unsigned)x > 11) return 0; /*x>12?*/
static const int T[12] ={0,0,0,0,1,0,1,0,0,1,0,1}; /* 0-based table 'if 30 days =1,else 0' */
return T[x]; /* return with boolean 1 = true, 0=false */
C example 2
Example of another C function - incrementing a month number (x) by 1 and automatically resetting if greater than 12
static const int M[12] ={2,3,4,5,6,7,8,9,10,11,12,1}; /* 1-based table to increment x */
return M[x]; /* return with new month number */
