Andreas Raab uploaded a new version of Collections to project The Trunk:
http://source.squeak.org/trunk/Collections-ar.212.mcz

==================== Summary ====================

Name: Collections-ar.212
Author: ar
Time: 24 November 2009, 9:48:13 am
UUID: fdceaa93-63c2-fe47-bf3e-0c2ba9e1a0f8
Ancestors: Collections-ul.209, Collections-ul.211

Merging Collections-ul.210, Collections-ul.211:

- HashedCollections have prime capacity (if they are not oversized)
- HashedCollections' growth rate is not 2, but 1.5 (2 for small sizes which decreases to 1.5 as the size increases)

(based on Andrés Valloud's changes made for pharo)
Load Kernel-ul.305 before this.

- replaced 32359813 with 32435981 in HashedCollection >> #goodPrimes.

=============== Diff against Collections-ul.209 ===============

Item was changed:
  ----- Method: HashedCollection>>growSize (in category 'private') -----
  growSize
+ 	"Answer what my next higher table size should be"
+ 	
+ 	^self class goodPrimeAtLeast: array size * 3 // 2 + 2!
- 	^ array size max: 2!

Item was changed:
+ ----- Method: HashedCollection class>>sizeFor: (in category 'sizing') -----
- ----- Method: HashedCollection class>>sizeFor: (in category 'instance creation') -----
  sizeFor: nElements
+ 	"Large enough prime (or odd if too large) size to hold nElements with some slop (see fullCheck)"
+ 	
+ 	nElements < 4 ifTrue: [ ^5 ].
+ 	^self goodPrimeAtLeast: nElements + 1 * 4 // 3!
- 	"Large enough size to hold nElements with some slop (see fullCheck)"
- 	nElements <= 0 ifTrue: [^ 1].
- 	^ nElements+1*4//3!

Item was added:
+ ----- Method: HashedCollection class>>goodPrimes (in category 'sizing') -----
+ goodPrimes
+ 	"Answer a sorted array of prime numbers less than one billion that make good
+ 	hash table sizes. Should be expanded as needed.  See comments below code"
+ 	
+ 	^#(5 11 17 23 31 43 59 79 107 149 199 269 359 479 641 857 1151 1549 2069
+ 		2237 2423 2617 2797 2999 3167 3359 3539 3727 3911
+ 		4441 4787 5119 5471 5801 6143 6521 6827 7177 7517 7853
+ 		8887 9587 10243 10937 11617 12289 12967 13649 14341 15013 15727
+ 		17749 19121 20479 21859 23209 24593 25939 27329 28669 30047 31469
+ 		35507 38231 40961 43711 46439 49157 51893 54617 57347 60077 62801
+ 		70583 75619 80669 85703 90749 95783 100823 105871 110909 115963 120997 126031
+ 		141157 151237 161323 171401 181499 191579 201653 211741 221813 231893 241979 252079
+ 		282311 302483 322649 342803 362969 383143 403301 423457 443629 463787 483953 504121
+ 		564617 604949 645313 685609 725939 766273 806609 846931 887261 927587 967919 1008239
+ 		1123477 1198397 1273289 1348177 1423067 1497983 1572869 1647761 1722667 1797581 1872461 1947359 2022253
+ 		2246953 2396759 2546543 2696363 2846161 2995973 3145739 3295541 3445357 3595117 3744941 3894707 4044503
+ 		4493921 4793501 5093089 5392679 5692279 5991883 6291469 6591059 6890641 7190243 7489829 7789447 8089033
+ 		8987807 9586981 10186177 10785371 11384539 11983729 12582917 13182109 13781291 14380469 14979667 15578861 16178053
+ 		17895707 19014187 20132683 21251141 22369661 23488103 24606583 25725083 26843549 27962027 29080529 30198989 31317469 32435981
+ 		35791397 38028379 40265327 42502283 44739259 46976221 49213237 51450131 53687099 55924061 58161041 60397993 62634959 64871921
+ 		71582857 76056727 80530643 85004567 89478503 93952427 98426347 102900263 107374217 111848111 116322053 120795971 125269877 129743807
+ 		143165587 152113427 161061283 170009141 178956983 187904819 196852693 205800547 214748383 223696237 232644089 241591943 250539763 259487603
+ 		285212677 301989917 318767107 335544323 352321547 369098771 385876021 402653189 419430419 436207619 452984849 469762049 486539323 503316511 520093703
+ 		570425377 603979799 637534277 671088667 704643083 738197549 771751961 805306457 838860817 872415239 905969671 939524129 973078537 1006632983 1040187403
+ 		1073741789)
+ 
+ "The above primes past 2069 were chosen carefully so that they do not interact badly with 1664525 (used by hashMultiply), and so that gcd(p, (256^k) +/- a) = 1, for 0<a<=32 and 0<k<=8.  See Knuth's TAOCP for details."!

Item was changed:
  ----- Method: HashedCollection>>grow (in category 'private') -----
  grow
  	"Grow the elements array and reinsert the old elements"
  	
+ 	self growTo: self growSize!
- 	self growTo: array size + self growSize!

Item was added:
+ ----- Method: HashedCollection class>>goodPrimeAtLeast: (in category 'sizing') -----
+ goodPrimeAtLeast: lowerLimit
+ 	"Answer the next good prime >= lowerlimit.
+ 	If lowerLimit is larger than the largest known good prime,
+ 	just make it odd."
+ 	
+ 	| primes low mid high prime |
+ 	primes := self goodPrimes.
+ 	low := 1.
+ 	high := primes size.
+ 	lowerLimit > (primes at: high) ifTrue: [
+ 		^lowerLimit even 
+ 			ifTrue: [ lowerLimit + 1 ]
+ 			ifFalse: [ lowerLimit ] ].
+ 	[ high - low <= 1 ] whileFalse: [
+ 		mid := high + low // 2.
+ 		prime := primes at: mid.
+ 		prime = lowerLimit ifTrue: [ ^prime ].
+ 		prime < lowerLimit
+ 			ifTrue: [ low := mid ]
+ 			ifFalse: [ high := mid ] ].
+ 	(primes at: low) >= lowerLimit ifTrue: [ ^primes at: low ].
+ 	^primes at: high!