4 ms·
> 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 valu
by 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
- marginalia_nu 3y agoYeah there's a ton of really cool things you can do with LSHs. They're really overlooked outside of a few niches.
- Solvency 3y agoThe OP mentioned murmur3 due to its speed and high avalanche effect. So what's the best LSH function for this use case?
- dahart 3y agoHi 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.
- Solvency 3y agoI'm basically asking for the most efficient and unavalanched hash map library recommended for the purposes of this use case.
- Solvency 3y agoIs 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?
- marginalia_nu 3y agoAdjacent 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.
- mxkopy 3y agoI 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.
- codebje 3y agoYou can't really say much in general about hash functions - they're just general functions. The more you try to infer additional rules about hash functions, the more use cases you start to exclude. For example, _mostly_ hash functions have a fixed bit size for values in their range, but there's a small handful with variable length output (HAS-V & HAVAL, eg) that would otherwise be considered examples of cryptographic hash functions. At the risk of making absolute statements in a field with vague and imprecise definitions, only perfect hash functions are injective. Imperfect hash functions (typically) map a large domain to a smaller range. The presence of collisions indicates a non-injective function. Surjection is not required for all hash functions. Cryptographic hashes should be surjective, but indexing hashes that not surjective may have other desirable properties. Since in general hash functions are neither injective nor surjective, they're definitely not bijective. You can have bijective hash functions, but the practicality of them would be extremely narrow.
- deleted 3y ago[deleted]
- mxkopy 3y agoYou’d better hope your hashmap is bijective, unless you’re ok with not being able to retrieve some data. Though granted the differentiating aspect of a hashmap AFAIK is the hash function.
- codebje 3y agoThe hash key is only an index, and the same input always gives the same hash value, so you can retrieve your item just fine even if you can't recover the original key from the hashed value. A hash _map_ is not a hash _function_.
- kazinator 3y agoI can easily meet those literal requirements with a function that is total garbage. 1. Take all the input bits and XOR them together. Now we have a value which flips between 0 and 1 every time we change a single bit of the input. 2. Use this value as an index into the sequence { 0xFFFFFFFF, 0xF0F0F0F0 } Now we get 50% of the bits flipping when we change a single bit of the input.
- dahart 3y agoThat doesn’t meet the Avalanche Effect requirements. The requirement is that 50% of the bits change independently (on average) whenever an input bit changes. In other words, the output bit values need to be both random and uniformly distributed relative to every input bit. https://en.wikipedia.org/wiki/Avalanche_effect#Bit_independence_criterion https://en.wikipedia.org/wiki/Avalanche_effect#Bit_independe...
- marginalia_nu 3y agoHold your plucked chicken, Diogenes. Note the "evenly distributed" requirement. This is not. But in general, sure, there's a lot of hash functions that aren't great. f(x)=x is one, that's actually even seen in the wild. Java's Integer class does that for its hashCode() function, and it even does a passable job of indexing a hash table.