CpE 207 Data Structure You are expected to Implement a map using two different techniques, namely: Implement a map using Hashing techniques with N=100013, and separate chaining for collision handling. Implement a map using AVL trees. For Key/Value Pair you may assume the following The key is an integer, which can be generated as a random integer from 0 -> 99999 Value is a random name generated by concatenating two names selected randomly from an array of names (you should create an array of 50 names) Your first Task is an array of m transaction with the following conditions m is the number of transactions in a Test suite, you will test for m = 1000, 10000, 100000, 1000000 Transaction will have two fields Transaction type which can be 0 indicating a put call, 70% of all transactions 1 indicating a get call, 20% of all transactions. 2 indicating a remove call, 10% of all transactions. The second field is a key value pai
r generated randomly as explained above. Your Solution should have a minimum of the following classes Pair attributes key : int, Value: String Transaction Attributes opType : int (0, 1, 2), pair: Pair Static final String names[]: a list of 50-100 names Methods Transaction generateTestCase(): This methods creates a random transactions with a probability of 70% to be a put, 20% a get, or 10% remove, and the pair with a random key from 0 -> 99999 and a random name Transaction [] generateTestSuite(int m): this method generates m random transactions a returns them as an array of size m. TestDrive Methods TestRun(int m): this method first generate a TestSuite of size m then runs it against a map implemented using an arraylist, a hashmap, an AVL maps, you should measure the run time for each run and print it. Position: an Interface Node: a binary tree node BinaryTree: a BinaryTree Interface AVLtree : implements a BinaryTree