package hjelpeklasser;
import java.util.*;
public class Hashtabell<T> implements Beholder<T>
{
private final float tetthet;
private int terskel;
private int antall;
private Beholder<T>[] hash;
private int indeks(T verdi)
{
return (verdi.hashCode() & 0x7fffffff) % hash.length;
}
@SuppressWarnings("unchecked")
private void rehash()
{
Beholder<T>[] gammel = hash;
hash = new Beholder[2*gammel.length + 1];
terskel = (int)(tetthet * hash.length);
for (int i = 0; i < hash.length; i++)
{
hash[i] = new EnkeltLenketListe<>();
}
for (Beholder<T> beholder : gammel)
{
if (!beholder.tom())
{
for (T t : beholder) leggInn(t);
}
}
}
@SuppressWarnings("unchecked")
public Hashtabell(int dimensjon)
{
if (dimensjon < 1) throw
new IllegalArgumentException("Ulovig dimensjon!");
hash = new Beholder[dimensjon];
for (int i = 0; i < dimensjon; i++)
{
hash[i] = new EnkeltLenketListe<>();
}
tetthet = 0.75f;
terskel = (int)(tetthet*dimensjon);
antall = 0;
}
public Hashtabell()
{
this(13);
}
@Override
public int antall() { return antall; }
@Override
public boolean tom() { return antall == 0; }
@Override
public boolean leggInn(T verdi)
{
if (verdi == null)
throw new IllegalArgumentException("verdi er null!");
if (antall >= terskel) rehash();
antall++;
return hash[indeks(verdi)].leggInn(verdi);
}
@Override
public boolean inneholder(T verdi)
{
if (verdi == null) return false;
else return hash[indeks(verdi)].inneholder(verdi);
}
@Override
public boolean fjern(T verdi)
{
if (verdi == null) return false;
antall--;
return hash[indeks(verdi)].fjern(verdi);
}
@Override
public void nullstill()
{
for (Beholder<T> beholder : hash) beholder.nullstill();
antall = 0;
}
@Override
public String toString()
{
if (tom()) return "[]";
StringBuilder s = new StringBuilder("[");
for (Beholder<T> beholder : hash)
{
if (!beholder.tom())
{
for (T t : beholder)
s.append(t).append(',').append(' ');
}
}
s.delete(s.length() - 2, s.length());
s.append(']');
return s.toString();
}
private class HashIterator implements Iterator<T>
{
private int indeks = 0;
private Iterator<T> i;
private HashIterator()
{
while (indeks < hash.length && hash[indeks].tom()) indeks++;
if (indeks < hash.length) i = hash[indeks].iterator();
else i = hash[0].iterator();
}
@Override
public boolean hasNext()
{
return i.hasNext();
}
@Override
public T next()
{
if (!hasNext())
throw new NoSuchElementException("Ingen flere verdier");
T temp = i.next();
if (!i.hasNext())
{
indeks++;
while (indeks < hash.length && hash[indeks].tom()) indeks++;
if (indeks < hash.length) i = hash[indeks].iterator();
}
return temp;
}
@Override
public void remove()
{
throw new UnsupportedOperationException();
}
}
@Override
public Iterator<T> iterator()
{
return new HashIterator();
}
}