anagram
A word made by rearranging the letters of another word, such as "listen" and "silent".
In more detail
A hash that simply adds up character codes gives every anagram the same value, so an attacker can generate thousands of colliding keys trivially. The course uses anagram keys to show why position must affect a string hash. A polynomial rolling hash avoids this weakness.
Related terms
- collision — Two different keys producing the same hash, or the same slot in a hash table.
- polynomial rolling hash — A string hash that treats the characters as digits of a number in some base, such as 31, and reduces the result modulo the table size.
- hash flooding — An attack that sends a server many keys crafted to collide in its hash tables, turning each O(1) operation into O(n) and exhausting its CPU.
Taught in
- Collisions In Practice And Hash Flooding — Algorithms & Data Structures for Working Engineers