$//---------------------------------------------------------------------------$

$//$ MapEntry.java by Dale$/$Joyce$/$Weems Chapter $8$

$//$

$//$ Provides key, value pairs for use with a Map.

$//$ Keys are immutable.

$//---------------------------------------------------------------------------$

package ch$08.$maps;

public class MapEntry

$\{$

protected K key;

protected V value;

MapEntry$($K k$,$ V v$)$

$\{$

key $=$ k; value $=$ v;

$\}$

public K getKey$()\{$return key;$\}$

public V getValue$()\{$return value;$\}$

public void setValue$($V v$)\{$value $=$ v;$\}$

@Override

public String toString$()$

$//$ Returns a string representing this MapEntry.

$\{$

return "Key : $"+$ key $+"$

Value: $"+$ value;

$\}$

$\}$

$//---------------------------------------------------------------------------$

$//$ HMap.java by Dale$/$Joyce$/$Weems Chapter $8$

$/$ Implements a map using an array$-$based hash table, linear probing collision

$//$ resolution.

$//$

$//$ The remove operation is not supported. Invoking it will result in the

$//$ unchecked UnsupportedOperationException being thrown.

$//$

$//$ A map provides $($K $=$ key, V $=$ value$)$ pairs, mapping the key onto the value.

$//$ Keys are unique. Keys cannot be null.

$//$

$//$ Methods throw IllegalArgumentException if passed a null key argument.

$//$

$//$ Values can be null, so a null value returned by put or get does

$//$ not necessarily mean that an entry did not exist.

$//---------------------------------------------------------------------------$

package ch$08.$maps;

import java.util.Iterator;

public class HMap implements MapInterface

$\{$

protected MapEntry$[]$ map;

protected final int DEFCAP $=1000$; $//$ default capacity

protected final double DEFLOAD $=0\mathrm{.}75$; $//$ default load

protected int origCap; $//$ original capacity

protected int currCap; $//$ current capacity

protected double load;

protected int numPairs $=0$; $//$ number of pairs in this map

public HMap$()$

$\{$

map $=$ new MapEntry$[$DEFCAP$]$;

origCap $=$ DEFCAP;

currCap $=$ DEFCAP;

load $=$ DEFLOAD;

$\}$

public HMap$($int initCap, double initLoad$)$

$\{$

map $=$ new MapEntry$[$initCap$]$;

origCap $=$ initCap;

currCap $=$ initCap;

load $=$ initLoad;

$\}$

private void enlarge$()$

$//$ Increments the capacity of the map by an amount

$//$ equal to the original capacity.

$\{$

$//$ create a snapshot iterator of the map and save current size

Iterator$>$ i $=$ iterator$()$;

int count $=$ numPairs;

$//$ create the larger array and reset variables

map $=$ new MapEntry$[$currCap $+$ origCap$]$;

currCap $=$ currCap $+$ origCap;

numPairs $=0$;

$//$ put the contents of the current map into the larger array

MapEntry entry;

for $($int n $=1$; n $<=$ count; n$++)$

$\{$

entry $=$ i$.$next$()$;

this.put$(($K$)$entry$.$getKey$(),($V$)$entry$.$getValue$())$;

$\}$

$\}$

public V put$($K k$,$ V v$)$

$//$ If an entry in this map with key k already exists then the value

$//$ associated with that entry is replaced by value v and the original

$//$ value is returned; otherwise, adds the $($k$,$ v$)$ pair to the map and

$//$ returns null.

$\{$

if $($k $==$ null$)$

throw new IllegalArgumentException$("$Maps do not allow null keys."$)$;

MapEntry entry $=$ new MapEntry$($k$,$ v$)$;

int location Math.abs$($k$.$hashCode$())\%$ currCap;

while $(($map$[$location$]!=$ null$)$ && $!($map$[$location$].$getKey$().$equals$($k$)))$

location $=($location $+1)\%$ currCap;

if $($map$[$location$]==$ null$)//$ k was not in map

$\{$

map$[$location$]=$ entry;

numPairs$++$;

if $(($float$)$numPairs$/$currCap $>$ load$)$

enlarge$()$;

return null;

$\}$

else $//$ k already in map

$\{$

V temp $=($V$)$map$[$location$].$getValue$()$;

map$[$location$]=$ entry;

return temp;

$\}$

$\}$

public V get$($K k$)$

$//$ If an entry in this map with a key k exists then the value associated

$//$ with that entry is returned; otherwise null is returned.

$\{$

if $($k $==$ null$)$

throw new IllegalArgumentException$("$Maps do not allow null keys."$)$;

int location $=$ Math.abs$($k$.$hashCode$())\%$ currCap;

while $(($map$[$location$]!=$ null$)$ && $!($map$[$location$].$getKey$().$equals$($k$)))$

location $=($location $+1)\%$ currCap;

if $($map$[$location$]==$ null$)//$ k was not in map

return null;

else $//$ k in map

return $($V$)$map$[$location$].$getValue$()$;

$\}$

public V remove$($K k$)$

$//$ Throws UnsupportedOperationException.

$\{$

throw new UnsupportedOperationException$("$HMap does not allow remove."$)$;

$\}$

public boolean contains$($K k$)$

$//$ Returns true if an entry in this map with key k exists;

$//$ Returns false otherwise.

$\{$

if $($k $==$ null$)$

throw new IllegalArgumentException$("$Maps do not allow null keys."$)$;

int location $=$ Math.abs$($k$.$hashCode$())\%$ currCap;

while $($map$[$location$]!=$ null$)$

if $($map$[$location$].$

must modify the books HMap class directly to complete this.

$1.$It includes a toString method that prints out the entire contents.

$2.$Provide a working remove method, using an additional boolean value associated with each hash table slot to track removal.

$3.$ Instead of probing it uses buckets of linked lists of MapEntry objects.