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-品” Q:What is the expected number of empty locations? 美 4口40，注+至是刀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 Idea Empty location After inserting n items into m locations Q:What is the probability of a given location is empty? (1-a” Q:What is the expected number of empty locations? 美 4口40，注42，是刀QC 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 Idea Empty location After inserting n items into m locations Q:What is the probability of a given location is empty? (1-a)” Q:What is the expected number of empty locations? 1 location i is empty 0,otherwise 。X=∑X 1≤i≤m 美 4口40，注+至是刀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-a)” Q:What is the expected number of empty locations? 。Xi= 1,location i is empty 10 otherwise X=∑X 1≤i≤m ·E(X)=E(∑X)=∑E(X)=∑(1-1/m)”= 1≤i≤m 1≤i≤m 1≤i≤m m(1-1/m)n 美 口4y，4艺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 Idea After inserting n items into a hashtable with n locations 發 4口4的，，左+生，2分Q0 MA Jun (Institute of Computer Software) Problem Solving May10.2022 8/34
Hash-table: Basic Idea After inserting n items into a hashtable with n locations Q : What is the expected number of items in a given location? Yi = ( 1 ,the ith item in the given location 0 , otherwise Y = P 1≤i≤n Yi E(Y ) = E( P 1≤i≤n Yi) = P 1≤i≤n E(Yi) = P 1≤i≤n 1/n = 1 Expected number of empty locations: n(1 − 1/n) n = n/e ≈ 0.368n PARADOX? collisions! MA Jun (Institute of Computer Software) Problem Solving May 10, 2022 8 / 34