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-digit result or, in the case of a double-digit result, just the last digit (yielding 45487). The original phone number and the name or address corresponding to it would then be put into a bucket labeled 45487.
Looking up an entry from a phone number involved quickly calculating the bucket number using Luhn’s method and then retrieving the information from that bucket. Even if each bucket contained multiple entries, sequentially searching through a single bucket was much faster than searching the entire list.
Over the decades, computer scientists and programmers have improved on Luhn’s methods and pushed them to new uses. But the basic idea is still the same: Use a math problem to organize data into easily searchable buckets. Because organizing and searching for data are such widespread problems in computing, hashing algorithms have become crucial to cryptography, graphics, telecommunications, and biology. Every time you send a credit card number over the Web or use your word processor’s dictionary, hash functions are at work.
Go read the rest at https://spectrum.ieee.org/tech-history/silicon-revolution/hans-peter-luhn-and-the-birth-of-the-hashing-algorithm

Comments

Post a Comment

Popular posts from this blog

Erlang, Binaries, and Garbage Collection (Sigh)

-
Image
The nice thing about garbage-collection is that it is makes memory management absolutely transparent to you Of course, the above is true right up to the point when it stops being transparent, at which point it does a phase change from nice to clusterf**k of biblical proportions .  There are entire posts, books, and suicide notes that have been written about this, and I have no great desire to add to them, save with the minor comment that paranoia about garbage-collection is still justified , albeit only in the edge-cases for most people. That said, I'll give you that Erlang GC is in many ways much, much better positioned in this regard than, oh, Java, but it still rears up and bites you in the butt when you least expect it. ( More information about Erlang's GC vis-a-vis Java here , and Jesper's truly excellent description of Erlang's GC here ).  A story from the past should serve to illustrate this. Once upon a time, in a magical land far far away - well, Her...
Read more

Spot The Difference — Deep Learning Edition

-
Image
You’ve played  Spot The Difference  at some point, right? (Of course you did. We  all  did  ). Think about what you actually did when you were trying to Spot The Difference — in fact, just do it again with SpongeBob juggling above. You’re probably doing something like 1. Quick glance to the left. 2. Quick glance to the right 3. “ Spatula on the left. Wonder if there is one on the right? ” 4. “ Yup, there is. Sriracha on the right. Is that on the left? ” 5. “ Nope! It’s a ketchup bottle on the left! And there is nothing on the plate below it! ” etc. To summarize, what you’re basically doing is looking at each image alternately, identifying objects in each image, and trying to find the same object in the other image. As it turns out, what most Deep Learning systems do is something quite different. They basically do something like this 1. Figure out everything in the first image (“ ketchup bottle at 1 o-clock, empty plate at 3 o-clock, spatula at 1...
Read more