The Invention of Hashing
You’ve heard of Luhn, right? Hans Peter Luhn ? Dude who invented the Hashing Algorithm? Well, for those of you who weren’t paying attention somewhere really early in CompSci 101, there is an excellent writeup on his legacy in IEEE Spectrum . In early 1953, Luhn had written an internal IBM memo in which he suggested putting information into “buckets” in order to speed up a search. Let’s say you wanted to look up a telephone number in a database and find out whom it belonged to. Given the 10-digit number 314–159–2652, a computer could simply search through the list one number at a time until it found the relevant entry. In a database of millions of numbers, though, this could take a while. Luhn’s idea was to assign each entry to a numbered bucket, as follows: The phone number’s digits were grouped into pairs (in this case, 31, 41, 59, 26, 52). The paired digits were then added together (4, 5, 14, 8, 7), from which a new number was generated, consisting of each single...