Page 1 Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_1.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing The Lecture Contains: Linear hashing Principle Searching Page 2 Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_1.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing The Lecture Contains: Linear hashing Principle Searching Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_2.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Linear hashing Number of buckets grow by at most 1 Linear growth Both primary and overflow buckets Overflow buckets are chained Family of hash functions n is initial number of buckets doubles the range of Page 3 Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_1.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing The Lecture Contains: Linear hashing Principle Searching Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_2.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Linear hashing Number of buckets grow by at most 1 Linear growth Both primary and overflow buckets Overflow buckets are chained Family of hash functions n is initial number of buckets doubles the range of Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_3.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Linear hashing Number of buckets grow by at most 1 Linear growth Both primary and overflow buckets Overflow buckets are chained Family of hash functions n is initial number of buckets doubles the range of Load factor decides when to split Split pointer decides which bucket to split is independent of overflowing bucket At level , is between 0 and is incremented and if at end, is reset to 0 Records in splitting bucket are rehashed using Equal chance of being in old and new buckets Page 4 Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_1.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing The Lecture Contains: Linear hashing Principle Searching Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_2.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Linear hashing Number of buckets grow by at most 1 Linear growth Both primary and overflow buckets Overflow buckets are chained Family of hash functions n is initial number of buckets doubles the range of Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_3.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Linear hashing Number of buckets grow by at most 1 Linear growth Both primary and overflow buckets Overflow buckets are chained Family of hash functions n is initial number of buckets doubles the range of Load factor decides when to split Split pointer decides which bucket to split is independent of overflowing bucket At level , is between 0 and is incremented and if at end, is reset to 0 Records in splitting bucket are rehashed using Equal chance of being in old and new buckets Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_4.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Principle Full buckets are not necessarily split Buckets split are not necessarily full Page 5 Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_1.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing The Lecture Contains: Linear hashing Principle Searching Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_2.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Linear hashing Number of buckets grow by at most 1 Linear growth Both primary and overflow buckets Overflow buckets are chained Family of hash functions n is initial number of buckets doubles the range of Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_3.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Linear hashing Number of buckets grow by at most 1 Linear growth Both primary and overflow buckets Overflow buckets are chained Family of hash functions n is initial number of buckets doubles the range of Load factor decides when to split Split pointer decides which bucket to split is independent of overflowing bucket At level , is between 0 and is incremented and if at end, is reset to 0 Records in splitting bucket are rehashed using Equal chance of being in old and new buckets Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_4.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Principle Full buckets are not necessarily split Buckets split are not necessarily full Objectives_template file:///C|/Documents%20and%20Settings/iitkrana1/My%20Documents/Google%20Talk%20Received%20Files/ist_data/lecture10/10_5.htm[6/14/2012 3:35:28 PM] Module 3: Hashing Lecture 10: Linear hashing Principle Full buckets are not necessarily split Buckets split are not necessarily full Principle: Every bucket will be split sooner or later and so all overflows will be reclaimed and rehashedRead More

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!