Hash-table:Basic Idea Model Assumption Model o Inserting n keys:sequence of n independent trails. o Each insertion corresponds to a value from {0,1,...,m-1} Assumption o For each insertion,the result is Uniformly Distributed,i.e.each value from (0,1,...,m-1}is equally picked. 發 口卡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
Hash-table:Basic Idea Model Assumption Model o Inserting n keys:sequence of n independent trails. o Each insertion corresponds to a value from (0,1,...,m-1. Assumption o 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 a =n/m (a:loading factor) 發 +口+4的，。左，4生，2QC MA Jun (Institute of Computer Software) Problem Solving My10.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
Hash-table:Basic ldea Empty location After inserting n items into m locations 口+4y，。法，生，生Q0 MA Jun (Institute of Computer Software) Problem Solving May10.2022 7/34
Hash-table: Basic Idea Empty location After inserting n items into m locations Q : What is the probability of a given location is empty? (1 − 1 m ) n Q : What is the expected number of empty locations? Xi = ( 1 , location i is empty 0 , otherwise X = P 1≤i≤m Xi E(X) = E( P 1≤i≤m Xi) = P 1≤i≤m E(Xi) = P 1≤i≤m (1 − 1/m) n = m(1 − 1/m) n MA Jun (Institute of Computer Software) Problem Solving May 10, 2022 7 / 34
Hash-table:Basic ldea Empty location After inserting n items into m locations Q:What is the probability of a given location is empty? 口卡4心，老生Q0 MA Jun (Institute of Computer Software) Problem Solving May10.2022 7/34
Hash-table: Basic Idea Empty location After inserting n items into m locations Q : What is the probability of a given location is empty? (1 − 1 m ) n Q : What is the expected number of empty locations? Xi = ( 1 , location i is empty 0 , otherwise X = P 1≤i≤m Xi E(X) = E( P 1≤i≤m Xi) = P 1≤i≤m E(Xi) = P 1≤i≤m (1 − 1/m) n = m(1 − 1/m) n MA Jun (Institute of Computer Software) Problem Solving May 10, 2022 7 / 34
Hash-table:Basic ldea Empty location After inserting n items into m locations Q:What is the probability of a given location is empty? (1-品)” 口卡4心，老生Q0 MA Jun (Institute of Computer Software) Problem Solving May10.2022 7/34
Hash-table: Basic Idea Empty location After inserting n items into m locations Q : What is the probability of a given location is empty? (1 − 1 m ) n Q : What is the expected number of empty locations? Xi = ( 1 , location i is empty 0 , otherwise X = P 1≤i≤m Xi E(X) = E( P 1≤i≤m Xi) = P 1≤i≤m E(Xi) = P 1≤i≤m (1 − 1/m) n = m(1 − 1/m) n MA Jun (Institute of Computer Software) Problem Solving May 10, 2022 7 / 34