public static void flood(WaterColor color,
LinkedList<Coord> flooded_list,
Tile[][] tiles,
Integer board_size) {
int i;
for (i = 0; i < flooded_list.size(); ++i) { // n iterations * O(n) = O(n^2)
List<Coord> neighbors = flooded_list.get(i).neighbors(tiles.length); // O(n) + O(1)=O(n)
for (Coord neighbor : neighbors) { // 4 iterations * O(n) = O(n)
if (tiles[neighbor.getY()][neighbor.getX()].getColor().equals(color)
&& !flooded_list.contains(neighbor)) { // O(1) + O(n) = O(n)
flooded_list.add(neighbor); // O(1)
}
}
}
}
time: O(n^2)
space: O(n)
public static void flood(WaterColor color,
LinkedList<Coord> flooded_list,
Tile[][] tiles,
Integer board_size) {
HashSet<Coord> is_flooded = new HashSet<>(flooded_list); // O(n)
ArrayList<Coord> flooded_array = new ArrayList<>(flooded_list); // O(n)
for (int i = 0; i != flooded_array.size(); ++i) { // n iterations * O(1) = O(n)
Coord c = flooded_array.get(i); // O(1)
for (Coord n : c.neighbors(board_size)) { // O(1) iterations * O(1) = O(1)
if (!is_flooded.contains(n)
&& tiles[n.getY()][n.getX()].getColor() == color) { // O(1)
flooded_array.add(n); // O(1)*
flooded_list.add(n); // O(1)
is_flooded.add(n); // O(1)
}
}
}
}
time: O(n)
space: O(n)
public static void flood(WaterColor color,
LinkedList<Coord> flooded_list,
Tile[][] tiles,
Integer board_size) {
for (int i = 0; i < flooded_list.size(); i++) {
checkNeighbor(flooded_list.get(i), // get is O(n), solution: use an arraylist
board_size, flooded_list, color, tiles);
}
}
public static void checkNeighbor(Coord currentTile,
Integer board_size,
LinkedList<Coord> flooded_list,
WaterColor color,
Tile[][] tiles){
List<Coord> neighborsList = currentTile.neighbors(board_size);
for (int i = 0; i < neighborsList.size(); i++) {
Coord neighbor = neighborsList.get(i);
if(!flooded_list.contains(neighbor)) { // contains is O(n)! solution: use a hashset
int x = neighbor.getX();
int y = neighbor.getY();
if(tiles[y][x].getColor() == color){
flooded_list.add(neighborsList.get(i));
checkNeighbor(neighborsList.get(i), board_size, flooded_list, color, tiles);
}
}
}
}
time: O(n) (after fixing the data structures wrt. get and contains)
space: O(n) + O(n) (call stack) = O(n)
public static void flood(WaterColor color,
LinkedList<Coord> flooded_list,
Tile[][] tiles,
Integer board_size) {
HashSet<Coord> is_flooded = new HashSet<>(flooded_list);
boolean[][] visited = new boolean[board_size][board_size];
ArrayList<Coord> queue = new ArrayList<>(flooded_list);
for (Coord c : queue) {
visited[c.getY()][c.getX()] = true;
}
while (queue.size() > 0) {
Coord c = queue.remove(0);
for (Coord n : c.neighbors(board_size)) {
if (!visited[n.getY()][n.getX()] && tiles[n.getY()][n.getX()].getColor() == color) {
if (is_flooded.add(n)) {
queue.add(n);
flooded_list.add(n);
}
}
visited[n.getY()][n.getX()] = true;
}
}
}
time: O(n)
space: O(n)
Java’s HashMap and HashSet classes are implemented with hash tables
Most programming languages have hash tables built-in or in the standard library.
The Map Abstract Data Type (aka. “dictionary”)
interface Map<K,V> {
V get(K key);
V put(K key, V value);
V remove(K key);
boolean containsKey(K key);
}
Map<K, Boolean> ~~ Set<K>
Compared to Binary Search Trees, the Map ADT does not provide an ordering of the elements.
Motivation: maps are everywhere!
We could implement the Map ADT with AVL Trees, then get() is O(log(n)).
Map implementationIf keys are integers, we can use an array.
Store items in array indexed by key (draw picture) use None to indicate absense of key.
What’s good?
get() is O(1)
What’s bad?
Prehashing fixes problem 1 by mapping everything to integers. (Textbook calls this the creation of a hash code.)
In Java, o.hashCode() computes the prehash of object o.
Ideally: x.hashCode() == y.hashCode() iff x and y are the same
object (but sometimes different objects have the same hash code)
User-definable: a class can override the hashCode method, and should
do so if you are overriding the equals method.
Algorithm for prehashing a string (aka. polynomial hash code) Map each character to one digit in a number. But there are 256 different characters, not 10. So we use a different base.
prehash_string('ab') == 97 * 256 + 98
prehash_string('abc') == 97 * (256^2) + 98 * (256^1) + 99
Hashing fixes problem 2 (reduce memory consumption).
The word “hash” is from cooking: “a finely chopped mixture”.
Towards proving that the average case time is O(1).
Simple Uniform Hashing assumption (mostly true but not completely true)
each key is equally likely to be hashed to each slot of the table independent of where other keys land. (uniformity and idependence)
what’s the expected length of a chain? (load factor)
n keys in m slots: n/m = λ
Search:
total for search: O(1 + λ) but λ <= 2, so total is O(1)
Takeaway: need to grow table size m as n increases so that λ stays small.
need to be careful about choice of table size m
if not, may not use all of the table
table size 4 (slots 0..3)
suppose the keys are all even: 0,2,..
0 -> 0 (0 mod 4 = 0)
2 -> 2 (2 mod 4 = 2)
4 -> 0 (4 mod 4 = 0)
6 -> 2 (6 mod 4 = 2)
8 -> 0 (8 mod 4 = 0)
...
Never used slot 1 and 3.
Good to choose a prime number for m, not close to a power of 2 or 10.
h(k) = ((a * k + b) mod p) mod m
where
Using the division method and chaining, insert the keys 4, 1, 3, 2, 0 into a hash table with table size 3 (m=3).
When the load factor gets too high, we need to grow the table.
Allocate a new table that is double the size.
Insert all of the entries from the old table into the new table,
using the new table size (the m) in the hash function.
Rehashing is an O(n) operation, but by doubling the same of the table, it doesn’t need to happen very often.