## Question

## Transcribed Text

## Solution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

class ThreeTenHashTable1<K,V> {//you must use this storage for the hash table

//and you may not alter this variable's name, type, etc.

private TableEntry<K,V>[] storage;

/* +++++++++++++++++++ YOUR CODE HERE +++++++++++++++++++ */

//Add additional instance variables here!

//You may also add additional _private_ methods if you'd like.

private int size, capacity;

//private TableEntry<K,V> tombStone = new TableEntry<K, V>(null, null);

@SuppressWarnings("unchecked")

public ThreeTenHashTable1(int size) {

//Create a hash table where the size of the storage is

//the provided size (number of "slots" in the table)

//You may assume size is >= 2

this.storage = new TableEntry[size];

this.size = 0;

this.capacity = size;

//Remember... if you want an array of ClassWithGeneric<V>, the following format ___SHOULD NOT___ be used:

// ClassWithGeneric<V>[] items = (ClassWithGeneric<V>,[]) Object[10];

//instead, use this format:

// ClassWithGeneric<V>[] items = (ClassWithGeneric<V>,[]) ClassWithGeneric[10];

}

public int getCapacity() {

//return how many "slots" are in the table

//O(1)

return capacity;

}

public int size() {

//return the number of elements in the table

//O(1)

return size;

}

private int findKey(K k)

{

int pos = Math.abs(k.hashCode()) % capacity, pos0 = pos;

while (storage[pos]!=null)

{

if (storage[pos].getKey().equals(k))

break;

pos = (pos + 1) % capacity;

if (pos == pos0)

return -1;

}

return pos;

}

public void put(K k, V v) {

//Place value v at the location of key k.

//Use linear probing if that location is in use.

//You may assume both k and v will not be null.

//Hint: Make a TableEntry to store in storage

//and use the absolute value of k.hashCode() for

//the probe start.

//If the key already exists in the table

//replace the current value with v.

//If the load on the table is >= 80% _after_ adding

//expand the table to twice the size.

//Worst case: O(n), Average case: O(1)

int pos = this.findKey(k);

if (storage[pos] == null) this.size++;

else if (storage[pos].getValue() == null) size++;

storage[pos] = new TableEntry<K, V>(k, v);

if (size *1.0 / capacity >= 0.8)

rehash(2*capacity);

}

public V remove(K k) {

//Remove the given key (and associated value)

//from the table. Return the value removed.

//If the value is not in the table, return null.

//Hint 1: Remember to leave a tombstone!

//Hint 2: Does it matter what a tombstone is?

// Yes and no... You need to be able to tell

// the difference between an empty spot and

// a tombstone and you also need to be able

// to tell the difference between a "real"

// element and a tombstone.

//Worst case: O(n), Average case: O(1)

int pos = this.findKey(k);

if (pos == -1)

return null;

V oldValue = storage[pos].getValue();

storage[pos] = new TableEntry<K, V>(k, null); // tombstone

this.size--;

return oldValue;

}

public V get(K k) {

//Given a key, return the value from the table....

By purchasing this solution you'll be able to access the following files:

Solution.zip.