Hash Table - Question 4 Answer

4

\begin{algorithm}
\caption{Hash Table}
\begin{algorithmic}
\REQUIRE size = size of the array to store data in
\REQUIRE hashFunc = hash function capable of simple uniform hashing
\OUTPUT hash table data structure
\FUNCTION{create}{size, hashFunc}
\STATE ht $\gets$ new memory allocation
\STATE ht.size$\gets$ size
\STATE ht.data $\gets$ array of size
\STATE ht.hashFunc $\gets$ hashFunc
\RETURN{ht}
\ENDFUNCTION
\STATE
\REQUIRE ht = hash table data structure
\REQUIRE key = key to generate an index for
\OUTPUT index with ht.size bounds
\FUNCTION{getIndex}{ht, key}
\STATE h $\gets$ \CALL{ht.hashFunc}{key}
\STATE A $\gets \frac{\sqrt{5}-1}{2}$
\STATE index $\gets \left \lfloor \text{ht.size}(h A \bmod 1) \right \rfloor$
\RETURN{index}
\ENDFUNCTION
\STATE
\REQUIRE ht = hash table data structure
\REQUIRE key = key to use for future lookups
\REQUIRE value = value to add to the queue
\FUNCTION{put}{ht, key, value}
\STATE index $\gets$ \CALL{getIndex}{ht, key}
\STATE
\STATE bucket $\gets$ HT.data[index]
\IF{bucket = NULL}
\STATE ht.data[index] $\gets$ \CALL{LinkedListCreate}{}
\STATE bucket $\gets$ HT.data[index]
\ENDIF
\STATE
\STATE keyValuePair $\gets$ \CALL{LinkedListSearch}{bucket, key}
\IF{keyValuePair = NULL}
\STATE keyValuePair $\gets$ \CALL{KeyValuePair}{key, value}
\ELSE
\STATE keyValuePair.value $\gets$ value
\ENDIF
\ENDFUNCTION
\STATE
\REQUIRE ht = hash table data structure
\REQUIRE key = key to search for
\OUTPUT value assoicated with key
\FUNCTION{get}{ht, key}
\STATE index $\gets$ \CALL{getIndex}{ht, key}
\STATE
\STATE bucket $\gets$ HT.data[index]
\IF{bucket = NULL}
\ELSE
\ENDIF
\ENDFUNCTION
\STATE
\REQUIRE ht = hash table data structure
\REQUIRE key = key to remove
\FUNCTION{remove}{ht, key}
\STATE index $\gets$ \CALL{getIndex}{ht, key}
\STATE
\STATE bucket $\gets$ HT.data[index]
\IF{bucket = NULL}