Andres Valloud a écrit :
> sig wrote:
>> look at MaDictionary class comment.
>>
>> both dictionaries used in comparison tests populated simply using just:
>>
>> obj := Object new.
>> dict at: obj put: obj.
> I don't have a Squeak image handy right now, but I'd suggest checking 
> these cases out...
> 
> Time it takes to add all strings in the image to a dictionary.
> 
> Time it takes to add all symbols in the image to a dictionary.
> 
> Time it takes to add 100k consecutive integers as keys of a dictionary.
> 
> Thanks,
> Andres.
> 

sig's BucketDictionary is optimized in the case of Poorly hashed keys.

Strings, Symbols and integers have rather good hash in Squeak, and in 
this case sig's BucketDictionary is slower than regular Dictionary.

Ian Piumarta a écrit :
 >
 > One classic optimisation would be to use an ArrayedCollection of some
 > kind (instead of a linked list) for the buckets.  When #findKeyOrNil:
 > hits and the association is not the first element in the bucket then
 > exchange it with the element immediately preceding it.  Associations
 > related to popular keys will gradually migrate to the front of their
 > buckets.
 >
 > Cheers,
 > Ian
 >

Ian, very bright to swap popular toward head.
But the Bucket efficiency in adding/removing comes from linked list.
How a copy of a bucket array would do better?
Maybe you mean avoiding writing something ugly like:

BucketDictionary>>findKeyOrNil: key
| index bucket prevprev prev next |
index := (key hash \\ array size) + 1.
bucket := array at: index.
prev := prevprev := nil.
next := bucket.
[next key = key ifTrue: [
	prev ifNotNil:
		[prev next: next next.
		next next: prev.
		prevprev
			ifNil [array at: index put: next]
			ifNotNil: [prevprev next: next]].
	^next].
prevprev := prev.
prev := next.
next := next next.
next isNil] whileFalse.
^nil

Argh! better start learning lisp next time...
I didn't test it. If it works, someone pay me a beer!

Nicolas