Index mapping

<h2 id="applicable-arrays">Applicable arrays</h2>
<p>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:
</p>
<ul><li><a href="/facts/Month/pMGGWtRc">month</a> in the year (1–12)</li>
<li><a href="/facts/Day/MTAtWLDj">day</a> in the month (1–31)</li>
<li><a href="/facts/Day_of_the_week/ENa9KgDx">day of the week</a> (1–7)</li>
<li>human age (0–130) – e.g. lifecover actuary tables, fixed-term mortgage</li>
<li><a href="/facts/ASCII/vGUI33Qu">ASCII</a> characters (0–127), encompassing common mathematical operator symbols, digits, punctuation marks, and English language alphabet</li></ul>
<h2 id="examples">Examples</h2>
<p>Using a trivial hash function, in a non-iterative table lookup, can eliminate conditional testing and branching completely, reducing the <a href="/facts/Instruction_path_length/Wk4jdu67">instruction path length</a> of a computer program.
</p>
<h3>Avoid branching</h3>
<p>Roger Sayle gives an example<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a> of eliminating a <a href="/facts/Multiway_branch/84mTcmjt">multiway branch</a> caused by a <a href="/facts/Switch_statement/oQCWnGWh">switch statement</a>:
</p>
inline bool HasOnly30Days(int m)
{
	switch (m) {
	case 4:  // April
	case 6:  // June
	case 9:  // September
	case 11: // November
		return true;
	default:
		return false;
	}
}

<p>Which can be replaced with a table lookup:
</p>
inline bool HasOnly30Days(int m)
{
	static const bool T[] = { 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0 };
	return T[m-1];
}

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Cormen, Thomas H. (2009). Introduction to algorithms (3rd ed.). Cambridge, Mass.: MIT Press. pp. 253–255. ISBN 9780262033848. Retrieved 26 November 2015. <a href="9780262033848" target="_blank">9780262033848</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Sayle, Roger Anthony (June 17, 2008). "A Superoptimizer Analysis of Multiway Branch Code Generation" (PDF). Proceedings of the GCC Developers' Summit: 103–116. Retrieved 26 November 2015. <a href="https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf" target="_blank">https://www.nextmovesoftware.com/technology/SwitchOptimization.pdf</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Index mapping open-in-new

Index mapping