Class Dictionary IndexedCollection hashTable
Methods Dictionary
	new
		hashTable <- Array new: 39

]
Methods Dictionary

	removeKey: aKey ifAbsent: exceptionBlock
		^ (self includesKey: aKey)
			ifTrue: [ self basicRemoveKey: aKey ]
			ifFalse: exceptionBlock

]
Methods Dictionary

	hash: aKey
		^ 3 * ((aKey hash) rem: ((hashTable size) quo: 3))

]
Methods Dictionary

	includesKey: aKey
		" look up, but throw away result "
		self at: aKey ifAbsent: [ ^ false ].
		^ true

]
Methods Dictionary

	basicRemoveKey: aKey		| hashPosition link |
		hashPosition <- self hash: aKey.
		((hashTable at: hashPosition + 1) = aKey)
			ifTrue: [ hashTable at: hashPosition + 1 put: nil.
				  hashTable at: hashPosition + 2 put: nil]
			ifFalse: [ link <- hashTable at: hashPosition + 3.
				(link notNil)
					ifTrue: [ hashTable at: hashPosition + 3
							put: (link removeKey: aKey) ]]

]
Methods Dictionary

	binaryDo: aBlock
		(1 to: hashTable size by: 3) do:
			[:i | (hashTable at: i) notNil
				ifTrue: [ aBlock value: (hashTable at: i)
						value: (hashTable at: i+1) ].
			      (hashTable at: i+2) notNil
				ifTrue: [ (hashTable at: i+2) 
						binaryDo: aBlock ] ]

]
Methods Dictionary

	removeKey: aKey
		^ self removeKey: aKey
			ifAbsent: [ smalltalk error: 'remove key not found']

]
Methods Dictionary

	at: aKey ifAbsent: exceptionBlock	| hashPosition  link |

		hashPosition <- self hash: aKey.
		((hashTable at: hashPosition + 1) = aKey)
			ifTrue: [ ^ hashTable at: hashPosition + 2].
		link <- hashTable at: hashPosition + 3.
		^ (link notNil)
			ifTrue: [ link at: aKey ifAbsent: exceptionBlock ]
			ifFalse: exceptionBlock

]
Methods Dictionary

	at: aKey put: aValue			| hashPosition link |

		hashPosition <- self hash: aKey.
		((hashTable at: hashPosition + 1) isNil)
		   ifTrue: [ hashTable at: hashPosition + 1 put: aKey ].
		((hashTable at: hashPosition + 1) = aKey)
		   ifTrue: [ hashTable at: hashPosition + 2 put: aValue ]
		   ifFalse: [ link <- hashTable at: hashPosition + 3.
			(link notNil)
				ifTrue: [ link at: aKey put: aValue ]
				ifFalse: [ hashTable at: hashPosition + 3
					put: (Link new; key: aKey; value: aValue)]]

]
Methods Dictionary

	display
		self binaryDo: [:x :y | (x printString , ' -> ', 
					y printString ) print ]

]