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 ?
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.
a) Sort the following list using the Radix Sort :
189, 205, 986, 421, 97, 192, 535, 839, 562, 674
Write a C procram to G.C.D. of two no. using recursion.
Write the recursive algorithm to find x^ n.
Distinguish between Decision table versus decision tree