Hash-table:Basic Idea Hashing:the idea Q:What is a Collision?When does it take place? E[O] E[] Hash Function Key Space 。++ E[m-1] 口卡4心，，之·生空 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Hashing: the idea Q : What is a Collision? When does it take place? Hash Function Key Space · · · · · · E [0] E [1] E [m − 1] x y E [k] MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 4 / 34
Hash-table:Basic Idea Hashing:the idea Q:What is a Collision?When does it take place? E[O] E[] E[k个 Hash Function. Key Space E[m-1刂 口卡+①，2是生Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20204/34
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Hashing: the idea Q : What is a Collision? When does it take place? Hash Function Key Space · · · · · · E [0] E [1] E [m − 1] x y E [k] MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 4 / 34
Hash-table:Basic Idea Collision Q:Given n keys and m slots,what is the expected number of keys hashed into the same slot? E[O] E[1] E[k个 ----H3 sh Functio0。 -0y Key Space E[m-1] @ 4口45，，左·生空 0a0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Collision Q : Given n keys and m slots, what is the expected number of keys hashed into the same slot? Hash Function Key Space x y · · · · · · E [0] E [1] E [m − 1] E [k] It depends ... MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 5 / 34
Hash-table:Basic Idea Collision Q:Given n keys and m slots,what is the expected number of keys hashed into the same slot? E[O] E[1] E[k个 ←---Hash Functio0. Key Space E[m-1刂 It depends... 口卡4①1左·生，生Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20205/34
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Collision Q : Given n keys and m slots, what is the expected number of keys hashed into the same slot? Hash Function Key Space x y · · · · · · E [0] E [1] E [m − 1] E [k] It depends ... MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 5 / 34
Hash-table:Basic Idea Model Assumption Model oInserting n keys:sequence of n s independent trails. Each insertion corresponds to a value from {0,1,...,m-1) 口卡+①，2是生Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20206/34
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Hash-table: Basic Idea Model & Assumption Model Inserting n keys: sequence of n s independent trails. Each insertion corresponds to a value from {0, 1, · · · , m − 1}. Assumption For each insertion, the result is Uniformly Distributed, i.e. each value from {0, 1, · · · , m − 1} is equally picked. In hashing n items into a hash table of size m, the expected number of items that hash to any one location is α = n/m (α: loading factor) MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 6 / 34