import java.util.Iterator; import java.util.NoSuchElementException; public class
ID: 3919673 • Letter: I
Question
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedHashSet<T> implements Set<T>
{
private LinkedList<T>[] array;
private int size;
@SuppressWarnings("unchecked")
public LinkedHashSet(int capacity)
{
array = new LinkedList[capacity];
for (int i = 0; i < capacity; i++)
{
array[i] = new LinkedList<T>();
}
}
public int size()
{
return size;
}
private LinkedListIterator<T> findMatch(T item)
{
// You must implement this method.
return null;
}
public T getMatch(T item)
{
LinkedListIterator<T> iterator = findMatch(item);
if (item.equals(iterator.getValue()))
{
return iterator.getValue();
}
else
{
return null;
}
}
public T add(T item)
{
// You must implement this method.
return null;
}
public T remove(T item)
{
// Implementing this method is optional.
throw new UnsupportedOperationException();
}
public Iterator<T> iterator()
{
return new IteratorImpl<T>(array);
}
// Static nested class (see extra material on inner classes)
private static class IteratorImpl<T> implements Iterator<T>
{
private int index = -1;
private LinkedList<T>[] array;
private Iterator<T> llIterator;
private IteratorImpl(LinkedList<T>[] array)
{
this.array = array;
findNext();
}
private void findNext()
{
do
{
index++;
}
while(index < array.length && (!array[index].iterator().hasNext()));
llIterator = index < array.length ? array[index].iterator() : null;
}
public boolean hasNext()
{
return index < array.length;
}
public T next()
{
if (!hasNext())
{
throw new NoSuchElementException();
}
T result = llIterator.next();
if (!llIterator.hasNext())
{
findNext();
}
return result;
}
}
}
1 Linked-List Hash Tables In lecture, we implemented linear probing as one technique for resolving collisions in a hash table. An alternative is to store an array of linked lists as the hash table. Whereas linear probing searches for an empty array index that is merely close to an element's hash index, a linked-list implementation allows each element to be inserted into a linked list at its exact hash index. The linked list allows us to have multiple elements at each index of the array, so collisions become a non-issue. There is a file on Moodle called LinkedHashSet.java that contains the start of an implementation of a hash table using linked lists. The iterator ) method has been taken care of for you, as has a constructor that initializes an array of linked lists and a size field. getMatch has been partially implemented, but depends on a subroutine called findMatch ) that you must implement. findMatch 0 should take an item as a parameter and do the following: 1. Use the item's hashCode () method to generate an array index. (Refer to the implementation of HashSet from lecture if you're not sure how to map a hashCode to an array index.) 2. Obtain a LinkedListIterator from the linked list at the index obtained in step 1 3. Advance the iterator until a call of getValue to the iterator returns the item you are searching for, or until the iterator has reached the end of the list.Explanation / Answer
here is your sol : ----------------->>>>>>>>>>
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.*;
public class LinkedHashSet<T> implements Set<T>
{
private LinkedList<T>[] array;
private int _size;
private int _capacity;
@SuppressWarnings("unchecked")
public LinkedHashSet(int capacity)
{
array = new LinkedList[capacity];
_size = 0;
_capacity = capacity;
for (int i = 0; i < capacity; i++)
{
array[i] = new LinkedList<T>();
}
}
public int size()
{
return _size;
}
private LinkedListIterator<T> findMatch(T item)
{
// You must implement this method.
int key = item.hashCode()%_capacity;
//you can call here the LinkedList iterator method i do not know the method name please refer to LinkedList class
LinkedListIterator<T> itr = array[key].iterator();
while(itr.hasNext()){
if(item.equals(itr.getValue())){
return itr;
}
itr.next();
}
//if not found return the start of the LinkedListIterator
return array[key].iterator();
}
public T getMatch(T item)
{
LinkedListIterator<T> iterator = findMatch(item);
if (item.equals(iterator.getValue()))
{
return iterator.getValue();
}
else
{
return null;
}
}
public T add(T item)
{
// You must implement this method.
LinkedListIterator<T> itr = findMatch(item);
if(item.equals(itr.getValue())){
//if item already present in the hasSet
return item;
}else{
//if not present in the hash set
int key = item.hashCode()%_capacity;
array[key].add(item);
return item;
}
return null;
}
public T remove(T item)
{
// Implementing this method is optional.
LinkedListIterator<T> itr = findMatch(item);
if(item.equals(itr.getValue())){
//if item already present in the hasSet
return array[key].remove(item);
}
return null;
throw new UnsupportedOperationException();
}
public Iterator<T> iterator()
{
return new IteratorImpl<T>(array);
}
// Static nested class (see extra material on inner classes)
private static class IteratorImpl<T> implements Iterator<T>
{
private int index = -1;
private LinkedList<T>[] array;
private Iterator<T> llIterator;
private IteratorImpl(LinkedList<T>[] array)
{
this.array = array;
findNext();
}
private void findNext()
{
do
{
index++;
}
while(index < array.length && (!array[index].iterator().hasNext()));
llIterator = index < array.length ? array[index].iterator() : null;
}
public boolean hasNext()
{
return index < array.length;
}
public T next()
{
if (!hasNext())
{
throw new NoSuchElementException();
}
T result = llIterator.next();
if (!llIterator.hasNext())
{
findNext();
}
return result;
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.