CpE 207 Data Structure

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