Hashing in Smalltalk
25 February, 2008
Andrés Valloud has just published “Hashing in Smalltalk: Theory and Practice” on Lulu. He describes the book as providing “a strong foundation for hashing, hash functions, and their application in the context of software development. The first part develops hashing and hash functions from first principles. The behavior characteristics required of hash functions are examined in detail. A thorough description of how hash functions are constructed follows, complete with a rich survey of existing hash functions. But often times existing hash functions are inappropriate for the task at hand. To address this problem, the second part shows how to build novel hash functions that are both efficient and of very high quality for many of the types of data that occur in practice.”
The book compares algorithms and implementations of hashing across the main Smalltalks (Squeak, Dolphin, Visual Works and VisualAge), as well as other languages including C, C++, C#, Java, OCaml and ML. It’s available for $40/€32.20/£22.04 .
Andrés has also posted a great illustration of the dangers of the use of inappropriate hashing functions.
The Weekly Squeak 
26 February, 2008 at 01:34
Any chance this will come out for the Amazon Kindle?
29 February, 2008 at 23:00
Brian,
At this time, the book will only be available through Lulu. Is there a reason why Lulu is not suitable for you?
Thanks,
Andres.
27 August, 2008 at 16:36
Hi Andrés, I just ordered a copy of your book. I can’t wait to get the hard copy in the mail. It’s awesome that you’re publishing via a print on demand publisher! I can’t wait to read your book and expand my brain with the next level of hashing insights that you’ve compiled.
I’m interested in mutli-level hashing, sort of a B-Tree for hashing… one use case is optimizing method look ups in N level class trees, where N is large. To optimize the method selector lookups to *one* look up for any receiver class means an interesting data structure that presents itself as a flattened full method hash table for each class with overridden methods taking into account. Since one wants to minimze the size of this structure in memory to fit into the second level or first level caches of current cpus it can be tricky with the simple version being excluded due to memory cost.
Are any of your hashing examples near this idea? Regardless, I look forward to reading your book!
Cheers,
Peter
27 August, 2008 at 16:39
Andrés, I’m also very interested in how you created your book’s fascinating cover! was it hand drawn or with a program? Did you make it or someone else? Please do tell…
Peter
1 September, 2008 at 22:55
Peter,
Regarding the N-level hashed collections, having N levels implies one will have to perform N lookups. If a hash function exists which will provide good distribution across the whole data set, then it will be faster to use a regular 1-level hashed collection using open addressing (perhaps with hash buckets). There is plenty of discussion regarding these matters in the book.
For the cover, well… I prefer to remain silent on that one. However, my sister has to do with it.
Andres.
1 September, 2008 at 22:56
Oh, also… there is an email address in the introduction. You can use it to contact me directly regarding the book.
Andres.