Think of an array as a row of storage cells. An indexing function takes an element or key and tells you which cell holds its associated value. With that direct lookup, searching, inserting, and deleting could each take constant time—provided the ideal assumptions hold. section 12.10
The index is not free. The function may first extract a unique identifier and convert a string into an integer. A simple character-sum formula makes anagrams collide; weighting characters by position produces a more informative base-256-style number. If computing the index takes O(k) time, it is effectively constant only when k is bounded independently of the collection size. section 12.11
The ideal direct-access arrangement has practical limits:
- It needs a way to distinguish occupied cells from empty ones, such as storing None or null. section 12.10
- It works poorly when possible keys vastly outnumber stored elements, because the array becomes mostly empty and wastes memory. section 12.12
- It is practical only when constraints limit the size and composition of the keys being stored. section 12.12
Turning a name into an index
For the string 'Joe Di Maggio', process each character in sequence: start with id = 0, add the character’s ordinal value, then multiply by 256. The resulting integer can serve as an array index, although the resulting key space may be enormous. section 12.11 section 12.12
id = 0
for c in 'Joe Di Maggio':
id = id + ord(c)
id *= 256
Inspect the character-by-character index calculation for the example name. section 12.11
