7 ms·
Hashing
- arek_nawo 3y agoThat's a good, visual primer! Congrats.
- samwho 3y agoThank you <3
- edvards 3y agoAmazingly well done article, thanks for sharing and making it!
- samwho 3y agoThank you! I absolutely love making these, and have plans for several more.
- marginalia_nu 3y ago> The Avalance Effect > Another way hash functions get evaluated is on something called the "avalanche effect." This refers to how many bits in the output value change when just a single bit of the input changes. To say that a hash function has a good avalanche effect, a single bit flip in the input should result in an average of 50% the output bits flipping. I think it's important to note that this isn't a property that is necessary for a hash function, there are hash functions that deliberately try to minimize the avalanche effect, such as in locality sensitive hashing; which is another form of hash function that has different use cases that are also very cool. You can use LSHs to for example remove near duplicate search results in a search engine without having to actually comparing the texts, even tolerating single-word differences; or to help with nearest neighbor searches. A lot of what's written about hash function tends to assume you want to use them for whatever thing the author has in mind, it's not a unique fault of the author -- many textbooks have this problem, and add all these properties to them that are accidental to what a hash function actually is; it's really just a mapping function to a fixed width representation with an even distribution across the domain.
- samwho 3y agoI didn't know that, but it makes perfect sense after reading your explanation of it. Thank you, TIL!
- marginalia_nu 3y agoIf you're interested, I built a stupid simple deduplication algorithm[1]. It ironically uses the avalanche effect of another hash function to implement random projection onto a locality preserving bit vector. It sounds like real computer science bingo but it's actually surprisingly simple and it works much better than it has any business doing. [1] https://github.com/MarginaliaSearch/MarginaliaSearch/blob/master/code/libraries/easy-lsh/src/main/java/nu/marginalia/lsh/EasyLSH.java https://github.com/MarginaliaSearch/MarginaliaSearch/blob/ma...
- quickthrower2 3y agoSo technically truncating and then padding is a hash function
- dahart 3y ago> You can use LSHs […] to help with nearest neighbor searches. Yes! A good example of this in graphics is a spatial nearest neighbor search. Space filling curves like the Morton and Hilbert curves are often used as hash functions that can preserve some amount of locality for 2-D / 3-D / N-D points. A locally sensitive hash function can basically be used to provide a sort key for data that doesn’t otherwise have a key, while increasing the odds that any two keys that are similar point to data that are also similar. This is useful on GPUs in order to improve coherence/performance of threads operating on spatial points. https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Z-order_curve https://en.wikipedia.org/wiki/Hilbert_curve https://en.wikipedia.org/wiki/Hilbert_curve
- thecoppinger 3y agoThis guide, just like your others, gave me the gift of several ‘ah-ha’ moments that not only helped hash maps click, but also several other linked concepts. Thank you so much for making the time and effort to create such quality content. Please keep producing more!
- mcdonje 3y agoBetween Sam and Bartosz, I think it's time to bite the bullet and get an RSS reader set up. Anyone got any good app recommendations for Android?
- samwho 3y agoTo be mentioned in the same breath as Bartosz Ciechanowski is an incredible compliment, thank you <3 I will say up front: my posts don't read well in an RSS reader. Sorry about that. But at least you'll get a notification when new ones come out.
- anayak 3y agoFantastic article! Love the visualizations and your explanations are concise and very clear.
- samwho 3y agoThank you! I'm really glad you liked it.
- michael_leachim 3y agocool, I enjoyed reading article and playing with visualizations. I liked it a lot. How can I learn to design a hash function? It is possible to understand that stringSum is bad compared to murmur3 by evaluating it against test cases, but what properties make it bad. Is it summation compared to xoring in murmur3? I intuit that summation is kinda lossy, but ofc there is much more rigorous work put into it. It would be really cool to learn more about this. Thank you
- samwho 3y agoI'm actually not sure, to be honest. The post explicitly doesn't touch on the implementation of murmur3, and part of the reason is that while I can see what it's doing, I have no idea why it's doing it. The initial announcement of murmur (https://tanjent.livejournal.com/756623.html https://tanjent.livejournal.com/756623.html) makes it seem like it's trial and error.
- aappleby 3y agoMurmur author here, it is a lot of trial and error but in general you're trying to pack as much "nonlinearity" as possible into as few instructions as possible. Multiplication is commutative, xor is commutative, but if you mix the two together you get functions that are strongly non-linear (in the algebra sense) because the mathematical "spaces" of integers and bits aren't connected together the same way. Ensuring that the nonlinearity applies to all the bits roughly equally is hard and requires trial and error.
- dahart 3y agoThe famous Bob Jenkins has lots of info on hash function design: http://www.burtleburtle.net/bob/index.html http://www.burtleburtle.net/bob/index.html http://www.burtleburtle.net/bob/hash/index.html http://www.burtleburtle.net/bob/hash/index.html
- moonchild 3y agoPerhaps look at some of what paul khuong has written about umash; it is dense, but good, and includes good references.
- photochemsyn 3y agoVery clear explanation! There's also a famous answer on SO that goes into collisions and has similar visual maps for viewing how random the hashing distributions are for a variety of different non-cryptographic hashing algorithms (top answer): https://softwareengineering.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed https://softwareengineering.stackexchange.com/questions/4955...
- samwho 3y agoI saw this during the writing of the post! Extremely cool, I mention it a little in my behind-the-scenes post.
- aappleby 3y agoMurmur3 author here, very nice writeup.
- samwho 3y agoThank you! That puts to bed some of my anxieties around whether I’ve misrepresented the qualities of murmur3
- ComputerGuru 3y agoGreat intro to hashing but if the concept of mmhash3’s seed is going to be brought up I think it’s only natural to mention its design limitations and why you still need something actually ddos resistant like SIP hash (even if we don’t get into the details of the latter). Also, it’s important to distinguish between hashing, hashing, and hashing. That is, hashing to map input to buckets, hashing to obscure the original string, and hashing to find similarities in the input data. They’re all called hashing but they have different (and conflicting!) requirements. There’s a reason you want mmhash3 to be fast but scrypt to be slow, and a reason why you want mmhash3 to avalanche but certainly don’t want your perceptual hashing algo of choice to do the same.
- aappleby 3y agoIf I ever write Murmur4 it's going to be the smallest function that I can prove (via sat solver) to have no seed-independent collisions :D
- ComputerGuru 3y agoI approve of the use of relative metrics, Austin! Just be prepared for mmhash4 to be a few megabytes in size ;)
- samwho 3y agoI did have the distinction between cryptographic and non-cryptographic in there originally but found when junior folks read it they’d get confused about which use-case was being discussed. So I decided to focus on just one. With more time, I would have liked to cover at least scrypt. I’ll be honest, I don’t know what the design limitations of the seeding in murmur3 are. What I wanted to show is the concept of seeding and what it’s there to prevent. I’m hoping that comes across, even without any deeper exploration of seeding.
- ComputerGuru 3y agoSeeding is kind of a hack. It doesn’t guarantee you’ll avoid a (or even the same) collision, and quite a few “popular” hashes only change the output (but don’t change whether or not there is a collision) when you change the seed. Thanks for the article, though!
- deleted 3y ago[deleted]
- mpartel 3y agoExcellent work, again! Your intros somehow elicit the best out of HN too: the comments are always full of interesting angles and variations. Wanna do quaternions next? :) Many have tried..
- samwho 3y agoThere’s a name I haven’t heard for a long time. Thank you, sir! As soon as I can reliably spell “quaternions” I will think about trying it. Funnily, one of the ideas I have cooking in my head is going to require a foray into 3D.
- vlovich123 3y agoI’m surprised xxhash wasn’t mentioned. Isn’t it faster and more hash collision resistant than murmur? I think I read a very good website on another hash proposal that can supersede xxhash (roughly similar performance but more methodical in construction and has other nice properties) but I can’t recall what it’s called (it’s not on the smasher tests yet if I recall correctly)
- samwho 3y agoThis was purely due to familiarity. I knew murmur3 was considered a good, current hashing algorithm. I was able to find a good implementation of it in JS, so I didn't really look any further. Thanks for exposing me to xxhash! I'll store that away as an alternative to murmur3 if I ever need one in future. :)
- sudobash1 3y agoOff-topic, but it just occurred to me that the "dialog" in this article between the author and the "Haskie" dog is a very traditional way of writing pedagogical works. Some historical examples of books written in this way are Galileo's "Dialogue Concerning the Two Chief World Systems" (the one that landed him in hot water), and "The Study of Counterpoint" by Johann Joseph Fux (also in the 17th century). A small excerpt from "The Study of Counterpoint": >Joseph.— Why did you leave out B between A and C? > Aloys.— Because it has no perfect fifth and therefore cannot be the final of a mode -- which we shall discuss more fully in its proper place. Both of these books are written as an entire discussion or argument, as was commonplace in teaching books. I honestly often find myself disliking it, but I think it is a great way to learn for many people.
- samwho 3y agoI didn't know this. I created Haskie during the writing of my Memory Allocation post because I found myself trying to pre-empt reader questions a lot and it was weird to read. Creating a proxy for the reader in Haskie made it flow a lot better. I've noticed in this post that a 2nd character that's a proxy for an "expert" in a topic would also be handy. Taking suggestions for a good dog breed to represent this character.
- d--b 3y agoGood stuff. I’d perhaps add a paragraph on bcrypt and why it must be slow.
- koromak 3y agoIts kind of confusing that the author use JS objects (aka hashes) as an entry inside the HashMap he's building. I think building the concept of a hash from the ground up would be more illuminating.
- samwho 3y agoI agonised over this. I did originally have a version that used 2-element arrays instead, but the resulting code felt more dense and hard to follow. I figured that people who know enough to point this out already know what's up. People who don't will benefit from the code being easier to read.
- omarelb 3y agoThanks for the delightful read! I would've also liked to know how hash maps are typically implemented in programming languages. For instance how the number of buckets is chosen and if buckets are added at runtime when the amount of items in the map changes. But I'll do some further research myself!
- samwho 3y agoYou're welcome! I deliberately didn't go in to that for a few reasons. 1. It would have made this article very, very long. 2. It's a bit out of scope for an article on hashing. 3. I think I might give hash maps their own article in future. Hash maps are fantastically deep. So many different ways to do it. You'll find a lot of material online but I'd recommend Raymond Hettinger's talk on how Pythons hash map data structure has evolved over time: https://www.youtube.com/watch?v=p33CVV29OG8 https://www.youtube.com/watch?v=p33CVV29OG8.