COSC 311  Homework hw1108

Distributed: 11/8/2018      Due: 11/15/2018

Hash 20 randomly generated int values (in the range 10 .. 50 inclusive) to a hash table.

Do linear probing to resolve collisions.

The initial hash table is size 8.  

When the hash table reaches 75% occupancy, you must create a new hash table that
is doubled in size. All values in the old table must be re-hashed to the new
table.
Therefore, the first 6 values will hash to initial table (size 8).
When you attempt to insert the 7th value, you will exceed maximum occupancy. So
you must create a new table, size 16, rehash the values, insert the 7th value.

The hash table size 16 can hold a maximum of 12 values.

The hash table size 32 can hold a maximum of 24 values.

After you have generated and hashed all 20 values, to demonstrate correctness,
you must output the final hash table as follows:
index   data value
0       <value>
1
2       <value>
3
4
5       <value>
6       <value>
...     ...


Constraints:
(1) Pseudo-code:
  Create empty hashTable size int[8].
  Initialize count = 0;                 // number elements in hashTable
  
  Create randomly generated data, put into inputArray[20];
  
  for (int i = 0; i < 20; i++) {
    key = inputArray[i];
    index = key % tableSize;
    insert key to hashTable, using linear probe to resolve collision;
    count++;
    if (count/tableSize >= .75) {
      create new hash table doubled in size;
      rehash all data items in old hash table;
      }
    }
    
    Output final hash table;
    
(2) Use exactly one random number generator. Initial seed set to 97.

(3) You may not generate duplicate input data.  
That is, you must do "selection without replacement."

(4) Only one Java file.

(5) Do NOT use ArrayList. Your data structure must be int[].

(6) Include the standard header.

(7) Minimal (or no) comments.

Grade based on:
(1) Correct functioning.
(2) Good readability.
(3) Good style, alignment, variable names, etc.  


Addendum:
For this homework you may not generate duplicate input values. Here is a straight-forward
approach to doing this in a hygienic way.

Say you want to generate 5 unique values from the set { 11, 12, 13, 14, 15, 16, 17, 18 }

Create an array size 8 and initialize it with the domain:

indexes:   0     |   1   |   2   |   3   |   4   |   5   |   6   |   7  
values:    11    |   12  |   13  |   14  |   15  |   16  |   17  |   18

max = 7;
repeat 5 times:
    ix = generate random int in range 0, ... max (inclusive)
    print (array[ix]);               // this is the random number
    array[ix] = array[max];          // remove used value from domain
    max--;                           // shrink array