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

61–68 of 68 posts

Re: Hashing

#61

Post by dahart »

kazinator wrote: post #60
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 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.

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

Re: Hashing

#62

Post by omarelb »

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

Re: Hashing

#63

Post by samwho »

omarelb wrote: post #62

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

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

Re: Hashing

#64

Post by marginalia_nu »

kazinator wrote: post #60
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 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.

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

Re: Hashing

#65

Post by [deleted] »

codebje wrote: post #58
mxkopy wrote: post #45

Earlier quoted context omitted.

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.

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

[deleted]

Re: Hashing

#66

Post by mxkopy »

codebje wrote: post #58
mxkopy wrote: post #45

Earlier quoted context omitted.

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.

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

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

Re: Hashing

#67

Post by codebje »

mxkopy wrote: post #66
codebje wrote: post #58

Earlier quoted context omitted.

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

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

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

Re: Hashing

#68

Post by mxkopy »

codebje wrote: post #67
mxkopy wrote: post #66

Earlier quoted context omitted.

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

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

> the same input always gives the same hash value, so you can retrieve your item just fine

You’ll retrieve a bunch of items that hash to the same value, so not exactly. You can retrieve the set of items that have the same hash as your item just fine - which is not exactly the same.

> A hash _map_ is not a hash _function_.

This is more or less what I was getting at. I know hash functions aren’t bijective, but hashmaps are often used as if they are. I guess I’m not sure if LSHs refer to a family of functions or hashmaps, and I guess the word hashes often implies functions - my bad.

Post reply on HN