Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Hashing

samwho.dev

Post reply on HN
Print view View original

21–30 of 68 posts

Re: Hashing

#21

Post by marginalia_nu »

dahart wrote: post #19
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…

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

Yeah there's a ton of really cool things you can do with LSHs. They're really overlooked outside of a few niches.

Re: Hashing

#22

Post by photochemsyn »

Very 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/4955...

Re: Hashing

#23

Post by Solvency »

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…

Is there a world in which hashes could be used as an alternative to word2vec style vector embeddings? Where you basically convert text inputs to an ideal fixed width representation and then calculate the "similarity" between them to derive some kind of meaning?

Re: Hashing

#24

Post by Solvency »

dahart wrote: post #19
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…

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

The OP mentioned murmur3 due to its speed and high avalanche effect.

So what's the best LSH function for this use case?

Re: Hashing

#26

Post by marginalia_nu »

Solvency wrote: post #23
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…

Is there a world in which hashes could be used as an alternative to word2vec style vector embeddings? Where you basically convert text inputs to an ideal fixed width representation and then calculate the "similarity" between them to derive some kind of meaning?

Adjacent algorithms are used all over that space.

In general random projection, which is used to for dimension reduction in vector spaces, can also be used to construct LSHs; for example.

Re: Hashing

#28

Post by aappleby »

samwho wrote: post #16
michael_leachim wrote: post #14

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

I'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 ) makes it seem like it's trial and error.

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

Re: Hashing

#29

Post by ComputerGuru »

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

Re: Hashing

#30

Post by aappleby »

ComputerGuru wrote: post #29

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

If 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
Post reply on HN