Data Structures and Algorithms Lecture Notes

25 April 2011 • 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 2006 January 24.