Good stuff.
I’d perhaps add a paragraph on bcrypt and why it must be slow.
Hashing
51–60 of 68 posts
Re: Hashing
#52Its kind of confusing that the author use JS objects (aka hashes) as an entry inside the HashMap he's building. I think building the concept of a hash from the ground up would be more illuminating.
Re: Hashing
#53Great 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 idea of "buckets" here is purely to speed up search time, at a very low level. Don't think about it in the context of a web server or database storage, its way more base than that. Its literally just arrays in memory.
The idea is: if you don't have a Hash or Map already implemented in your language, how would you build a fast one? You cant write my_object['my_key'], that doesn't exist, you don't have Key-Value storage. You need instead to somehow store those pieces of information, and find them later.
Obviously, you could just stick every value inside one big array. Then when you call MyHash.get('key'), you simply do an array search. But that would be slow.
Instead, you can hash the 'key', stick it into a smaller bucket based on the hash, and then more quickly search for it later. In the future, you know the hash of 'key', so you know which bucket to look in.
The author does make it confusing, since in their example each bucket contains Entry (entry['value']), meaning they are already using a JS HashMap implementation in their rebuilding of a HashMap, but you could rewrite the example to do it without any objects. The code would be harder to read though.
Re: Hashing
#54Off-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 excer…
I didn't know this. I created Haskie during the writing of my Memory Allocation post because I found myself trying to pre-empt reader questions a lot and it was weird to read. Creating a proxy for the reader in Haskie made it flow a lot better.
I've noticed in this post that a 2nd character that's a proxy for an "expert" in a topic would also be handy. Taking suggestions for a good dog breed to represent this character.
Re: Hashing
#55Earlier quoted context omitted.
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 idea of "buckets" here is purely to speed up search time, at a very low level. Don't think about it in the context of a web server or database storage, its way more base than that. Its literally just arrays in memory. The idea is: if you don't have a Hash or Map already implemented in your language, how would you build a fast one? You cant write my_object['my_key'], that doesn't exist, you don't have Key-Value st…
This is my eternal struggle: be correct, or be simple.
I wrote a version that used 2-element arrays but the code became more dense and I worried about losing people. I was hoping that how easy it would be to translate it to not use objects would give me a pass here, but apparently not :D
Re: Hashing
#56Its kind of confusing that the author use JS objects (aka hashes) as an entry inside the HashMap he's building. I think building the concept of a hash from the ground up would be more illuminating.
I agonised over this. I did originally have a version that used 2-element arrays instead, but the resulting code felt more dense and hard to follow.
I figured that people who know enough to point this out already know what's up. People who don't will benefit from the code being easier to read.
Re: Hashing
#57Very 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...
I saw this during the writing of the post! Extremely cool, I mention it a little in my behind-the-scenes post.
Re: Hashing
#58> 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.
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 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.
Re: Hashing
#59> 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
Technically the identity function on 64-bit integers is a hash function. There's just not much you can say about hash functions in general.
Re: Hashing
#60> 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.