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.
What is a B-Tree? Show how the letters A to P English alphabet can be entered into a B-tree of order 4.
Write a C language function to find the in-order successor of the root of a binary tree.
What is the benefit of using arrays of pointers instead of several pointer variables?
What are tunnelling and encapsulation in the context of mobile IP?
Write a C program to check a year is leap year or not.