Good read: cPython's dictionary implementation

Tim Peters is very good at practical algorithm design. He one of the primary designers of the Python dictionary algorithms. His sort algorithm (timsort) is also pretty cool. Also check out the Knights Tour and N-Queens algorithms in the unit tests: <http://svn.python.org/view/python/trunk/Lib/test/test_genera... .

The introductory comments are an excellent read about the pragmatics of good hash table design. It would have been really helpful a couple of decades back when I was routinely implementing custom hash tables. OTOH tuning the probe parameters for a table was always an entertaining way to spend an afternoon. Generating a perfect hash for an evolving keyword table was too cumbersome, but trying to reach nearly every symbol in a dense table with a single probe was good sport.

http://svn.python.org/view/python/trunk/Objects/dictnotes.tx... is a great summary of the issues.

iirc isn't there a chapter in Beautiful Code about this? http://oreilly.com/catalog/9780596510046