Thursday, May 10, 2007

The BAD Library

Not long after my last post I wrote some code to get some rough timings, and also to experiment with variations of hash tables that my textbooks never taught me: with cuckoo hashing you can have expected constant-time insertion and worst-case lookup time. Additionally, with cells, you get hash tables that can handle over 90% load. Also, hash functions recommended by classic textbooks are no good: Bob Jenkins' hash functions are much better.

Along the way I had to implement (or import from other projects of mine) other abstract data types. Soon I had crit-bit trees, hash tables, linked lists and dynamic arrays.

I finally got around to packaging it up: bad-0.0.0.tar.bz2.

BAD stands for Ben's Abstract Datatype, and also refers to the current state of the code and documentation. See the README for the preliminary results.