I never said it was easy.
Another way to do it is to compact eagerly on removal (as it's done in
Pharo). This gives better mass removal performance, and some of the code
becomes significantly simpler. This results in further performance boost.

Removal still takes O(n) time, which means mass removal is in O(n^2), but 
with a significantly smaller constant (~1/10), which improves the
usability of the collection quite a bit:

| n random array |
n := 10000.
random := Random seed: 36rSQUEAK.
array := Array new: n streamContents: [ :stream |
         n timesRepeat: [ stream nextPut: (random nextInt: 1073741823) -> 1 
] ].
{ OrderedDictionary. LinkedDictionary } collect: [ :class |
     Smalltalk garbageCollect.
     [
         | instance |
         instance := class new.
         instance addAll: array.
         array do: [ :each | instance removeKey: each key ] ] timeToRun ].
"==> #(78 10)"

(If n is 100k, then the result is still pretty bad: #(7055 136).)

You can find these changes in the Inbox.

Levente

On Mon, 19 Jan 2015, Marcel Taeumel wrote:

> Woah, managing such a lookup index between "array" and "order" is quite
> complicated with the current implementation of Dictionary. :D
>
> Best,
> Marcel
>
>
>
> --
> View this message in context: http://forum.world.st/The-Trunk-Collections-mt-599-mcz-tp4800299p4800317.html
> Sent from the Squeak - Dev mailing list archive at Nabble.com.
>
>