CSE 331 Lecture Notes - Lecture 4: Avl Tree, Prime Number
Hash Tables
• Give a key, we can put it in the hash table by taking the integer value given, we can mod
it with the table size
• A hash function is a way to translate the key to a value of index of the array.
• Ex:
o put(0, “foo”) where table is only of size 10: 0 % 10 = 0, so “foo” in index 0.
o put(5, “bar”) where table is only of size 10, 5%10= 5, so “bar” in index 5.
o put(11, “biz”) where table is only of size 10, 11%10=1 so “biz” in index 1.
o However, if we do put(20, “bop”), we would overwrite index 0. This leads to a
collision
• Collisions: when multiple keys translate to the same location of the array. The fewer the
collisions, the better the runtime
o More collisions means we move further away from O(1)
• To avoid this, we can have each space hold a bucket that can store multiple values.
Bucket is often implemented with a LinkedList
• The load factor, lambda, is the number of total key-value pairs divided by capacity of
array (number of elements divided by number of buckets)
• Try to make it so that not everything is in the same bucket
• Worst case scenario is when everything is in the same bucket, so we just have a
LinkedList in the end.
• If we put in a duplicate key, then the value will be replaced with the new value (putting in
(5,”bar”) and then (5,”foo”))
• To optimize the bucket, we can use an AVL tree instead of a LinkedList.
o Java starts off as a LinkedList, then as load factor gets too big, it converts
everything to AVL
• If our buckets get too big, we can make a few table with larger size and then rehash
everything.
o Done when lambda is approximately 1.
o Increase array size to next prime number that is roughly double the array size
since prime numbers reduce collisions
• Hash function: an algorithm that maps a given key to an integer representing the index in
the array for where to store the associated value
o Every java objected has an automatically implemented hash function method for
a value.
