The goal of this project is to explore the insertion performance of a hash table

Question

The goal of this project is to explore the insertion performance of a hash table, using linear probing. You will produce a data set that shows the average displacement for the entire data set of size N when it is placed in a hash table of size M for various value of the ratio N/M. (this project is to be done in Java).

1. First, implement the hash table class described in the text book.

2. Next, write a test method (you can use the main() method of your HashTable class) that adds values to the hash table. You can generate random integers, or read words from a file, or anything convenient for you (I generated random numbers using StdRandom.uniform(1000000)). Each time a value is added, you will need to measure and record the displacement (how far each entry had to be shifted from its natural position, due to collision).

3. Generate a data set consisting of the average displacement across the whole data set (all N keys). Actually, you will need to do this a number of times.

4. Run step 3 for a variety of values of N for a given M.

5. Produce a graph: the X values are the different ratios of N/M, and the Y values are the average displacement across a number of data sets. The completeness and accuracy of your graph will be a significant part of your grade (3 or 4 data points won't cut it).

Explanation / Answer

<script type="text/javascript" src="jshashtable.js">

</script> <script type="text/javascript">

function HashTable(){

this.bucketCount = 100000;

this.buckets = [];

for (var i=0; i< this.bucketCount;i++){ this.buckets.push(new NaiveDict())

}

}

HashTable.prototype.hashFunction = function(key){

return hash;

}

public Value get(Key key)

     {

          for (int i = hash(key); keys[i] != null; i = (i + 1) % M)

               if (keys[i].equals(key))

                    return vals[i];

          return null;

     }

Test method (such as using the main() method of the HashTable class) that adds values to the hash table. Each time a value is added, you will need to measure and record the displacement (how far each entry had to be shifted from its natural position,

The x values are the different ratios of N/M, and the Y values are the average displacement across a number of data sets. The completeness and accuracy of the graph will be a significant part of the grade.

private int hash(Key key)

     {    return (key.hashCode() & 0x7fffffff) % M; }

     private void resize()           // See code below

     public void put(Key key, Value val)

     {

          if (N >= M/2) resize(2*M);     // double M

          int I;

          for (i = hash(key); keys[i] != null; i = (i + 1) % M)

               if (keys[i].equals(key)) { vals[i] = val; return; }

          keys[i] = key;

          vals[i] = val;

          N++;

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.