Suppose that a company hires you as an IT expert for advancing their ID-System.

Your goal is to design a system that supports fast searching/insertion/deletion.

Array and Linked-list-based implementation led you to O(n) time complexity for searing/insertion/deletion in the worst case.

AVL trees led to log(n), but balancing and high depth are the major concerns in this scenario.

So, plan something else. Think before reading the solution.

Hashing can be a solution, but collision is a problem that you have to deal with for the best performance

. Task 1: Design a hash function that should perform best (nearly best, in terms of the number of collisions). Insert data into a hash table using the designed hash function.

Task 2: To avoid collisions, implement the linear probing technique. Now, note the problem with deletion. To avoid deletion problems, implement a chaining method.

Task-3: Implement linked-list-based chaining.

Task-4: Implement BST-based chaining.