277 lines
7.8 KiB
Java
277 lines
7.8 KiB
Java
package dictionary;
|
|
|
|
import arraylist.ArrayIndexList;
|
|
import arraylist.IndexList;
|
|
import exceptions.HashExceptionKey;
|
|
import exceptions.InvalidEntryException;
|
|
import position.NodePositionList;
|
|
import priorityqueue.Entry;
|
|
import priorityqueue.MyEntry;
|
|
|
|
import exceptions.InvalidKeyException;
|
|
import java.util.Iterator;
|
|
|
|
/**
|
|
* Created with MONSTER.
|
|
* User: xgiovio
|
|
* Date: 11/05/2014
|
|
* Time: 19:28
|
|
*/
|
|
|
|
//Complete implementation by xgiovio
|
|
// Collisions resolved with linear probing
|
|
|
|
public class LinearProbingHashTable<K,V> implements Dictionary<K,V> {
|
|
|
|
IndexList<Entry<K,V>> table = null;
|
|
Entry<K,V> AVAIBLE = null;
|
|
int avaible_slots = 0;
|
|
int elements = 0;
|
|
int p = 0;
|
|
int scale = 0;
|
|
int shift = 0;
|
|
|
|
public LinearProbingHashTable(int in_p, int in_size){
|
|
table = new ArrayIndexList<Entry<K, V>>(in_size);
|
|
AVAIBLE = new MyEntry<K, V>(null,null);
|
|
p = in_p;
|
|
java.util.Random rand = new java.util.Random();
|
|
scale = rand.nextInt(p-1) + 1;
|
|
shift = rand.nextInt(p);
|
|
|
|
for (int i= 0 ; i< in_size ;i++){
|
|
table.add(i,AVAIBLE);
|
|
avaible_slots ++;
|
|
}
|
|
}
|
|
|
|
public LinearProbingHashTable(int in_size){
|
|
this(109345121,in_size);
|
|
}
|
|
|
|
public LinearProbingHashTable(){
|
|
this(109345121,100);
|
|
}
|
|
|
|
|
|
|
|
public float load_factor () throws InvalidKeyException{
|
|
float ret = (size() / (float)raw_size());
|
|
if ( ret >= 0.5 ) {
|
|
reformat();
|
|
return load_factor();
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
public int raw_size (){
|
|
return table.size();
|
|
}
|
|
|
|
@Override
|
|
public int size() {
|
|
return elements;
|
|
}
|
|
|
|
@Override
|
|
public boolean isEmpty() {
|
|
return (size() == 0);
|
|
}
|
|
|
|
protected int hash ( K key) {
|
|
return (int) ((Math.abs(key.hashCode()*scale + shift) % p) % raw_size());
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
public Entry<K, V> find(K key) throws InvalidKeyException {
|
|
|
|
checkKey(key);
|
|
int h = hash(key);
|
|
int count = 0;
|
|
for (;count < raw_size();){
|
|
if (table.get( (h+count)%raw_size() ) == AVAIBLE)
|
|
return null;
|
|
if (table.get((h+count)%raw_size()) == null)
|
|
continue;
|
|
if (table.get((h+count)%raw_size()).getKey().equals(key))
|
|
return table.get((h+count)%raw_size());
|
|
count++;
|
|
}
|
|
return null;
|
|
}
|
|
|
|
@Override
|
|
public Iterable<Entry<K, V>> findAll(K key) throws InvalidKeyException {
|
|
checkKey(key);
|
|
NodePositionList<Entry<K,V>> to_return = new NodePositionList<Entry<K, V>>();
|
|
int h = hash(key);
|
|
int count = 0;
|
|
for (;count < raw_size();){
|
|
if (table.get((h+count)%raw_size()) == AVAIBLE)
|
|
return to_return;
|
|
if (table.get((h+count)%raw_size()) == null)
|
|
continue;
|
|
if (table.get((h+count)%raw_size()).getKey().equals(key))
|
|
to_return.addLast( table.get((h+count)%raw_size()));
|
|
count++;
|
|
}
|
|
return to_return;
|
|
}
|
|
|
|
@Override
|
|
public Entry<K, V> insert(K key, V value) throws InvalidKeyException {
|
|
checkKey(key);
|
|
if (load_factor() >= 0.5 )
|
|
reformat();
|
|
int h = hash(key);
|
|
if (table.get(h) == AVAIBLE || table.get(h ) == null ) {
|
|
MyEntry<K, V> n = new MyEntry<K, V>(key,value);
|
|
table.set(h,n);
|
|
avaible_slots--;
|
|
elements++;
|
|
return n;
|
|
} else {
|
|
int count = 1;
|
|
for ( ; count < raw_size() ;) {
|
|
if (table.get((h+count)%raw_size()) == AVAIBLE || table.get((h+count)%raw_size()) == null ) {
|
|
MyEntry<K, V> n = new MyEntry<K, V>(key, value);
|
|
table.set((h+count)%raw_size(), n);
|
|
avaible_slots--;
|
|
elements++;
|
|
return n;
|
|
}
|
|
count++;
|
|
}
|
|
return null; // non dovresti essere qui a causa del load factor
|
|
}
|
|
}
|
|
protected Entry<K, V> insert_refactor(Entry<K, V> in_e) throws InvalidKeyException {
|
|
// no check of in_e because this function is used internally from reformat
|
|
int h = hash(in_e.getKey());
|
|
if (table.get(h) == AVAIBLE || table.get(h ) == null ) {
|
|
Entry<K, V> n = in_e;
|
|
table.set(h,n);
|
|
avaible_slots--;
|
|
elements++;
|
|
return n;
|
|
} else {
|
|
int count = 1;
|
|
for ( ; count < raw_size() ;) {
|
|
if (table.get((h+count)%raw_size()) == AVAIBLE || table.get((h+count)%raw_size()) == null ) {
|
|
Entry<K, V> n = in_e;
|
|
table.set((h+count)%raw_size(), n);
|
|
avaible_slots--;
|
|
elements++;
|
|
return n;
|
|
}
|
|
count++;
|
|
}
|
|
return null; // non dovresti essere qui a causa del load factor
|
|
}
|
|
}
|
|
|
|
@Override
|
|
public Entry<K, V> remove(Entry<K, V> e) throws InvalidEntryException {
|
|
if (e == null)
|
|
throw new InvalidEntryException();
|
|
int h = hash(e.getKey());
|
|
if (table.get(h) == AVAIBLE)
|
|
throw new InvalidEntryException();
|
|
if (table.get(h) == null){
|
|
|
|
} else {
|
|
if (table.get(h) == e) {
|
|
table.set(h, null);
|
|
elements--;
|
|
avaible_slots++;
|
|
return e;
|
|
}
|
|
}
|
|
int count = 1;
|
|
for (; count < raw_size() ;){
|
|
if (table.get((h+count)%raw_size()) == AVAIBLE)
|
|
throw new InvalidEntryException();
|
|
if (table.get((h+count)%raw_size()) == null){
|
|
|
|
} else {
|
|
if (table.get((h+count)%raw_size()) == e) {
|
|
table.set((h+count)%raw_size(), null);
|
|
elements--;
|
|
avaible_slots++;
|
|
return e;
|
|
}
|
|
}
|
|
count++;
|
|
}
|
|
throw new InvalidEntryException();
|
|
|
|
}
|
|
|
|
@Override
|
|
public Iterable<Entry<K, V>> entries() {
|
|
|
|
NodePositionList<Entry<K,V>> ret = new NodePositionList<Entry<K, V>>();
|
|
|
|
for (int i = 0 ; i< raw_size() ;i++){
|
|
if (table.get(i) != AVAIBLE && table.get(i) != null ){
|
|
ret.addLast(table.get(i));
|
|
}
|
|
}
|
|
return ret;
|
|
}
|
|
|
|
|
|
protected void checkKey(K key) throws InvalidKeyException {
|
|
if (key == null )
|
|
throw new InvalidKeyException("Invalid key");
|
|
}
|
|
|
|
|
|
void reformat () throws InvalidKeyException{
|
|
|
|
Iterable<Entry<K,V>> ite = entries();
|
|
int new_size = raw_size() * 2;
|
|
IndexList<Entry<K,V>> table2 = new ArrayIndexList<Entry<K, V>>(new_size);
|
|
avaible_slots = 0;
|
|
elements = 0;
|
|
java.util.Random rand = new java.util.Random();
|
|
scale = rand.nextInt(p-1) + 1; // new hash scaling factor
|
|
shift = rand.nextInt(p); //// new hash shifting factor
|
|
|
|
for (int i= 0 ; i< (new_size) ;i++){
|
|
table2.add(i,AVAIBLE);
|
|
}
|
|
table = table2;
|
|
|
|
for (Entry<K,V> e : ite){
|
|
insert_refactor(e);
|
|
|
|
}
|
|
}
|
|
|
|
|
|
public String toString() {
|
|
|
|
Iterator<Entry<K,V>> it = entries().iterator();
|
|
|
|
String to_return = "";
|
|
to_return = to_return + "[";
|
|
|
|
for (;it.hasNext();){
|
|
Entry<K,V> t = it.next();
|
|
|
|
if (it.hasNext()) {
|
|
|
|
to_return+=(t.toString() + " , ");
|
|
} else {
|
|
|
|
to_return+=(t.toString());
|
|
}
|
|
}
|
|
|
|
return to_return+= "]";
|
|
}
|
|
}
|