How does a hash function turn a word into an array index?

Take the word cat. In ASCII its bytes are 99, 97 and 116. A toy hash that treats the bytes as digits in base 31 computes $99 \times 31^2 + 97 \times 31 + 116$. Since $31^2 = 961$, that is $99 \times 961 + 97 \times 31 + 116 = 95{,}139 + 3{,}007 + 116 = 98{,}262$. With a table of $m = 1000$ slots, $98{,}262 \bmod 1000 = 262$, so cat goes to index 262. With a table of $m = 16$ slots, $98{,}262 = 16 \times 6{,}141 + 6$, so the same hash goes to index 6. The hash number did not change; only the table size changed.

The second step is just division with remainder. Any whole number, however many digits it has, leaves a remainder in the range $0$ to $m-1$ when divided by $m$. That is why the method works for a word of any length without a lookup table: the hash can be enormous, but the remainder is guaranteed to be a legal index. When $m$ is a power of two, the remainder keeps only the lowest bits of the hash, which is why the mixing step has to affect those bits and not just the early bytes.

The natural guess is that a good hash must encode every word uniquely, or that somewhere there is a table mapping each word to its slot. Neither is what happens. A hash is a function from a much larger set of possible keys to a much smaller set of positions, so it cannot be one to one. With eight lower-case letters there are $26^8 = 208{,}827{,}064{,}576$ possible words. In a table of one million slots, that is $208{,}827{,}064{,}576 / 1{,}000{,}000 = 208{,}827.064576$ possible words per slot on average. The count is not a defect of a particular hash; it is arithmetic. A hash that looked perfect would have to be storing the word somewhere, and the whole point is to avoid that.

Collisions show up even for the modest words. A bad hash that adds the bytes gives listen, silent, enlist and tinsel the same sum: 108 + 105 + 115 + 116 + 101 + 110 = 655. With $m = 1000$ all four get index 655. A mixing hash multiplies and combines each byte so that changing the order changes the result, and the same four words scatter. The difference is not the remainder; it is whether the large number depends on all the bytes in their order.

Collisions are not a late-stage problem. In a table of one million slots, the chance that no two of $n$ keys share a slot is roughly $e^{-n^2/(2m)}$. Setting that to one half gives $n \approx \sqrt{2m \ln 2}$. With $m = 1{,}000{,}000$, $2m \ln 2 = 2{,}000{,}000 \times 0.693147 = 1{,}386{,}294$, whose square root is about 1,177. At $n = 1{,}177$, $n^2/(2m) = 1{,}385{,}329 / 2{,}000{,}000 = 0.6926645$, and $e^{-0.6926645}$ is about 0.5. So a table that is only 0.1177 percent full already has an even chance of a collision.

Knowing the index is therefore only the first half of a lookup. Arriving at slot 262 does not prove that the word there is cat, because another word may have hashed to 262. The stored key must be compared in full once the slot is reached. The hash narrows the search to one slot; the comparison confirms the item.

The method also has limits that follow from the same arithmetic. A hash gives an index, not an identity, so it cannot answer whether a key is present without the key and a comparison. If the table grows too full, or if the hash is poor and clusters keys into a narrow band, the slot holds a crowd and the constant-time hope fails. If the table size changes, every index may change, because the remainder is taken modulo a different $m$. And if two keys have the same bytes, no hash can tell them apart; it only sees bytes.