MODULE V
1. What is Hashing? Discuss the properties of a good hash function. Explain the following
hash function with proper example(10)
a. Division
b. Midsquare
c. Folding
2. Explain static and dynamic hashing in detail(8)
3. What is chained hashing? Discuss its pros and cons. Construct the hash table to insert the
keys: 7, 24, 18, 52, 36, 54, 11, 23 in a chained hash table of 9 memory locations. Use h(k)
= k mod m(8)
4. What is dynamic hashing? Explain the following techniques with examples: (8)
i) Dynamic hashing using directories ii) Directory less dynamic hashing
5. Consider a hash table of size 10. Using linear probing, insert the keys 72, 27, 36, 24, 63,
81, 92, and 101 into the table (10)
6. Consider a hash table of size 10. Using quadratic probing, insert the keys 72, 27, 36, 24,
63, 81, and 101 into the table. Take c1 = 1 and c2 = 3 (10)
7. Define the leftist tree. Give its declaration in C. Check whether the given binary tree is a
leftist tree or not. Explain your answer(5)
8. Define min Leftist tree. Meld the given min leftist trees(5)
9. Define double ended priority queue and min-max heap. Explain Insertion and Deletion in
a min-max heap with example(8)
10. What is Optimal Binary Search Tree? Write a c function to find an Optimal Binary
Search Tree.
, 1. What is Hashing? Discuss the properties of a good hash function. Explain the
following hash function with proper example(8)
a. Division Method
b. Midsquare Method
c. Folding Method
Hashing
• Hashing is a technique to convert a range of key values into a range of indexes of an array.
In general we use modulo operator to get a range of key values. Hashing technique use a
special function called the Hash function which is used to map a given value with a
particular key for faster access of elements.
• Each Item can be located in a Bin/Bucket/Shelf according to its key value (number)
• Most simple Hash Method/Function
int hash(int key)
{
return key % SIZE;
}
Hash Function
• A hash function is any function that can be used to map a data set of an arbitrary size to a
data set of a fixed size, which falls into the hash table. The values returned by a hash
function are called hash values, hash codes, hash sums, or simply hashes. There are many
hash functions that use numeric or alphanumeric keys.
Properties of good Hash Function
• Hash function should be simple to compute
• Number of collision should be less
• The hash function uses all the input data
• The hash function "uniformly" distributes the data across the entire set of possible hash
values
• The hash function generates very different hash values for similar strings
Types of Hash functions
o Division Method
o Mid Square Method
o Folding Method
i) Modular method /Division Method :
• It is the most simple method of hashing an integer x. This method divides x by size of
hash table M and then uses the remainder obtained. In this case, the hash function can
be given as
h(x) = x mod M
• Example: To calculate the hash values of keys 1234 and 5462. Solution Setting M =
97, hash values can be calculated as:
h(1234) = 1234 % 97 = 70
h(5642) = 5642 % 97 = 16
• Mid-square Method
o The mid-square method is a good hash function which works in two steps:
o Step 1: Square the value of the key. That is, find k2.
o Step 2: Extract the middle r digits of the result obtained in Step 1.
o In the mid-square method, the same r digits must be chosen from all the keys.
, o Therefore, the hash function can be given as:
▪ h(k) = s where s is obtained by selecting r digits from k2.
o Example: To calculate the hash value for keys 1234 and 5642 using the mid-square
method:
▪ The hash table has 100 memory locations.
▪ Solution: Note that the hash table has 100 memory locations whose indices
vary from 0 to 99.
▪ This means that only two digits are needed to map the key to a location in
the hash table, so r = 2.
• When k = 1234, k2 = 1522756, h (1234) = 27
• When k = 5642, k2 = 31832164, h (5642) = 21
• Folding Method:
o The folding method works in the following two steps:
o Step 1: Divide the key value into a number of parts. That is, divide k into parts k1,
k2, ..., kn, where each part has the same number of digits except the last part which
may have lesser digits than the other parts.
o Step 2: Add the individual parts. That is, obtain the sum of k1 + k2 + ... + kn. The
hash value is produced by ignoring the last carry, if any. Note that the number of
digits in each part of the key will vary depending upon the size of the hash table. .
o Example: Given a hash table of 100 locations, calculate the hash value using
folding method for keys 5678 and 34567
o Solution: Since there are 100 memory locations to address, we will break the key
into parts where each part (except the last) will contain two digits. The hash values
can be obtained as shown below: Key: 34567, Parts: 34,56 and 7, Sum:97 so, Hash
value: 97 Key: 5678, Parts: 56 and 78, Sum:134 Hash value: 34 (ignore carry)
2. Explain static and dynamic hashing in detail(8)
Static Hashing
• In static hashing, the identifiers are stored in a fixed size table called a hash table
• When a search key is given hash function always computes the same address
• Hashing technique in which the table(bucket) size remains the same (Fixed during
compilation time) is called static hashing
• A static hashing scheme is one where the size of the hash table is fixed
• Various techniques of static hashing are linear probing and chaining
• As the size is fixed, this type of hashing consist handling overflow of elements
(Collision)efficiently
• Example of hash functions: h(k) = k MOD m (k is key & m is size of hash table)
1. What is Hashing? Discuss the properties of a good hash function. Explain the following
hash function with proper example(10)
a. Division
b. Midsquare
c. Folding
2. Explain static and dynamic hashing in detail(8)
3. What is chained hashing? Discuss its pros and cons. Construct the hash table to insert the
keys: 7, 24, 18, 52, 36, 54, 11, 23 in a chained hash table of 9 memory locations. Use h(k)
= k mod m(8)
4. What is dynamic hashing? Explain the following techniques with examples: (8)
i) Dynamic hashing using directories ii) Directory less dynamic hashing
5. Consider a hash table of size 10. Using linear probing, insert the keys 72, 27, 36, 24, 63,
81, 92, and 101 into the table (10)
6. Consider a hash table of size 10. Using quadratic probing, insert the keys 72, 27, 36, 24,
63, 81, and 101 into the table. Take c1 = 1 and c2 = 3 (10)
7. Define the leftist tree. Give its declaration in C. Check whether the given binary tree is a
leftist tree or not. Explain your answer(5)
8. Define min Leftist tree. Meld the given min leftist trees(5)
9. Define double ended priority queue and min-max heap. Explain Insertion and Deletion in
a min-max heap with example(8)
10. What is Optimal Binary Search Tree? Write a c function to find an Optimal Binary
Search Tree.
, 1. What is Hashing? Discuss the properties of a good hash function. Explain the
following hash function with proper example(8)
a. Division Method
b. Midsquare Method
c. Folding Method
Hashing
• Hashing is a technique to convert a range of key values into a range of indexes of an array.
In general we use modulo operator to get a range of key values. Hashing technique use a
special function called the Hash function which is used to map a given value with a
particular key for faster access of elements.
• Each Item can be located in a Bin/Bucket/Shelf according to its key value (number)
• Most simple Hash Method/Function
int hash(int key)
{
return key % SIZE;
}
Hash Function
• A hash function is any function that can be used to map a data set of an arbitrary size to a
data set of a fixed size, which falls into the hash table. The values returned by a hash
function are called hash values, hash codes, hash sums, or simply hashes. There are many
hash functions that use numeric or alphanumeric keys.
Properties of good Hash Function
• Hash function should be simple to compute
• Number of collision should be less
• The hash function uses all the input data
• The hash function "uniformly" distributes the data across the entire set of possible hash
values
• The hash function generates very different hash values for similar strings
Types of Hash functions
o Division Method
o Mid Square Method
o Folding Method
i) Modular method /Division Method :
• It is the most simple method of hashing an integer x. This method divides x by size of
hash table M and then uses the remainder obtained. In this case, the hash function can
be given as
h(x) = x mod M
• Example: To calculate the hash values of keys 1234 and 5462. Solution Setting M =
97, hash values can be calculated as:
h(1234) = 1234 % 97 = 70
h(5642) = 5642 % 97 = 16
• Mid-square Method
o The mid-square method is a good hash function which works in two steps:
o Step 1: Square the value of the key. That is, find k2.
o Step 2: Extract the middle r digits of the result obtained in Step 1.
o In the mid-square method, the same r digits must be chosen from all the keys.
, o Therefore, the hash function can be given as:
▪ h(k) = s where s is obtained by selecting r digits from k2.
o Example: To calculate the hash value for keys 1234 and 5642 using the mid-square
method:
▪ The hash table has 100 memory locations.
▪ Solution: Note that the hash table has 100 memory locations whose indices
vary from 0 to 99.
▪ This means that only two digits are needed to map the key to a location in
the hash table, so r = 2.
• When k = 1234, k2 = 1522756, h (1234) = 27
• When k = 5642, k2 = 31832164, h (5642) = 21
• Folding Method:
o The folding method works in the following two steps:
o Step 1: Divide the key value into a number of parts. That is, divide k into parts k1,
k2, ..., kn, where each part has the same number of digits except the last part which
may have lesser digits than the other parts.
o Step 2: Add the individual parts. That is, obtain the sum of k1 + k2 + ... + kn. The
hash value is produced by ignoring the last carry, if any. Note that the number of
digits in each part of the key will vary depending upon the size of the hash table. .
o Example: Given a hash table of 100 locations, calculate the hash value using
folding method for keys 5678 and 34567
o Solution: Since there are 100 memory locations to address, we will break the key
into parts where each part (except the last) will contain two digits. The hash values
can be obtained as shown below: Key: 34567, Parts: 34,56 and 7, Sum:97 so, Hash
value: 97 Key: 5678, Parts: 56 and 78, Sum:134 Hash value: 34 (ignore carry)
2. Explain static and dynamic hashing in detail(8)
Static Hashing
• In static hashing, the identifiers are stored in a fixed size table called a hash table
• When a search key is given hash function always computes the same address
• Hashing technique in which the table(bucket) size remains the same (Fixed during
compilation time) is called static hashing
• A static hashing scheme is one where the size of the hash table is fixed
• Various techniques of static hashing are linear probing and chaining
• As the size is fixed, this type of hashing consist handling overflow of elements
(Collision)efficiently
• Example of hash functions: h(k) = k MOD m (k is key & m is size of hash table)
