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-品)P Q:What is the expected number of empty locations? 自 4口卡40，注42，是QC MA Jun (Institute of Computer Software) Problem Solving May14,20207/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 = ∑ 1≤i≤m Xi E(X) = E( ∑ 1≤i≤m Xi) = ∑ 1≤i≤m E(Xi) = ∑ 1≤i≤m (1 − 1/m) n = m(1 − 1/m) n MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 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-品)P Q:What is the expected number of empty locations? 1 location i is empty 美 口卡+①，22变Q0 MA Jun (Institute of Computer Software) Problem Solving May14,20207/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 = ∑ 1≤i≤m Xi E(X) = E( ∑ 1≤i≤m Xi) = ∑ 1≤i≤m E(Xi) = ∑ 1≤i≤m (1 − 1/m) n = m(1 − 1/m) n MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 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-品)P Q:What is the expected number of empty locations? 。X= 1 location i is empty 0,otherwise 。X=∑X 1≤ism 美 4口卡40，注至，是Q0 MA Jun (Institute of Computer Software) Problem Solving May14,20207/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 = ∑ 1≤i≤m Xi E(X) = E( ∑ 1≤i≤m Xi) = ∑ 1≤i≤m E(Xi) = ∑ 1≤i≤m (1 − 1/m) n = m(1 − 1/m) n MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 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-品)P Q:What is the expected number of empty locations? 1 location i is empty 。X=0,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 自 口卡+①，22变Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20207/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 = ∑ 1≤i≤m Xi E(X) = E( ∑ 1≤i≤m Xi) = ∑ 1≤i≤m E(Xi) = ∑ 1≤i≤m (1 − 1/m) n = m(1 − 1/m) n MA Jun (Institute of Computer Software) Problem Solving May 14, 2020 7 / 34
Hash-table:Basic Idea After inserting n items into a hashtable with n locations 口卡4y，。老4=2)Q0 MA Jun (Institute of Computer Software) Problem Solving May14.20208/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 = ∑ 1≤i≤n Yi E(Y ) = E( ∑ 1≤i≤n Yi) = ∑ 1≤i≤n E(Yi) = ∑ 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 14, 2020 8 / 34