3 ms·

One interesting alternative to hash tables that appears to get too little love is the Judy tree: https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.o

by krylon 10y ago

One interesting alternative to hash tables that appears to get too little love is the Judy tree: https://en.wikipedia.org/wiki/Judy_array https://en.wikipedia.org/wiki/Judy_array They are not quite as versatile, I think, but for simple cases where your keys are strings or ints, they work just as well and are quite fast, too. The API is very simple, too. I don't do much programming in C these days (pretty much none at all), but I used Judy in one toy project and have fond memories of it.

stuxnet79 10y ago
Gotta love HN. I'm always learning new stuff. Thanks for posting this. The "Judy Shop Manual" (http://judy.sourceforge.net/application/shop_interm.pdf http://judy.sourceforge.net/application/shop_interm.pdf) looks very complicated so I don't know if I should take the time to fully understand how they work, especially if they are not as versatile as hash tables.
- krylon 10y ago
  Judy's author appears to have poured bathtubs full of cleverness into his brainchild to make it fast at the cost of implementation complexity. As long as you don't look behind the curtain, it's genius - an API so simple a child could use it, and it's so fast... But try to understand how it works, and your brain melts. Well, mine, at least. Then again, I suspect the same can be said of what used to be called the STL, or Boost. In a library that is meant to be used by lots of other projects, the trade-off is legitimate.
matheweis 10y ago
Neat! I developed something similar back in college in JAVA - it was a ternary radix tree, and wow was that thing fast... something like only about 10% slower than HashMap for storing the entire English dictionary and looking up an arbitrary string a million times. There were all sorts of other interesting advantages relative to hash tables since I kept it sorted... you could retrieve an element and then find five adjacent elements. Handy for something like a dictionary app etc.

by krylon 10y ago

stuxnet79 10y ago

Gotta love HN. I'm always learning new stuff. Thanks for posting this. The "Judy Shop Manual" (http://judy.sourceforge.net/application/shop_interm.pdf http://judy.sourceforge.net/application/shop_interm.pdf) looks very complicated so I don't know if I should take the time to fully understand how they work, especially if they are not as versatile as hash tables.

krylon 10y ago
Judy's author appears to have poured bathtubs full of cleverness into his brainchild to make it fast at the cost of implementation complexity. As long as you don't look behind the curtain, it's genius - an API so simple a child could use it, and it's so fast... But try to understand how it works, and your brain melts. Well, mine, at least. Then again, I suspect the same can be said of what used to be called the STL, or Boost. In a library that is meant to be used by lots of other projects, the trade-off is legitimate.

matheweis 10y ago

Neat! I developed something similar back in college in JAVA - it was a ternary radix tree, and wow was that thing fast... something like only about 10% slower than HashMap for storing the entire English dictionary and looking up an arbitrary string a million times. There were all sorts of other interesting advantages relative to hash tables since I kept it sorted... you could retrieve an element and then find five adjacent elements. Handy for something like a dictionary app etc.