Hash-table:Basic Idea Model Assumption Model oInserting n keys:sequence of n s 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. 口卡+①，2是生QC MA Jun (Institute of Computer Software) Problem Solving My14.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
Hash-table:Basic Idea Model Assumption Model o Inserting n keys:sequence of n s 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 o=n/m (a:loading factor) 4口卡40，左·生·生Q0 MA Jun (Institute of Computer Software) Problem Solving My14.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
Hash-table:Basic ldea Empty location After inserting n items into m locations 口+4y，法=2)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? 口卡+①，2是生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 口卡+①，2是生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