img
Question:
Published on: 28 March, 2024

a) What do you mean by hashing ?

What are the applications where you will prefer hash tables to other data structures ?

What do you mean by collision ?How is it handled ? 

 

Answer:

 

a) Hashing provides the direct access of record from the file no matter where the record is in the file. This is possible with the help of a hashing function H which map the key with the corresponding key address or location. It provides the key-to-address transformation.

 

Applications of a Hash Table

Hash tables are good in situations where you have enormous amounts of data from which you would like to quickly search and retrieve information. A few typical hash table implementations would be in the following situations:

  • For driver's license record's. With a hash table, you could quickly get information about the driver (ie. name, address, age) given the licence number.

  • For compiler symbol tables. The compiler uses a symbol table to keep track of the user-defined symbols in a C++ program. This allows the compiler to quickly look up attributes associated with symbols (for example, variable names)

  • For internet search engines.

  • For telephone book databases. You could make use of a hash table implementatation to quickly look up John Smith's telephone number.

  • For electronic library catalogs. Hash Table implementations allow for a fast find among the millions of materials stored in the library.

  • For implementing passwords for systems with multiple users. Hash Tables allow for a fast retrieval of the password which corresponds to a given username.

 

Collision

 If two key k1 and k2 produce same bucket index L for same hash function, then it is called collision.

The collision resolution techniques can be into two board category:

1. open addressing

a. linear probing

b. Quadratic probing

c. double probing

2. chaining method.

 

Random questions