Question: \"Implement a generic Map that supports the put and get operations. Th
ID: 3595155 • Letter: Q
Question
Question:
"Implement a generic Map that supports the put and get operations. The implementation
will store a hash table of pairs (key, definition). Figure 5.55 provides the Map
specification (minus some details)."
And the extra specifics: Implement a generic Map class using the structure provided in the book. You must use theTheQuadraticProbingHashTable.java included and it must not be changed. Provide equals and hashCode methods in the private class to get this working properly.
Here is the code for TheQuadraticProbingHashTable.java:
// QuadraticProbing Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// bool insert( x ) --> Insert x
// bool remove( x ) --> Remove x
// bool contains( x ) --> Return true if x is present
// void makeEmpty( ) --> Remove all items
/**
* Probing table implementation of hash tables.
* Note that all "matching" is based on the equals method.
* @author Mark Allen Weiss
*/
public class QuadraticProbingHashTable
{
/**
* Construct the hash table.
*/
public QuadraticProbingHashTable( )
{
this( DEFAULT_TABLE_SIZE );
}
/**
* Construct the hash table.
* @param size the approximate initial size.
*/
public QuadraticProbingHashTable( int size )
{
allocateArray( size );
doClear( );
}
/**
* Insert into the hash table. If the item is
* already present, do nothing.
* @param x the item to insert.
*/
public boolean insert( AnyType x )
{
// Insert x as active
int currentPos = findPos( x );
if( isActive( currentPos ) )
return false;
array[ currentPos ] = new HashEntry<>( x, true );
theSize++;
// Rehash; see Section 5.5
if( ++occupied > array.length / 2 )
rehash( );
return true;
}
/**
* Expand the hash table.
*/
private void rehash( )
{
HashEntry [ ] oldArray = array;
// Create a new double-sized, empty table
allocateArray( 2 * oldArray.length );
occupied = 0;
theSize = 0;
// Copy table over
for( HashEntry entry : oldArray )
if( entry != null && entry.isActive )
insert( entry.element );
}
/**
* Method that performs quadratic probing resolution.
* @param x the item to search for.
* @return the position where the search terminates.
*/
private int findPos( AnyType x )
{
int offset = 1;
int currentPos = myhash( x );
while( array[ currentPos ] != null &&
!array[ currentPos ].element.equals( x ) )
{
currentPos += offset; // Compute ith probe
offset += 2;
if( currentPos >= array.length )
currentPos -= array.length;
}
return currentPos;
}
/**
* Remove from the hash table.
* @param x the item to remove.
* @return true if item removed
*/
public boolean remove( AnyType x )
{
int currentPos = findPos( x );
if( isActive( currentPos ) )
{
array[ currentPos ].isActive = false;
theSize--;
return true;
}
else
return false;
}
/**
* Get current size.
* @return the size.
*/
public int size( )
{
return theSize;
}
/**
* Get length of internal table.
* @return the size.
*/
public int capacity( )
{
return array.length;
}
/**
* Find an item in the hash table.
* @param x the item to search for.
* @return the matching item.
*/
public boolean contains( AnyType x )
{
int currentPos = findPos( x );
return isActive( currentPos );
}
public AnyType get( AnyType x )
{
int currentPos = findPos( x );
if( isActive( currentPos ))
return array[currentPos].element;
else
return null;
}
/**
* Return true if currentPos exists and is active.
* @param currentPos the result of a call to findPos.
* @return true if currentPos is active.
*/
private boolean isActive( int currentPos )
{
return array[ currentPos ] != null && array[ currentPos ].isActive;
}
/**
* Make the hash table logically empty.
*/
public void makeEmpty( )
{
doClear( );
}
private void doClear( )
{
occupied = 0;
for( int i = 0; i < array.length; i++ )
array[ i ] = null;
}
private int myhash( AnyType x )
{
int hashVal = x.hashCode( );
hashVal %= array.length;
if( hashVal < 0 )
hashVal += array.length;
return hashVal;
}
private static class HashEntry
{
public AnyType element; // the element
public boolean isActive; // false if marked deleted
public HashEntry( AnyType e )
{
this( e, true );
}
public HashEntry( AnyType e, boolean i )
{
element = e;
isActive = i;
}
}
private static final int DEFAULT_TABLE_SIZE = 101;
private HashEntry [ ] array; // The array of elements
private int occupied; // The number of occupied cells
private int theSize; // Current size
/**
* Internal method to allocate array.
* @param arraySize the size of the array.
*/
private void allocateArray( int arraySize )
{
array = new HashEntry[ nextPrime( arraySize ) ];
}
/**
* Internal method to find a prime number at least as large as n.
* @param n the starting number (must be positive).
* @return a prime number larger than or equal to n.
*/
private static int nextPrime( int n )
{
if( n % 2 == 0 )
n++;
for( ; !isPrime( n ); n += 2 )
;
return n;
}
/**
* Internal method to test if a number is prime.
* Not an efficient algorithm.
* @param n the number to test.
* @return the result of the test.
*/
private static boolean isPrime( int n )
{
if( n == 2 || n == 3 )
return true;
if( n == 1 || n % 2 == 0 )
return false;
for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false;
return true;
}
}
And here is the structure of the generic Map class provided by the book:
class Map
{
public Map( )
public void put( KeyType key, ValueType val )
public ValueType get( KeyType key )
public boolean isEmpty( )
public void makeEmpty( )
private QuadraticProbingHashTable> items;
private static class Entry
{
KeyType key;
ValueType value;
// Appropriate Constructors, etc.
}
}
Thanks, please provide working code! The other answer available for this question in the textbook solutions isn't really all that helpful.
Explanation / Answer
Program
---------------
package chegg;
import java.util.Objects;
import java.util.Scanner;
class QuadraticProbingHashTable<K, V> {
private static final int DEFAULT_TABLE_SIZE = 101;
static final HashEntry<?, ?>[] EMPTY_TABLE = {};
@SuppressWarnings("unchecked")
transient HashEntry<K, V>[] table = (HashEntry<K, V>[]) EMPTY_TABLE;
private int currentSize, maxSize;
HashEntry<K, V>[] arrays = null;
/**
*
*/
public QuadraticProbingHashTable() {
this(DEFAULT_TABLE_SIZE);
}
/**
*
* @param capacity
*/
public QuadraticProbingHashTable(int size) {
currentSize = 0;
maxSize = size;
allocateArray(size);
doClear();
}
/**
*
* @param n
* @return
*/
private static int nextPrime(int n) {
if (n % 2 == 0)
n++;
for (; !isPrime(n); n += 2)
;
return n;
}
/**
*
* @param n
* @return
*/
private static boolean isPrime(int n) {
if (n == 2 || n == 3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
private void doClear() {
for (int i = 0; i < arrays.length; i++)
arrays[i] = null;
}
@SuppressWarnings("unchecked")
private void allocateArray(int arraySize) {
arrays = new HashEntry[nextPrime(arraySize)];
}
/*
* private int myhash(K x) { int hashVal = x.hashCode(); hashVal %=
* arrays.length; if (hashVal < 0) hashVal += arrays.length; return hashVal;
* }
*/
private int myhash(K key) {
return key.hashCode() % maxSize;
}
/** Function to get size of hash table **/
public int getSize() {
return currentSize;
}
/** Function to check if hash table is full **/
public boolean isFull() {
return currentSize == maxSize;
}
/** Function to check if hash table is empty **/
public boolean isEmpty() {
return getSize() == 0;
}
/** Fucntion to check if hash table contains a key **/
public boolean contains(K key) {
return get(key) != null;
}
private int findPos(K x) {
int offset = 1;
int currentPos = myhash(x);
while (arrays[currentPos] != null && !arrays[currentPos].key.equals(x)) {
currentPos += offset; // Compute ith probe
offset += 2;
if (currentPos >= arrays.length)
currentPos -= arrays.length;
}
return currentPos;
}
/**
*
* @param key
* @param val
*/
public void insert(K key, V val) {
int tmp = myhash(key);
int i = tmp, h = 1;
do {
if (arrays[i] == null) {
arrays[currentSize] = new HashEntry<K, V>(tmp, key, val, null);
currentSize++;
return;
}
if (arrays[i].key.equals(key)) {
arrays[i].value = val;
return;
}
i = (i + h * h++) % maxSize;
} while (i != tmp);
}
public V insert1(K k, V v) {
if (k == null)
return putForNullKey(v);
int hash = myhash(k);
int i = indexFor(hash, arrays.length);
for (HashEntry<K, V> e = arrays[i]; e != null; e = e.next) {
K k1;
if (e.hash == hash && ((k1 = e.key) == k || k1.equals(k))) {
V oldValue = e.value;
e.value = v;
return oldValue;
}
}
addEntry(hash, k, v, i);
return null;
}
private V putForNullKey(V value) {
for (HashEntry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
addEntry(0, null, value, 0);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((currentSize >= maxSize) && (null != arrays[bucketIndex])) {
rehash();
hash = (null != key) ? myhash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
void createEntry(int hash, K key, V value, int bucketIndex) {
HashEntry<K, V> e = arrays[bucketIndex];
arrays[bucketIndex] = new HashEntry<K, V>(hash, key, value, e);
currentSize++;
}
private void rehash() {
HashEntry<K, V>[] oldArray = arrays;
// Create a new double-sized, empty table
allocateArray(2 * oldArray.length);
currentSize = 0;
maxSize = 0;
// Copy table over
for (HashEntry<K, V> entry : oldArray)
if (entry != null)
insert1(entry.key, entry.value);
}
final HashEntry<K, V> getEntry(K key) {
if (currentSize == 0) {
return null;
}
int hash = (key == null) ? 0 : myhash(key);
for (HashEntry<K, V> e = arrays[indexFor(hash, arrays.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash
&& ((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}
private V getForNullKey() {
if (maxSize == 0) {
return null;
}
for (HashEntry<K, V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
static int indexFor(int h, int length) {
// assert Integer.bitCount(length) == 1 :
// "length must be a non-zero power of 2";
return h & (length - 1);
}
/** Function to get value for a given key **/
public V get(K k) {
if (k == null)
return getForNullKey();
HashEntry<K, V> entry = getEntry(k);
return null == entry ? null : entry.getValue();
}
static class HashEntry<K, V> implements java.util.Map.Entry<K, V> {
final K key;
V value;
HashEntry<K, V> next;
int hash;
/**
* Creates new entry.
*/
HashEntry(int h, K k, V v, HashEntry<K, V> n) {
value = v;
next = n;
key = k;
hash = h;
}
public final K getKey() {
return key;
}
public final V getValue() {
return value;
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (!(o instanceof HashEntry))
return false;
@SuppressWarnings("unchecked")
HashEntry<K, V> e = (HashEntry<K, V>) o;
Object k1 = getKey();
Object k2 = e.getKey();
if (k1 == k2 || (k1 != null && k1.equals(k2))) {
Object v1 = getValue();
Object v2 = e.getValue();
if (v1 == v2 || (v1 != null && v1.equals(v2)))
return true;
}
return false;
}
public final int hashCode() {
return Objects.hashCode(getKey()) ^ Objects.hashCode(getValue());
}
public final String toString() {
return getKey() + "=" + getValue();
}
}
}
class Map<K, V> {
private QuadraticProbingHashTable<K, V> items;
public Map() {
items = new QuadraticProbingHashTable<K, V>(10);
}
public Map(int capacity) {
items = new QuadraticProbingHashTable<K, V>(capacity);
}
public void put(K key, V val) {
items.insert1(key, val);
}
public V get(K key) {
return items.get(key);
}
public boolean isEmpty() {
return items.isEmpty();
}
public void makeEmpty() {
// items.makeEmpty();
}
}
public class QuadraticProbingHashTableTest {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.println("Enter Intial capacity for Map or Enter Map size");
Map<String, String> map = new Map<String, String>(scan.nextInt());
char ch;
do {
System.out.println(" Hash Table Operations ");
System.out.println("1. insert ");
System.out.println("2. get");
int choice = scan.nextInt();
switch (choice) {
case 1:
System.out.println("Enter key and value");
map.put(scan.next(), scan.next());
break;
case 2:
System.out.println("Enter key");
System.out.println("Value = " + map.get(scan.next()));
break;
default:
System.out.println("Wrong Entry ");
break;
}
System.out.println(" Do you want to continue (Type y or n) ");
ch = scan.next().charAt(0);
} while (ch == 'Y' || ch == 'y');
}
}
--------------- End---------------------
Output
-------------
Enter Intial capacity for Map or Enter Map size
5
Hash Table Operations
1. insert
2. get
1
Enter key and value
10
100
Do you want to continue (Type y or n)
y
Hash Table Operations
1. insert
2. get
1
Enter key and value
20
200
Do you want to continue (Type y or n)
y
Hash Table Operations
1. insert
2. get
2
Enter key
20
Value = 200
Do you want to continue (Type y or n)
y
Hash Table Operations
1. insert
2. get
2
Enter key
10
Value = 100
Do you want to continue (Type y or n)
y
Hash Table Operations
1. insert
2. get
3
Wrong Entry
Do you want to continue (Type y or n)
2
Description
----------------
I have done some changes in exiting Java code which you provided in actual question.
the basically the exiting code does not support the Map structure. map always store elements in key and value pair. i did the same.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.