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 the benefit of using arrays of pointers instead of several pointer variables?
Explain left factoring with suitable example.
What are tunnelling and encapsulation in the context of mobile IP?
For the input expression (4*7+1)*2, construct an annotated parse tree.
Write a C program to transpose of a matrix.
