Two marks Questions with Answers

Two Marks Questions with Answers

Q.1 What is hashing ?

Ans.

Hashing is a technique of storing the elements directly at the specific location in the hash table. The hashing makes use of hash function to place the record at its position. Using the same hash function the data can be retrieved directly from the hash table.

Q.2 List out the various techniques of hashing.

Ans. : Various techniques of hashing are -

1. Division method         4. Digit folding

2. Mid square method     5. Multiplicative hash function

3. Digit analysis.

Q.3 What is uniform hash function ?

Ans; An uniform hash function is one that equally distributes data items over the whole hash table data structure.

Q.4 What is rehashing ?

Ans. Rehashing is a technique in which the table is resized. That means the size of the table is doubled by creating a new table. The total size of the table is usually a prime number. Following are the situations in which the rehashing is required -

1. When table is completely full.

2. With quadratic probing the table is filled half.

3. When insertions fail due to overflow.

Q.5 What is collision in hashing ?

Ans; The situation in which the hash function returns the same hash key for more than one record is called collision.

Q.6 What is overflow in hashing?

Ans. : The situation in which there is no room for a new pair in the hash table is called overflow.

Q.7What are the characteristics of good hashing function ?

Ans. : 

Rules for choosing good hash function

1. The hash function should be simple to compute.

2. Number of collisions should be less while placing the record in the hash table. Ideally no collision should occur. Such a function is called perfect hash function.

3. Hash function should produce such keys which will get distributed uniformly over an array.

4.The hash function should depend on every bit of the key. Thus the hash function that simply extracts the portion of a key is not suitable.

Q.8 What is the major problem in linear probing ?

Ans. : One major problem in linear probing is primary clustering. Primary clustering is the process in which a block of data is formed in the hash table when collision is resolved.

Q.9 What are the applications of hashing ?

OR Why hashing is needed?

Ans. Hashing is used for obtaining the position of the desire record efficiently. Following are some applications of hashing -

• In compilers to keep track of declared variables.

• For online spelling the hashing functions are used.

• Hashing help in Game playing programs to store the moves made by the player.

• In web browsing programs for caching the web pages hashing is used.ee

Q.10 What are the advantages of rehashing ?

Ans;  Following are the advantages -

1. This technique provides the programmer a flexibility to enlarge the table size if required.

2. Only the space gets doubled with simple hash function which avoids occurrence of collisions.

Q.11 What is the advantage of chained hash table over open addressing scheme ?

 Ans. : The deletion of particular record from the hash function becomes easier.

 Q.12 State some major drawback of chaining.

Ans; Requirement of additional data structure is the major drawback of chaining.

Q.13 Specify the hashing technique in which the table size can be changed.

Ans; The rehashing is a hashing technique in which the table size can be changed.

 Q.14What will be the position of the number 3111 in a hash table, when the mid square method is applied? (The table size is 1000)

Ans. : The position will be 783 because (3111)2 = 9678321.

Q.15 Which hash function maintains the record in order of hash field values? Ans. : The folding method maintains the record in order of hash field values.

Q.16 Enlist the conditions in which the rehashing is required.

Ans. : The rehashing is required in following conditions -

1. Table is completely full.

2. Insertion fails due to overflowing.

3. When there is a need to transfer the contents from old hash table to new hash table.

Q.17 What do you understand by collision resolution by chaining?

Ans. : When collision happens we create a new memory location outside the existing table and use a chain to link to the new memory location.

Q.18 Use of pointer is in    hashing technique.

Ans. : chaining.

Q.19 Define extendible hashing

Ans;  Extendible hashing is a technique which handles a large amount of data. The data to be placed in hash table is by extracting certain number of bits. Extendible hashing grow and shrink similar to B-trees.

Q.20 Give the significance of extendible hashing.

Ans;

1) Extendible hashing is a dynamic hashing technique. The hash table grows or shrinks on addition or deletion of records.

2) There is no hash table overflow problem when extendible hashing technique is used.

Q.21 What are the advantages and disadvantages of separate chaining and linear probing?

Ans. : 

1) Separate chaining:

Advantages:

i) It is simple to implement.

ii) Hash table never fills and we can add elements in the linked list fashion.

iii) The meaning of hash function can be preserved.

Disadvantages:

i) It requires extra space to maintain links.

ii) If the chain becomes too long then it takes more time to search an element.

iii) There may be wastage of space as some parts of hash table are never used. 

2)Linear probing:

Advantage :

1) It is faster due to locality of references.

Disadvantage :

1) It forms primary clustering. Hence only some part of hash table remain occupied and other part remains vaccant.