A hash function deterministically turns an input key or string into a value, often an index or a number that can be compared quickly. In a hash map, the value helps locate a key; in Rabin–Karp, it represents a pattern or text window. section 1.4.1 section 4.0
The result depends on the function: different inputs can produce the same hash, a collision. In string searching, a hash match is only a candidate match, so compare the actual characters to rule out false matches. section 4.1 section 4.4
A collision in string matching
A simple addition-based hash can give ACT and CAT the same value. Giving characters different positional weights, such as powers of 10, reduces this collision; a rolling hash then updates the window’s value as characters enter and leave. section 4.4 section 4.1
Figure 4.4 Two substrings previously with a simple hash function yield the same hash value. When the hash function is changed using powers of 10, the same two substrings yield different hash values. This reduces the problem of collision.
Compare how a simple hash collides and how positional weights distinguish the substrings. section 4.1


















