Data Structures and Applications (CS204) Module 4
Module 5
Graphs: Definitions, Terminologies, Matrix and Adjacency List Representation of Graphs,
Elementary Graph operations.
Hashing: Hash Table organizations, Hashing Functions, Static and Dynamic Hashing
Summarization of all modules.
Case Studies:
a. Design a music playlist system: The functionality of a playlist needs to be implemented, i.e.,
adding a song to the playlist, playing the next song, playing the previous song, switching to a song,
display of songs based on its genre type etc.
b. Efficiently manage table reservations for a restaurant: Managing table reservations for a
restaurant efficiently involves handling various aspects such as availability of tables, booking
requests, and ensuring a smooth flow of operations.
Text book1: 6.1, 6.2, 8.1, 8.2, 8.3
5.2 Hashing
Why Hashing?
Internet has grown to millions of users generating terabytes of content every day. So, if we
need to process a very large data set, we need a new technique called hashing that allows us to
update and retrieve any entry in constant time which means, the amount of time to perform the
operation does not depend on data size n.
Hashing is a process of converting a data set of variable size into a data set of a fixed size.
Two types of hashing – static hashing and dynamic hashing.
5.2.1 Static Hashing
In static hashing the key and its index (pair) are stored in a table, ht, called the hash table. The
hash table is partitioned into b buckets, ht[0], …, ht[b-1]. A bucket is said to consist of s slots, each
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 1
, Data Structures and Applications (CS204) Module 4
slot being large enough to hold one pair (key and its index). Usually s=1, and each bucket can hold
exactly one pair. The address or location of key k is determined by a hash function, h, which maps
keys into buckets. Thus for any key k, h(k) is an integer in the range 0 through b-1. h(k) is the hash
of k.
Hash table Organization
Hash table is a data structure in which keys are mapped into its respective index by using a hash
function.
Hashing is a technique to convert a range of key values into a range of indexes of an array.
Hashing is method of inserting data into hash table.
In a hash table, data is stored in an array format, where each data value has its own unique index value.
Access of data becomes very fast if we know the index of the desired data.
Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the
size of the data (Retrieving the element in one search). Hash Table uses an array as a storage medium and
uses hash technique to generate an index where an element is to be inserted or is to be located from.
Hashing Functions
1.Division Method (Remainder method)
It is the most simple method of hashing an integer x. This method divides x(key) by M(size of
table) and then uses the remainder obtained as the index to store key. In this case, the hash
function can be given as
h(x) = x mod M
Generally, it is best to choose M to be a prime number because making M a prime number
increases the likelihood that the keys are mapped with a uniformity in the output range of
values. (To reduce the number of collisions the table size should be chosen as a prime number).
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 2
Module 5
Graphs: Definitions, Terminologies, Matrix and Adjacency List Representation of Graphs,
Elementary Graph operations.
Hashing: Hash Table organizations, Hashing Functions, Static and Dynamic Hashing
Summarization of all modules.
Case Studies:
a. Design a music playlist system: The functionality of a playlist needs to be implemented, i.e.,
adding a song to the playlist, playing the next song, playing the previous song, switching to a song,
display of songs based on its genre type etc.
b. Efficiently manage table reservations for a restaurant: Managing table reservations for a
restaurant efficiently involves handling various aspects such as availability of tables, booking
requests, and ensuring a smooth flow of operations.
Text book1: 6.1, 6.2, 8.1, 8.2, 8.3
5.2 Hashing
Why Hashing?
Internet has grown to millions of users generating terabytes of content every day. So, if we
need to process a very large data set, we need a new technique called hashing that allows us to
update and retrieve any entry in constant time which means, the amount of time to perform the
operation does not depend on data size n.
Hashing is a process of converting a data set of variable size into a data set of a fixed size.
Two types of hashing – static hashing and dynamic hashing.
5.2.1 Static Hashing
In static hashing the key and its index (pair) are stored in a table, ht, called the hash table. The
hash table is partitioned into b buckets, ht[0], …, ht[b-1]. A bucket is said to consist of s slots, each
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 1
, Data Structures and Applications (CS204) Module 4
slot being large enough to hold one pair (key and its index). Usually s=1, and each bucket can hold
exactly one pair. The address or location of key k is determined by a hash function, h, which maps
keys into buckets. Thus for any key k, h(k) is an integer in the range 0 through b-1. h(k) is the hash
of k.
Hash table Organization
Hash table is a data structure in which keys are mapped into its respective index by using a hash
function.
Hashing is a technique to convert a range of key values into a range of indexes of an array.
Hashing is method of inserting data into hash table.
In a hash table, data is stored in an array format, where each data value has its own unique index value.
Access of data becomes very fast if we know the index of the desired data.
Thus, it becomes a data structure in which insertion and search operations are very fast irrespective of the
size of the data (Retrieving the element in one search). Hash Table uses an array as a storage medium and
uses hash technique to generate an index where an element is to be inserted or is to be located from.
Hashing Functions
1.Division Method (Remainder method)
It is the most simple method of hashing an integer x. This method divides x(key) by M(size of
table) and then uses the remainder obtained as the index to store key. In this case, the hash
function can be given as
h(x) = x mod M
Generally, it is best to choose M to be a prime number because making M a prime number
increases the likelihood that the keys are mapped with a uniformity in the output range of
values. (To reduce the number of collisions the table size should be chosen as a prime number).
Prof.V.Sonia Devi, Dept. of CSE, CITech 2024-25 Page 2
