Be careful because (I think) Pharo has significantly changed the HashedCollection in comparison with Squeak, hasn't it ?
On Mon, Nov 28, 2011 at 5:33 PM, Nicolas Cellier < [email protected]> wrote: > The Squeak trunk version is: > > I am an abstract collection of objects that implement hash and > equality in a consitent way. This means that whenever two objects are > equal, their hashes have to be equal too. If two objects are equal > then I can only store one of them. Hashes are expected to be integers > (preferably SmallIntegers). I also expect that the objects contained > by me do not change their hashes. If that happens, hash invariants > have to be re-established, which can be done by #rehash. > > Since I'm abstract, no instances of me should exist. My subclasses > should implement #scanFor:, #fixCollisionsFrom: and > #noCheckNoGrowFillFrom:. > > Instance Variables > array: <ArrayedCollection> (typically Array or WeakArray) > tally: <Integer> (non-negative) > > array > - An array whose size is a prime number, it's non-nil elements are > the elements of the collection, and whose nil elements are empty > slots. There is always at least one nil. In fact I try to keep my > "load" at 75% or less so that hashing will work well. > > tally > - The number of elements in the collection. The array size is always > greater than this. > > Implementation details: > I implement a hash table which uses open addressing with linear > probing as the method of collision resolution. Searching for an > element or a free slot for an element is done by #scanFor: which > should return the index of the slot in array corresponding to it's > argument. When an element is removed #fixCollisionsFrom: should rehash > all elements in array between the original index of the removed > element, wrapping around after the last slot until reaching an empty > slot. My maximum load factor (75%) is hardcoded in #atNewIndex:put:, > so it can only be changed by overriding that method. When my load > factor reaches this limit I replace my array with a larger one (see > #grow) ensuring that my load factor will be less than or equal to 50%. > The new array is filled by #noCheckNoGrowFillFrom: which should use > #scanForEmptySlotFor: instead of #scanFor: for better performance. I > do not shrink. > > > 2011/11/28 Stéphane Ducasse <[email protected]>: > > I'm an abstract class supporting dictionary based data structure. I > provide access to my elements based on their hash. > > > > Stef > > > > On Nov 28, 2011, at 4:29 PM, Sean P. DeNigris wrote: > > > >> Today: HashedCollection > >> > >> > >> Comment Of The Day Contest - One Day One Comment > >> Rules: > >> #1: Each day a not commented class is elected. Each day the best comment > >> will be integrated with name of the author(s). > >> #2: If you cannot comment it, deprecate it. > >> Results: http://code.google.com/p/pharo/wiki/CommentOfTheDayContest > >> > >> -- > >> View this message in context: > http://forum.world.st/COTDC-85-HashedCollection-tp4115592p4115592.html > >> Sent from the Pharo Smalltalk mailing list archive at Nabble.com. > >> > > > > > > > > -- Mariano http://marianopeck.wordpress.com
