CS70 L23 Hashing (1)! Dan Garcia © UCB!2003-10-22 Dan Garcia (www.cs.berkeley.edu/~ddgarcia) inst.eecs.berkeley.edu/~cs70/ 1 Handout: notes Computer Science 70 Discrete Mathematics and Probability Theory Hashing Lecture 23CS70 L23 Hashing (2)! Dan Garcia © UCB!Big Idea: memoization • General principle: store rather than recompute. • Context is a tree-recursive algorithm with lots of repeated computation, e.g. Fibonacci: int Fib (int n) {! if (n==0 || n==1) {! return n;! } else if (we’ve computed n's value already) {! return that value;! } else {! int value = Fib(n-1) + Fib(n-2);! store (n, value);! return value;! }!}"• Pairs (n, value of Fib(n)) are stored in the table.CS70 L23 Hashing (3)! Dan Garcia © UCB!Hash Function • If what we want to memoize isn’t a simple number, how do we convert it to a number to easily store it into a table? • We need something that can help us map this data into an integer, to serve as an index into an array (used to store the table). • This mapping function is called a hash function http://en.wikipedia.org/wiki/Hash_functionCS70 L23 Hashing (4)! Dan Garcia © UCB!Writing hash functions - TTT (1) • Let's consider Tic-Tac-Toe: – One player chooses X, the other chooses O – They take turns placing their piece on the board – Assume X goes first – Once a piece is placed, it isn't moved – The player who first gets 3-in-a-row wins – If the board gets filled up and nobody wins, it's a tieCS70 L23 Hashing (5)! Dan Garcia © UCB!Writing hash functions - TTT (2) • Writing a Tic-Tac-Toe hash function: • One idea is to ignore the 2D nature of the game and make it a 1D array of slots h = 13,205 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8CS70 L23 Hashing (6)! Dan Garcia © UCB!Writing hash functions - TTT (3) • Think of each of the 9 slots as 1 of 3 values – Blank, O and X – Let's assign values 0, 1 and 2 to these • How can we create a single number from this? – Let's think about this as a ternary number: – S8•38 + S7•37 + … + S1•31 + S0•30 – 2•38 + 1•34 + 2•30 = 13, 205 • This is known as a "polynomial hash code" 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 2 0 0 0 1 0 0 0 2CS70 L23 Hashing (7)! Dan Garcia © UCB!Writing hash functions - TTT (4) • Analysis of ternary polynomial hashcode: – What's the smallest #? – What's the biggest #? – Is this as optimal (I.e., tightly-packed) as possible? – Any suggestions for making this more optimal? 0 39-1 No!CS70 L23 Hashing (8)! Dan Garcia © UCB!Writing hash functions - TTT (5) • Optimizing the Tic-Tac-Toe hash function – This involves understanding the rules of placement » The players take turns & X goes first! – Let's consider some small 1D boards (S = # of slots) » S=1: 2 boards (- | X) We'll use "|" to separate groups » S=2: 5 boards (-- | -X, X- | XO, OX) » S=3: 13 boards (--- | --X, -X-, X-- | -OX, -XO, O-X, OX-, X-O, XO- | OXX, XOX, XXO) = (1 + 3 + 6 + 3) » S=4: __ boards ( __ + __ + __ + __ + __ ) » …pattern?CS70 L23 Hashing (9)! Dan Garcia © UCB!Remember your Combinatorics! • Let's figure out numBoards(s), s = # slots • For n=5, we had: # ways to rearrange 0 Xs, 0 Os in 4 slots + # ways to rearrange 1 Xs, 0 Os in 4 slots + # ways to rearrange 1 Xs, 1 Os in 4 slots + # ways to rearrange 2 Xs, 1 Os in 4 slots + # ways to rearrange 2 Xs, 2 Os in 4 slots • Generalizing from this example (p=# pieces): • But what is rearrange(x,o,s)? – # of ways to rearrange x Xs, o Os in s slots? € numBoards(s) = rearrange( p, p,s) +p= 0s 2 ∑rearrange( p, p −1,s)p=1s 2 ∑CS70 L23 Hashing (10)! Dan Garcia © UCB!Recall Pascal's Triangle ( )=10 0 1 2 3 4 5 6 0 1 1 1 1 2 1 2 1 3 1 3 3 1 4 1 4 6 4 1 5 1 5 10 10 5 1 6 1 6 15 20 15 6 1 5 2 This table describes how to calculate combinations. I.e., "N choose K". That is, the number of ways to rearrange 2 pieces in 5 slots is "5 choose 2", which is the expression at the top. 10 ways. N K = N! K! (N-K)! N KCS70 L23 Hashing (11)! Dan Garcia © UCB!rearrange(x,o,s) = r(x,o,s) • How many ways to rearrange x Xs, o Os in s slots? • Blur method – First, blur eyes, how many ways to rearrange ALL (x+o) pieces in s slots? [stop blurring now] – For EACH, how many ways to rearrange Xs in pieces? – Answer is product of these • Overcount method – Think of permuting all the elements; how many? – How many were overcounted? Xs, Os, spaces – Answer is quotient of these 0 1 2 3 4 5 6 7 8 s x+o x+o x s! o! x! (s-x-o)! s! o! x! (s-x-o)! s x+o x+o x s! (s-x-o)!(x+o)! (x+o)! o! x! = •CS70 L23 Hashing (12)! Dan Garcia © UCB!Now we know our Hash Table size • Now we know numBoards(s) – numBoards(4) ⇒ ( 1 + 4 + 12 + 12 + 6 ) = 35 – numBoards(9) ⇒ ( 1+9+72+252+756+1260+1680+1260+630+126) = 6,046 < 19,683 = 39 • Plotting rearrange(x,o,4) 2 6 1 12 12 0 1 4 0 1 2 o x Note zig-zag pattern as a result of the alternating moves of each player! numBoards just sums 'em! s=4CS70 L23 Hashing (13)! Dan Garcia © UCB!But what about the hash function? • How do we write the combinatorially optimal hash()? – This take our board and generates a # between 0 and (numBoards - 1) • Two steps (sum the following numbers) 1. Finding out how many numbers there were in the zigzag up to our box (this is the BIAS, or OFFSET) 2. Finding out our number REARRANGEMENT within our box » Exactly same idea as the ternary polynomial hash code: • X counts as 2, i.e., 2•3i, O counts as 1, I.e., 1•3i, – = 0 » Here, we consider the leftmost slot & how much it's worth • X counts for all ways to rearrange if it were O & – • O counts for all ways to rearrange if it were – • – counts for 0 • (Shortcut when a board has all the same piece, counts for 0)CS70 L23 Hashing (14)! Dan Garcia © UCB!Example TicTacToe hash function • Let's hash XO-X = X3O2-1X0 – Must be a # between 0 and (numBoards(4)- 1) = 34 • Two steps: BIAS + REARRANGEMENT # – BIAS: X=2,O=1,S=4; Count buckets up to us:1+4+12=17 – …
View Full Document
Unlocking...