Hashmap and Hashset

Class Hasher<T>
	Method hashCode:int(i:T)
		Return 0
	End
	Method equals:Bool(i:T, i2:T)
		Return False
	End
End

Class IntHasher Extends Hasher<int>
	Method hashCode:int(i:int)
		Return i
	End
	Method equals:Bool(i:int, i2:int)
		Return i = i2
	End
End

Class StringHasher Extends Hasher<String>
	Method hashCode:int(i:String)
		Local hash:Int = 1
		Local prime:Int = 31
		For Local j:Int = 0 To i.Length() -1
			hash = prime * hash + i[j]
		Next
		Return hash
	End
	Method equals:Bool(i:String, i2:String)
		Return i.Compare(i2) = 0
	End
End


'	A hashtable element represents an entry in the hash map/table.
'	Works like a singly linked list to deal with hash collisions.
Class HTElem<K, V>
	Field key:K
	Field value:V
	Field nxt:HTElem<K, V>
	Method New(k:K, v:V, n:HTElem<K, V>)
		key = k
		value = v
		nxt = n
	End
End

'	A hash map class that uses chained bucketing to deal with hash collisions.
' 	K and V represent the classes of the key and value items in the hash map.
'	To use this class one will have to provide a 'Hasher' object defined above.
Class HashMap<K, V>
	Private
	Field table:HTElem<K, V>[]		'	The array that backs the hash table
	Field numElems:Int = 0			'	Number of elements in the hash table
	Const MAX_LOAD:Float = 1.75	'	When the hashtable exceedes this density it will resize itself
	Const GROWTH_FACTOR:= 3			'	The multiple to with the table resizes
	Const DEFAULT_HT_SIZE:= 11		'	The default hash table size
	Const SHRINK_FACTOR:= 0.5
	Const MIN_LOAD:= 0.3
	Field hasher:Hasher<K>			'	The hasher object that provides equals and hashCode methods
	
	'	Resizes the hash map while keeping all its entries.
	Method resize:Void(size:int)
		Local tmp:HTElem<K, V>[] = table
		table = New HTElem<K, V>[size]
		For Local i:int = 0 Until tmp.Length
			Local curr:= tmp[i]
			While (curr <> Null)
				Self.add(curr.key, curr.value)
				curr = curr.nxt
			Wend
		Next
	End
	
	'	Gets the location for a key in the current table
	Method getLoc:Int(key:K)
		Return Abs(hasher.hashCode(key) Mod table.Length)
	End
	
	Public
	
	'	------Constructors-------
	' Create a new hashmap with a specific size
	Method New(h:Hasher<K>, size:Int)
		table = New HTElem<K, V>[size]
		hasher = h
	End
	'	Create a default hashmap
	Method New(h:Hasher<K>)
		table = New HTElem<K, V>[DEFAULT_HT_SIZE]
		hasher = h
	End
	
	'	Check if the hashmap contains a specific element
	Method contains:Bool(key:K)
		Local location:Int = Self.getLoc(key)
		Local curr:HTElem<K, V> = table[location]
		While (curr <> Null)
			If (hasher.equals(curr.key, key))
				Return True
			EndIf
			curr = curr.nxt
		Wend
		Return False
	End
	
	Method get:V(key:K)
		Local location:Int = Self.getLoc(key)
		Local curr:HTElem<K, V> = table[location]
		While (curr <> Null)
			If (hasher.equals(curr.key, key))
				Return curr.value
			EndIf
			curr = curr.nxt
		Wend
		Throw New Throwable
	End
	
	'	Add a new key/value pair
	Method add:Void(key:K, value:V)
		Local location:Int = Self.getLoc(key)
		Local tst:= table[location]
		table[location] = New HTElem<K, V>(key, value, table[location])
		Self.numElems += 1
		If (Self.numElems / Float(table.Length) >= MAX_LOAD)
			Self.resize(table.Length * GROWTH_FACTOR)
		EndIf
		tst = table[location]
	End
	
	'	Remove all instances of a key
	Method remove:Void(key:K)
		Local location:Int = Self.getLoc(key)
		Local curr:HTElem<K, V> = table[location]
		Local prev:HTElem<K, V> = Null
		While (curr <> Null)
			If (hasher.equals(curr.key, key))
				If (prev <> Null)
					prev.nxt = curr.nxt
				Else
					table[location] = table[location].nxt
				EndIf
			EndIf
			prev = curr
			curr = curr.nxt
		Wend
	End
	
End


'	A set that is backed by a hashmap
Class HashSet<T> Extends HashMap<T, Object>
	Method New(h:Hasher<K>, size:Int)
		Super.New(h, size)
	End
	Method New(h:Hasher<K>)
		Super.New(h)
	End
	Method add:Void(key:T, value:Object = Null)
		Super.add(key, Null)
	End
	
	Method remove:bool(key:T)
		Return Super.remove(key)
	End
	
	Method contains:bool(key:T)
		Return Super.contains(key)
	End
End

Local h:HashSet<String> = New HashSet<String>(New StringHasher())
h.add("hello hashset!")