Hashing

> 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.

Re: Hashing

#7

Post by thecoppinger » Tue, Jun 20, 2023, 12:29 PM UTC

This 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!

Re: Hashing

#8

Post by samwho » Tue, Jun 20, 2023, 12:34 PM UTC

marginalia_nu wrote: post #6

> 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…

I didn't know that, but it makes perfect sense after reading your explanation of it. Thank you, TIL!

Re: Hashing

#9

Post by quickthrower2 » Tue, Jun 20, 2023, 12:49 PM UTC

marginalia_nu wrote: post #6

> 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…

So technically truncating and then padding is a hash function

Re: Hashing

#10

Post by marginalia_nu » Tue, Jun 20, 2023, 12:55 PM UTC

samwho wrote: post #8

marginalia_nu wrote: post #6

> 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…

I didn't know that, but it makes perfect sense after reading your explanation of it. Thank you, TIL!

If 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/ma...