hash tables notes

Hash Tables

Big Theta (NOT O) tends towards 1 if we do the hashtable well

rethink how we put stuff into it; hashtables are bad at ordering or sorting data

A hash table combines two things-- hash function and an array that can store data
run our data through the hash function
store data in the element of the array represented by the returned hash code

for example: hashcode(tank) = 4
so we store tank in array(4)
and then to retrieve it we just do the hash code again and it gives us 4

how do we define a hash function?
good hash functions exist... use them
Scala has hashCode   x.hashCode

=====

What do I do if there is a collision?  when two pieces of data yield the same hashcode
We want to store both
Need a way to get both into table and still maintain quick insertion and lookup

Helps to mod by length of array

Solution: linear probing-- move to the right and whatnot
Only problem is it causes clustering

What if each array element was the head of a linked list?  This is called chaining