Hash-table:Basic Idea Hashing:the idea Q:What is a Collision?When does it take place? E[O] E[叫 Hash Function oy Key Space E[m-1] 酸 ，口+4心，。左，生，生 0Q0
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 10, 2022 4 / 34
Hash-table:Basic Idea Hashing:the idea Q:What is a Collision?When does it take place? E[O] E[1] E[周 Hash Function Key Space E[m-1 口卡4心，左·急安 Dao MA Jun (Institute of Computer Software) Problem Solving May10.2022 4/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 10, 2022 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[0] E E[周 ←---Hash Function Key Space E[m-1] ，口+4的，。之，生，生 0Q0
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 10, 2022 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[0] E E[周 ←---Hash Function Key Space E[m-1刂 It depends .. 口+4的，·左·生·生分Q0 MA Jun (Institute of Computer Software) Problem Solving May10.2022 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? 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 10, 2022 5 / 34
Hash-table:Basic Idea Model Assumption Model oInserting n keys:sequence of n independent trails. o Each insertion corresponds to a value from {0,1,...,m-1 4口4的在4是安QC MA Jun (Institute of Computer Software) Problem Solving May10.2022 6/34
Hash-table: Basic Idea Model & Assumption Model Inserting n keys: sequence of n 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 10, 2022 6 / 34