Linear Hashing - Hashing, PPT Computer Science Engineering (CSE) Notes | EduRev

Computer Science Engineering (CSE) : Linear Hashing - Hashing, PPT Computer Science Engineering (CSE) Notes | EduRev

 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
rehashed
 
 
 
 
 
 
 
 
 
 
 
 
 
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

Related Searches

Exam

,

Sample Paper

,

study material

,

shortcuts and tricks

,

Previous Year Questions with Solutions

,

Linear Hashing - Hashing

,

Linear Hashing - Hashing

,

Extra Questions

,

PPT Computer Science Engineering (CSE) Notes | EduRev

,

MCQs

,

PPT Computer Science Engineering (CSE) Notes | EduRev

,

Objective type Questions

,

mock tests for examination

,

Viva Questions

,

ppt

,

pdf

,

Important questions

,

Semester Notes

,

past year papers

,

video lectures

,

PPT Computer Science Engineering (CSE) Notes | EduRev

,

Free

,

practice quizzes

,

Linear Hashing - Hashing

,

Summary

;