Need help wiht this. I have the test code and HashSet.java longestChain an int m
ID: 3863559 • Letter: N
Question
Need help wiht this. I have the test code and HashSet.java
longestChain an int method that returns the number of nodes in the longest linked list (chain) of this HashSet. The empty set returns zero, most small sets return one, but sets where hash code collisions occur will have longer chains.
Test code:
public class Quiz18 {
public static void main(String[] args) {
HashSet<Character> test1 = new HashSet<Character>();
test1.add((char)97); test1.add('b'); test1.add('c');
System.out.println(test1); // [a,b,c]
System.out.println(test1.equals(test1)); // true
// char 97, 107, and 117 all three hash to 7
test1.add((char)107); test1.add((char)117);
System.out.println(test1); // [u,k,a,b,c]
System.out.println(test1.longestChain()); // 3
}
}
public class HashSet<E> {
private static final double MAX_LOAD_FACTOR = 0.75;
private HashEntry<E>[] elementData;
private int size;
// Constructs an empty set.
@SuppressWarnings("unchecked")
public HashSet() {
elementData = new HashEntry[10];
size = 0;
}
// ADD METHODS HERE for exercise solutions:
// toStirng method to print results to display
public String toString2(){
String result ="";
String index =" ";
String data [][] =new String[elementData.length][elementData.length];
boolean first = true;
int counter =0;
if(!isEmpty()){
for(int i =0; i<elementData.length;i++){
for(int j=0; j<elementData.length;j++){
data[i][j]=" ";
}
}
}
for(int i= 0; i<elementData.length;i++){
int j =0;
HashEntry<E> val = elementData[i];
index+= "[";
index+=Integer.toString(i);
index+="] ";
while(val!=null){
data[i][j++]+=val.data;
val = val.next;
}
if(counter<j)
counter=j;
index+="";
}
index+=" ";
result += index;
first=true;
for(int i= 0; i<counter; i++){
for(int j=0; j<elementData.length; j++){
if(!data[j][i].equals(" ")){
result+= data[j][i];
}
else{
result += " ";
result += " ";
result += " ";
}
}
}
return result;
}
public boolean equals(HashSet<E> s){
if(s instanceof HashSet) {
HashSet set = (s) ;
if(size != set.size())
return false;
for(int i = 0; i < elementData.length; i++) {
HashSet<E>.HashEntry<E> current = elementData[i];
while(current != null) {
if(!set.contains(current.data))
return false;
current = current.next;
}
}
return true;
}
return false;
}
// Adds the given element to this set, if it was not already
// contained in the set.
public void add(E value) {
if (!contains(value)) {
if (loadFactor() >= MAX_LOAD_FACTOR) {
rehash();
}
// insert new value at front of list
int bucket = hashFunction(value);
elementData[bucket] = new HashEntry<E>(value, elementData[bucket]);
size++;
}
}
// Removes all elements from the set.
public void clear() {
for (int i = 0; i < elementData.length; i++) {
elementData[i] = null;
}
size = 0;
}
// Returns true if the given value is found in this set.
public boolean contains(E value) {
int bucket = hashFunction(value);
HashEntry<E> current = elementData[bucket];
while (current != null) {
if (current.data.equals(value)) {
return true;
}
current = current.next;
}
return false;
}
// Returns true if there are no elements in this queue.
public boolean isEmpty() {
return size == 0;
}
// Removes the given value if it is contained in the set.
// If the set does not contain the value, has no effect.
public void remove(E value) {
int bucket = hashFunction(value);
if (elementData[bucket] != null) {
// check front of list
if (elementData[bucket].data.equals(value)) {
elementData[bucket] = elementData[bucket].next;
size--;
} else {
// check rest of list
HashEntry<E> current = elementData[bucket];
while (current.next != null && !current.next.data.equals(value)) {
current = current.next;
}
// if the element is found, remove it
if (current.next != null && current.next.data.equals(value)) {
current.next = current.next.next;
size--;
}
}
}
}
// Returns the number of elements in the queue.
public int size() {
return size;
}
// Returns a string representation of this queue, such as "[10, 20, 30]";
// The elements are not guaranteed to be listed in sorted order.
public String toString() {
String result = "[";
boolean first = true;
if (!isEmpty()) {
for (int i = 0; i < elementData.length; i++) {
HashEntry<E> current = elementData[i];
while (current != null) {
if (!first) {
result += ", ";
}
result += current.data;
first = false;
current = current.next;
}
}
}
return result + "]";
}
// Returns the preferred hash bucket index for the given value.
private int hashFunction(E value) {
return Math.abs(value.hashCode()) % elementData.length;
}
private double loadFactor() {
return (double) size / elementData.length;
}
// Resizes the hash table to twice its former size.
@SuppressWarnings("unchecked")
private void rehash() {
// replace element data array with a larger empty version
HashEntry<E>[] oldElementData = elementData;
elementData = new HashEntry[2 * oldElementData.length];
size = 0;
// re-add all of the old data into the new array
for (int i = 0; i < oldElementData.length; i++) {
HashEntry<E> current = oldElementData[i];
while (current != null) {
add((E)current.data);
current = current.next;
}
}
}
// Represents a single value in a chain stored in one hash bucket.
@SuppressWarnings("hiding")
private class HashEntry<E> {
public E data;
public HashEntry<E> next;
@SuppressWarnings("unused")
public HashEntry(E data) {
this(data, null);
}
public HashEntry(E data, HashEntry<E> next) {
this.data = data;
this.next = next;
}
}
}
Explanation / Answer
// =========== IN YOUR HashSet CLASS ADD THE FOLOWING METHOD =======================//
public int longestChain(){
int count = 0;
for(int i=0;i<elementData.length;i++){
HashEntry<E> list = elementData[i];
int innerCount = 0;
while(list != null){
list = list.next;
innerCount++;
}
if(count<innerCount)
count = innerCount;
}
return count;
}