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 pair 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
