Lecture notes for CS 503, Advanced Programming I

Advanced Programming I Lecture Notes

4 April 2006 • Hashing Basics

For example, it is frequently helpful if string hashes have the potential to hash palindromes to different values, so that, for example, hash("otto") ≠ hash("toot").

The hash code

h = 0
for i = 1 to n
  h = h xor str[i]

does not distinguish palindromes (because xor is commutative), while the hash code

h = 0
for i = 1 to n
  h = (h << 1) xor str[i]

(potentially) does. Note that the pidgeon-hole principle makes it impossible to guarentee that all palendromes can be distingushed.

This page last modified on 24 January 2006.