[Pharo-project] [COTDC] 85 - HashedCollection
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.
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.
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 <stephane.ducasse@inria.fr>:
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.
thanks this is a good one! Stef On Nov 28, 2011, at 5:33 PM, Nicolas Cellier 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 <stephane.ducasse@inria.fr>:
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.
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 < nicolas.cellier.aka.nice@gmail.com> 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 <stephane.ducasse@inria.fr>:
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
participants (4)
-
Mariano Martinez Peck -
Nicolas Cellier -
Sean P. DeNigris -
Stéphane Ducasse