Chapter Notes - Designing Hash Tables (Hashing) Notes | EduRev

: Chapter Notes - Designing Hash Tables (Hashing) Notes | EduRev

 Page 1


Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Page 2


Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Designing a hash table
? Hash function: establishing a key with an
indexed location in a hash table.
? Index = hash(key) % table_size;
? Resolve conflicts:
? Need to handle multiple keys that may be mapped to
the same index.
? Two representative solutions
? Linear probe open addressing (will discuss more later)
? Chaining with separate lists.
Page 3


Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Designing a hash table
? Hash function: establishing a key with an
indexed location in a hash table.
? Index = hash(key) % table_size;
? Resolve conflicts:
? Need to handle multiple keys that may be mapped to
the same index.
? Two representative solutions
? Linear probe open addressing (will discuss more later)
? Chaining with separate lists.
Separate Chaining
? Each table entry
stores a list of items
? So we don’t need to
worry about multiple
keys mapped to the
same entry.
Page 4


Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Designing a hash table
? Hash function: establishing a key with an
indexed location in a hash table.
? Index = hash(key) % table_size;
? Resolve conflicts:
? Need to handle multiple keys that may be mapped to
the same index.
? Two representative solutions
? Linear probe open addressing (will discuss more later)
? Chaining with separate lists.
Separate Chaining
? Each table entry
stores a list of items
? So we don’t need to
worry about multiple
keys mapped to the
same entry.
Separate Chaining (contd.)
Type Declaration for
Separate Chaining
Hash Table
Page 5


Hashing - 2
Designing Hash Tables
Sections 5.3, 5.4, 5.4, 5.6
Designing a hash table
? Hash function: establishing a key with an
indexed location in a hash table.
? Index = hash(key) % table_size;
? Resolve conflicts:
? Need to handle multiple keys that may be mapped to
the same index.
? Two representative solutions
? Linear probe open addressing (will discuss more later)
? Chaining with separate lists.
Separate Chaining
? Each table entry
stores a list of items
? So we don’t need to
worry about multiple
keys mapped to the
same entry.
Separate Chaining (contd.)
Type Declaration for
Separate Chaining
Hash Table
Separate Chaining (contd.)
Read More
Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!