please answer

$/*$ This is a program to explore collision resolution in hashing

$*$ NUMITEMS is the number of items to be inserted

$*$ PRIME$1$ should be a prime number that is larger than twice NUMITEMS

$*$ quadratic collision resolution will not work otherwise

$*$ PRIME$2$ is used in double hashing and must be less than PRIME$1$

$*$ SEED is the seed for the random number generator

$*$ it is needed to compare the methods for the same list of pseudo random numbers

$*$ change the value to get a different sequence

$*$ change "new Random$($SEED$)"$ to "new Random$()"$ to get a different sequence every time

$*/$

import java.util.$*$;

public class LabHashing $\{$

$$ static final int NUMITEMS $=50000$;

$$ static final int PRIME$1=100003$;

$$ static final int PRIME$2=41$;

$$ static final int SEED $=12345$;

$$ static Random rand;

$$ public static void main$($String$[]$ args$)\{$

$$ System.out.println$("$Linear Probing"$)$;

$$ rand $=$ new Random$($SEED$)$;

$$ HashLinear tableLinear $=$ new HashLinear$($PRIME$1)$;

$$ hashIt$($tableLinear$)$;

$$

$$ System.out.println$("$Quadratic Probing"$)$;

$$ rand $=$ new Random$($SEED$)$;

$$ HashQuadratic tableQuadratic $=$ new HashQuadratic$($PRIME$1)$;

$$ hashIt$($tableQuadratic$)$;

$$

$$ System.out.println$("$Double Hash Probing"$)$;

$$ rand $=$ new Random$($SEED$)$;

$$ HashDouble tableDouble $=$ new HashDouble$($PRIME$1,$PRIME$2)$;

$$ hashIt$($tableDouble$)$;

$\}$

$$

$$ static void hashIt$($Hash table$)\{$

$$ int total $=0$;

$$ for$($int i$=0$; i $\{$

$$ int capacity;

$$ E$[]$ table;

$$ int numCollisions;

$$

$$ public Hash$($int size$)\{$

$$ capacity $=$ size;

$$ table $=($E$[])$new Object$[$size$]$;

$\}$

$$

$$ public int insert$($E it$)\{$

$$ numCollisions $=0$;

$$ int h $=$ Math.abs$($it$.$hashCode$())\%$ capacity;

$$ if $($table$[$h$]==$ null$)\{$

$$ table$[$h$]=$ it;

$$ return numCollisions;

$\}$

$$ if $($table$[$h$].$equals$($it$))$ return numCollisions;$//$ don't allow duplicates

$$ while$($table$[$h$]!=$ null && $!$table$[$h$].$equals$($it$))\{$

$$ numCollisions$++$;

$$ h $=$ increment$($it$,$ h$)$;

$\}$

$$ if $($table$[$h$]==$ null$)\{$

$$ table$[$h$]=$ it;

$\}$

$$ return numCollisions;

$\}$

$$ int increment$($E it$,$ int h$)\{$

$$ return $($h $+1)\%$ capacity;

$\}$

$$

$\}$

class HashLinear extends Hash $\{$

$$ public HashLinear$($int size$)\{$

$$ super$($size$)$;

$\}$

$$

$\}$

class HashQuadratic extends Hash $\{$

$$ public HashQuadratic$($int size$)\{$

$$ super$($size$)$;

$\}$

$$

$$ int increment$($E it$,$ int h$)\{$

$$ return $($h $+2*$ numCollisions $-1)\%$ capacity;

$\}$

$$

$\}$

class HashDouble extends Hash $\{$

$$ int mod;

$$ public HashDouble$($int size, int m$2)\{$

$$ super$($size$)$;

$$ mod $=$ m$2$;

$\}$

$$

$$ int increment$($E it$,$ int h$)\{$

$$ int hash$2=$ mod $-($Math$.$abs$($it$.$hashCode$())\%$ mod$)$;

$$ return $($h $+$ hash$2)\%$ capacity;

$\}$

$\}$

Use LabHashing.java as a starting point.

It provides a very simple implementation of hashing that you can use to explore three

collision resolution methods.

Change values of the constants that are defined at the beginning of the program to

examine

What happens when the load factor increases? $($Above $0\mathrm{.}5,$ you may have to comment

out the quadratic hashing call.$)$

What effect does PRIME$2$ have on double hashing?

What other interesting effects can you find?

create a Word document with graphs of your collision

resolution counts and observation: