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

41–50 of 68 posts

Re: Hashing

#41

Post by Solvency »

dahart wrote: post #37
Solvency wrote: post #24

Earlier quoted context omitted.

The OP mentioned murmur3 due to its speed and high avalanche effect. So what's the best LSH function for this use case?

Hi I’m not sure I understand the question. Avalanche and local sensitivity are opposing goals, so typically the more avalanche, the less locally sensitive, and vice versa. You could even state the avalanche goal as being locally insensitive - the whole idea of avalanche is one bit change in the input produces a maximally different and uniformly distributed output.

I'm basically asking for the most efficient and unavalanched hash map library recommended for the purposes of this use case.

Re: Hashing

#42

Post by marginalia_nu »

Solvency wrote: post #41
dahart wrote: post #37

Earlier quoted context omitted.

Hi I’m not sure I understand the question. Avalanche and local sensitivity are opposing goals, so typically the more avalanche, the less locally sensitive, and vice versa. You could even state the avalanche goal as being locally insensitive - the whole idea of avalanche is one bit change in the input produces a maximally different and uniformly distributed output.

I'm basically asking for the most efficient and unavalanched hash map library recommended for the purposes of this use case.

I don't think you're gonna get one-size-fits-all answers the same way you will with avalanching hash functions. They can be one-size-fits-all because the requirement is that there is no (discernible) correlation between the input and output.

Locality-sensitive hashes depend on what sort of thing you are hashing. Is the data ordered, is it a sequence, is it points in space? The requirement is that given similarity in the input given a specific metric, there is a similarity in the output given another metric.

There are no universal locality sensitive hash functions because the function depends on in what sense you're trying to preserve locality.

Re: Hashing

#43

Post by vlovich123 »

I’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)

Re: Hashing

#44

Post by dahart »

Solvency wrote: post #41
dahart wrote: post #37

Earlier quoted context omitted.

Hi I’m not sure I understand the question. Avalanche and local sensitivity are opposing goals, so typically the more avalanche, the less locally sensitive, and vice versa. You could even state the avalanche goal as being locally insensitive - the whole idea of avalanche is one bit change in the input produces a maximally different and uniformly distributed output.

I'm basically asking for the most efficient and unavalanched hash map library recommended for the purposes of this use case.

Ah, got it. I don’t even know of one, TBH, let alone have a best one in mind. Every time I’ve used an LSH, the hashing code has been ad-hoc and tailored to pretty specific data and optimization goals. (An added layer of difficulty is that “locality” isn’t universally defined.)

I’m not sure but it might be simplest to just look for a decent Map library in your favorite language, and keep the hashing part separate. It’s generally very easy to insert your own hash transform wherever you need, whether it’s on the fly, or saved as a sort key in memory. This way all you would need is to find a Morton order function, for example, if you want to hash with a z-order curve.

Re: Hashing

#45

Post by mxkopy »

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 feel like there's a more general concept of "bijective index" that subsumes LSHs and cryptographic hashes. When I think of hash I usually think of modulos, randomness, etc. when in general they're just ways of creating a set that's 1:1 to your inputs.

Re: Hashing

#46

Post by samwho »

vlovich123 wrote: post #43

I’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)

This 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. :)

Re: Hashing

#47

Post by Solvency »

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…

One thing I wish the original article would explain is the use case of buckets. I'm sort of imagining weird use cases where the buckets represent different servers or storage systems for the purpose of spreading out data efficiently...but I'm totally guessing here. Because I would assume a proper load balancer would be based on the dynamics of real-time server performance, not because of some simple hash function. What are common hash to bucket use cases?

Re: Hashing

#48

Post by samwho »

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

One thing I wish the original article would explain is the use case of buckets. I'm sort of imagining weird use cases where the buckets represent different servers or storage systems for the purpose of spreading out data efficiently...but I'm totally guessing here. Because I would assume a proper load balancer would be based on the dynamics of real-time server performance, not because of some simple hash function. Wh…

The buckets, in the context of hash maps, are typically lists. Either arrays or linked lists. They're used to store the key-value pairs.

Some load balancers do use hashing in much the same way hash maps do. Usually they'll take a combination of: source IP, source port, destination IP, destination port, and hash it. They'll then use that hash to pick a server. The practical impact of this is that each user always gets mapped to the same server. This is typically called "session sticky load balancing" because it means session information about that user can live on the server, safe in the knowledge that the user will always end up on that server and not get routed to any others.

Re: Hashing

#49

Post by moonchild »

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…

Perhaps look at some of what paul khuong has written about umash; it is dense, but good, and includes good references.

Re: Hashing

#50

Post by sudobash1 »

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

Post reply on HN