COURSE : Data Structures and algorithms
UNIT I :Hashing
, Syllabus
⚫ Hash Table-
⚫ Concepts-
⚫ Hash function, perfect hash function , properties of
good hash function, division, multiplication, extraction,
mid-square, folding and universal ,basic operations,
bucket, collision, probe, synonym, load density, full
table, load factor,
⚫ Rehashing, issues in hashing,
⚫ Collision resolution strategies- open addressing and
chaining,
⚫ Extendible hashing
⚫ Skip List- representation, searching and operations-
2 insertion, removal
, Hash Table
⚫ Hash table is a data structure that is used to store <key
value>
Pairs
⚫ It uses a hash function to compute an index to an array in
which an element will be inserted or searched
⚫ Under reasonable assumptions the average time required to
search for an element in a hash table is O(1).
3
, Introduction
⚫ Hashing is finding an address where the data is to be
stored as well as located using a key with the help of the a
function.
⚫ Hashing is a method of directly computing the address of
the record with the help of a key by using a suitable
mathematical function called the hash function
⚫ The resulting address is used as the basis for storing and
retrieving records and this address is called as home
address of the record
⚫ For array to store a record in a hash table, hash function is
applied to the key of the record being stored, returning an
index within the range of the hash table
⚫ The item is then stored in the table of that index position 4
UNIT I :Hashing
, Syllabus
⚫ Hash Table-
⚫ Concepts-
⚫ Hash function, perfect hash function , properties of
good hash function, division, multiplication, extraction,
mid-square, folding and universal ,basic operations,
bucket, collision, probe, synonym, load density, full
table, load factor,
⚫ Rehashing, issues in hashing,
⚫ Collision resolution strategies- open addressing and
chaining,
⚫ Extendible hashing
⚫ Skip List- representation, searching and operations-
2 insertion, removal
, Hash Table
⚫ Hash table is a data structure that is used to store <key
value>
Pairs
⚫ It uses a hash function to compute an index to an array in
which an element will be inserted or searched
⚫ Under reasonable assumptions the average time required to
search for an element in a hash table is O(1).
3
, Introduction
⚫ Hashing is finding an address where the data is to be
stored as well as located using a key with the help of the a
function.
⚫ Hashing is a method of directly computing the address of
the record with the help of a key by using a suitable
mathematical function called the hash function
⚫ The resulting address is used as the basis for storing and
retrieving records and this address is called as home
address of the record
⚫ For array to store a record in a hash table, hash function is
applied to the key of the record being stored, returning an
index within the range of the hash table
⚫ The item is then stored in the table of that index position 4
