2009/10/22 Andres Valloud <[email protected]>: > Igor et al, >> That's why each of implementations (Dictionary and HashTable) having own >> niche. >> For small sizes, dictionaries in their current state is best. >> For bigger sizes, one could choose to use HashTable, or any other >> implementation, which may fit better. >> > > As long as this refers to objects that implement #hash as #identityHash, > yes. If you can produce a (reasonably efficient) hash function that has > very few collisions, then open addressing with linear probing (the usual > implementation of Set/Dictionary) tends to be the most efficient. >
Well, you can always attack the problem from different side - create a Set and Dictionary which using a perfect hash algorythms. As you may know, a perfect hash is a function which producing unique values for a limited set of elements. So, that in sets hashed using perfect hash function, no collisions possible, and hence the access time to any element is O(1). The drawback of such approach, that finding a perfect hash function for a set of elements is time consuming (best ones, AFAIK, consuming O(k*n) time, where n is number of elements), so you would never want to use a perfect hashing for collections which tend to grow or shrink often. But for collections, which populated once, and then used for read-only access this is worth doing. And its quite easy to modify current classes to use a perfect hash: just add a perfectHash ivar to it, and if its not nil , then use it to find an index of item. And if perfectHash is nil, then we just use the current implementation. And of course, you need to implement a perfect hash search, which standing aside :) But then you could just do: set := something collect: [... ] asSet rehashWithPerfectHash. and voila, you got a set with no collisions :) > Andres. > > _______________________________________________ > Pharo-project mailing list > [email protected] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
