// HACKER NEWS — CYBERSECURITY
Speeding Up (Small) Ruby Hashes
Something I must confess is that I absolutely hate writing these blog posts.
It’s not quite as bad as having to give a conference talk, but it’s up there on the list of activities that feel like pulling teeth to me.
Not that I’m not proud of the result.
I absolutely am.
But the process of writing them is very painful for me.
It’s particularly true of the very first sentence, as the post progresses, it gets a bit easier
Yet, I force myself to do it, because it helps me think about problems, and “compile” knowledge in my head.
I’m so terrified of posting something wrong or inaccurate that I tend to double-check some long-held assumptions,
dig into more details about how some things are implemented, etc.
And very often, quickly after publishing the post, I think of new ideas I previously missed.
This post is about one such idea I had right after publishing the previous one on shrinking Ruby hashes.
If you haven’t read it yet, please do, as this one is a direct continuation.
One of the main takeaways from the previous post is that, up to 8 entries, Ruby’s Hash class isn’t truly a Hash Table
as its name would make you think.
Instead, it’s literally an array of pairs.
Let’s look at its data structure:
C can be a little cryptic to the uninitiated, so let me unpack it:
As I mentioned in the previous post, a hint is essentially a single-byte hash-code.
In Ruby, hash-codes are 8 bytes long, and when backed by an st_table (the real hash-table implementation),
the entire hash-code is stored and compared.
But to save memory, ar_table only stores the lower byte of the hash-code.
Fundamentally, that doesn’t change anything, except make hash collisions more likely, but that’s an acceptable
tradeoff when we know we never have any more than 8 keys.
If we were to implement ar_table in Ruby, the structure for {a: 1, b: 2, c: 3} could look like this:
Now let’s look at the core of the ar_table lookup routine, the one I looked at closely while writing the previous post,
but that I never really thought of deeply before then:
As you may be able to see, it’s essentially a linear, AKA O(n), search.
We receive the hint of the key we’re searching for, and linearly search for a match in the table list.