 # Assignment 2: Hash Tables Setup • Download the assignment2.z...

## Question

Show 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 +++++++++++++++++++ */
//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;
//instead, use this format:
//         ClassWithGeneric<V>[] items = (ClassWithGeneric<V>,[]) ClassWithGeneric;
}

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.

\$38.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

### Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.