In general terms, open addressing with linear probing should tie or beat chaining. For this to happen, the hash function used must be of high quality. If chaining is beating open addressing with linear probing, I'd strongly suspect that the hash function used is producing significant collisions or unevenly distributed values for the data set in question. You may want to take a look at the Hash Analysis Tool I wrote for VW (it's in the public Store repository under a MIT license). For a more in-depth treatment of these matters, you may also want to look at the hash book I wrote (www.lulu.com/avSmalltalkBooks), and its matching Smalltalk Solutions 2008 presentation (http://video.google.com/videoplay?docid=-7510297003494499688&hl=en#). Andres. Lukas Renggli wrote:
2009/10/20 Laval Jannik <jannik.laval@gmail.com>:
Hi, Since some weeks, We use in our projects the project HashTable, available at http://www.squeaksource.com/ht.html It could be a good idea to integrate these collections to replace Dictionary and Set.
I don't think that this is generally a good idea. It might be beneficial in your situation, but certainly not for everybody in all situations. I've been using the HashTable implementation in several projects with great success. In other projects I've been using the BTree package on SqueakSource that provides similar functionality optimized for yet another context. These highly specialized data structures should only be applied if they make sense in the given context (and if you understand both, the cost and gain). I guess this was exactly the reason why SkipList was removed from the Pharo image.
Lukas