Fun fact! A previous use of the term "adaptive hash" was as a descriptor for things like Bcrypt, which have the exact opposite goal (to consistently be as slow as possible regardless of advances in hardware).
Nevermark 18 hours ago [-]
So we just flip a sign in Bcrypt! Or flip a decision Boolean? Or a sort order?
Regardless it will be easy. Apply the inverse operation of the “introduce more slowness” operation.
Unfortunately, I have seen some software in my day, and I don’t think it will work. Just really perverse stuff.
90s_dev 1 days ago [-]
"tptacek's law: given enough time, diametrically opposed algorithms will have the same name"
tptacek 1 days ago [-]
Yes! See: quicksort.
1 days ago [-]
tialaramex 20 hours ago [-]
Huh? What's the other "quicksort" ? Tony's famous Quicksort I'm aware of, and while you should not use this algorithm this century† in its pure form it's still in the core of good sorts, you just need other ingredients too.
So what's the diametrically opposed algorithms with the same name ?
† Don't tell C++ programmers, some of their standard libraries only stopped shipping quicksort as the default algorithm during the Biden administration.
heisig 1 days ago [-]
Let me comment as an SBCL user: This is outstanding work, and I can now remove a lot of performance hacks from my code because the default hash tables became equally fast!
Also, this technique eliminates a number of worst-case scenarios and inefficiencies, which is a boon for any hash table user.
vlovich123 1 days ago [-]
> For string keys, hash only the first and last 2 characters.
For list keys, only hash the first 4 elements.
I would think it make some sense to change these constants as the collision chain grows, thereby improving the hash quality of keys and avoiding collisions as the table gets larger and larger
Regardless it will be easy. Apply the inverse operation of the “introduce more slowness” operation.
Unfortunately, I have seen some software in my day, and I don’t think it will work. Just really perverse stuff.
So what's the diametrically opposed algorithms with the same name ?
† Don't tell C++ programmers, some of their standard libraries only stopped shipping quicksort as the default algorithm during the Biden administration.
Also, this technique eliminates a number of worst-case scenarios and inefficiencies, which is a boon for any hash table user.
I would think it make some sense to change these constants as the collision chain grows, thereby improving the hash quality of keys and avoiding collisions as the table gets larger and larger