Hashing in Smalltalk

25 February, 2008

Hashing in SmalltalkAndré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.

6 Responses to “Hashing in Smalltalk”

  1. Brian Says:

    Any chance this will come out for the Amazon Kindle?

  2. Andres Says:

    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.


  3. 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


  4. 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


  5. 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.


  6. Oh, also… there is an email address in the introduction. You can use it to contact me directly regarding the book.

    Andres.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: