Content deleted Content added
Stevebroshar (talk | contribs) |
Stevebroshar (talk | contribs) →Sparse one-dimensional array: Use 'control table' |
||
Line 22:
===Sparse one-dimensional array===
{| class="wikitable floatright" style="text-align:center; "
|+
|- style="vertical-align:bottom;"
! index
|-
| 0 ||style="background:lightblue;"| 00
|-
| ... ||style="background:lightblue;"| 00
Line 43 ⟶ 45:
|-
| ... ||style="background:lightblue;"| 00
|-
| 255 ||style="background:lightblue;"| 00
|}
A relatively simple implementation consists of a [[sparse file |sparse]], one-dimensional array of values. The index space is fully covered by the array such that lookup involves indexing into the array by the input value, and a value is found even for an index that is not intended to be used; preventing an error that might otherwise occur for an unused index value. The lookup is achieved in [[constant time]]; without searching. In most [[computer architecture |architecture]]s, this can be accomplished in two or three [[machine instruction]]s. The technique is known as a "[[trivial hash function]]" or, when used specifically for branch tables, "[[double dispatch]]". To be feasible, the range of index values should be relatively small. In the example, the table is indexed by ASCII character value so it has 256 entries; an entry for each ASCII value. Only the values for the letter A, D, M, and S are important. All other values are uninteresting and set to 0.
| |||