use the sum of the characters in a string as its hash
use 1 for "a", 2 for "b", etc
so the string "edo" hashes to 5 + 4 + 15 = 24
the string "hello" hashes to 8 + 5 + 12 + 12 + 15 = 52
the string "world" hashes to 23 + 15 + 18 + 12 + 4 = 72
if the hash table has size 11, this gives a perfect hash
function for these three strings:
24 modulo 11 = 2, so "edo" is stored at index 2
52 modulo 11 = 8, so "hello" is stored at index 8
72 modulo 11 = 6, so "world" is stored at index 6
in each case, computing the index takes time independent of
both the table size and the number of elements in the table:
O(1) or, to be accurate, O(key size)
supposing I wanted to use the same hash function on a table
of size 3,
24 modulo 3 = 0, so "edo" is stored at index 0
52 modulo 3 = 1, so "hello" is stored at index 1
72 modulo 3 = 0, so "world" is stored at index 0
the first and last string need to be stored in the same location,
which is a collision
hash table collisions
an array location can only hold one item, so what to do in case
of a collision?
a number of solutions:
can store colliding elements (and only those elements) in a
separate data structure (e.g. a linked list), which is searched when needed
can increase (e.g. double plus one) the size of the array until
the collision goes away
can look for another place in the same array that is available.
This is called open address hashing
can have each array element refer to a linked list rather than a
single element: chained hashing
or combinations of the above
in-class exercise: assuming few collisions, what is the average runtime
of each of the above strategies?
in-class exercise: assuming many collisions, what is the worst-case
runtime of each of the above strategies?
Hash functions
finding a perfect hash function is not practical unless all keys
are known in advance
for random, evenly distributed keys, any hash function should
produce random, evenly distributed hash codes, with a few collisions
for non-random keys that resemble one another, a good hash
function should still produce random, evenly distributed hash codes
so for example, using the first three digits of a telephone number
(the area code) as a hash key would give many collisions if all the
keys are from the same geographic area
in-class exercise: using h(key) = key mod table size, insert
elements with key 99, 43, 14, 77 into a table of size 10
for a much more in-depth explanation of hash functions,
see here,
which includes
this link
to a more effective (and more complex) hash functions.
Open addressing
when inserting a value in a hash table, if the slot indicated
by the hash function is full, insert it into another slot
this works until the hash table is full (100% load factor), i.e.
it works as long as there are open slots
the probe sequence determines where to look next when there
is a collision
when looking up a value in a hash table, the same probe sequence
must be followed as when inserting
when removing a value from a hash table,
the hash table must record that the element was removed, so future
searches can keep looking when they reach the slot of a deleted element
each slot must record whether it is empty, full, or deleted
a slot can only be empty until the first time a value is inserted,
after which it can only be full or deleted
probing in open addressing
linear probing:
increment the index (modulo the array size) until a free slot is
found
if many keys hash to similar values, may lead to long search times
quadratic probing:
add the square of the probe number (modulo the array size) to get the
next index
avoids the problem with similar key hashes
for example,
hash 200 would probe locations 200, 201, 204, 209, etc
hash 201 would probe locations 201, 202, 205, 210, etc, with overlap
at only one index (201)
works well unless the hashes are identical
double hashing
define two hash functions h1 and h2
h1(key) determines the initial slot to look into
h2(key) determines the step size for the next probe
h2(key) != 0
even if h1(key1) == h1(key2),
hopefully h2(key1) != h2(key2)
for example, h1(key) could be the sum of the letters
in the string, and h2(key) could be the product of the letters
in the string plus 1
even if two strings sum to the same number, the product would almost
certainly be different, as long as the two keys are different
open addressing table size
load factor cannot exceed 100%, so the table must have at least as
many slots as the number of stored elements
if the table size is a prime number, linear hashing or double hashing
will visit the entire table before giving up
otherwise, for example double hashing in a table of size
100, with step size 10, can only visit 1/10th of the slots
if the table size is ever changed, each element must be reinserted
using the hash function and the new table size, since just copying
the old array would map an element to the wrong index:
24 modulo 11 = 2, but 24 modulo 23 = 1 -- no simple relationship
without recomputing the hash value
in-class exercises
what is the probing sequence if the hash table size is 11,
and h(key) = 4? answer for each of linear addressing,
quadratic addressing, and double hashing where h2(key) = 5
using h(key) = key mod table size, insert
elements with key 56, 48, 40, 13 into a table of size 7
remove the element with key 48
locate the element with key 13
Alternatives to open addressing
chaining or chained hashing: each array element refers to a
linked list of elements
buckets: each array element can store up to a fixed number of elements
either can accomodate load factors greater than 100%
chaining is more flexible, but requires dynamic memory allocation
in-class exercise: repeat the previous exercise using chained hashing
Java equality details
four kinds of equality:
== is true if and only if
two references are to the exact same object (or for basic types)
object1.equals(object2) is true if
object1's equals method (in its wisdom) decides
they are the same
object1.compareTo(object2) is 0 if the
compareTo method decides they are the same
transitive: if (((compare(a, b) > 0) && ((compare(b, c) > 0)),
then ((compare(a, c) > 0)
consistent: if (compare(a, b) == 0), then sgn(compare(a, c)) should
be the same as sgn(compare(b, c))
when building ordered linked lists, heaps, or when sorting, can
use either interface, e.g. class
Collections has two different methods for sorting,
static <T extends Comparable<? super T>> void sort(List<T> list)
static <T> void sort(List<T> list, Comparator<? super T> c)
applications of sorting
finding duplicate elements in a list
making a list of elements, where each element must occur at most once
preparing for future binary search (dictionary, phone book)
presenting data in an appropriate format, e.g. for printing (bank
statement sorted by date)
comparing two lists to find out which elements are in one,
the other, or both
merging multiple sorted collections into a new sorted collection,
with or without duplicates
in-class exercise
sort by first name
what algorithm did you use?
Java sorting
Java has
public static void sort(x[] items);
public static void sort(x[] items, int fromIntex, int toIndex);
for type x being any one of:
int
Object -- the objects must be Comparable
Comparator, in which case the last argument is
the comparator object
as mentioned above,
there is also a sort method declared on lists of objects that
are either Comparable, or can be compared by a
Comparator.compare() method
Selection Sort
start with an unsorted array a
the empty sub-array (elements 0 to -1) is sorted
to extend this sub-array, search in 0..a.length-1 for the
smallest element at index i (i is at least 0 and at most a.length - 1)
swap the elements at index i and at index 0
now, the sub-array with elements 0..0 is sorted
to extend this sub-array, search in 1..a.length-1 for the
smallest element at index i
swap the elements at index i and at index 1
now, the sub-array with elements 0..1 is sorted
in-class exercise (in groups of 2 or 3): write code to implement
selection sort
in-class exercise: how long does selection sort take?
Bubble Sort
start with an unsorted array a
loop through all the elements of array a, swapping any that
are not sorted
repeat until the array is sorted
in-class exercise: how long might this take? how long does it take
in the best case? how do these compare to selection sort?
historical trivia: if the data is stored on a magnetic tape, how many
passes of the tape are needed to sort the entire tape? (this is assuming
the tape can store much more data than the memory of the computer)
current trivia: bubble sort can be done in parallel on n processors...
Insertion Sort
in selection sort, find the smallest element, and put it in the next
position
in insertion sort, take the next element, and put it in the right
place
trivia: card players typically use insertion sort to arrange their decks
the sub-array at the beginning of the array is already sorted,
just as in selection sort
the next element e is always taken from the next index in the array
elements greater than e (in the sorted part of the array) are
shifted up one position, to free the position where element e
will be stored
in-class exercise (in groups of 2 or 3): write code to implement
insertion sort
in-class exercise: how long does insertion sort take?