Lad mig proeve at illustrere hvordan det virker med en hjemmestrikket hash tabel.
package hashtable;
public class PrimitiveHashTable<K,V> {
private static class PrimitiveEntry<K,V> {
private K key;
private V value;
private int index;
public PrimitiveEntry(K key, V value) {
this.key = key;
this.value = value;
this.index = -1;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
private int capacity;
private PrimitiveEntry<K,V> table[];
private int nextfree;
public PrimitiveHashTable(int capacity) {
this.capacity = capacity;
this.table = new PrimitiveEntry[2 * capacity];
this.nextfree = capacity;
}
public void put(K key, V value) {
int ix = key.hashCode() % capacity;
if(table[ix] == null) {
table[ix] = new PrimitiveEntry<K,V>(key, value);
} else {
if(nextfree >= table.length) throw new RuntimeException("Table is full");
while(table[ix].getIndex() >= 0) ix = table[ix].getIndex();
table[nextfree] = new PrimitiveEntry<K,V>(key, value);
table[ix].setIndex(nextfree);
nextfree++;
}
}
public V get(K key) {
int ix = key.hashCode() % capacity;
if(table[ix] == null) {
return null;
} else {
while(ix >= 0) {
if(table[ix].getKey().equals(key)) {
return table[ix].getValue();
}
ix = table[ix].getIndex();
}
}
return null;
}
}
package hashtable;
public class Test {
public static void main(String[] args) {
PrimitiveHashTable<String,Boolean> map = new PrimitiveHashTable<String,Boolean>(100);
map.put("en", true);
map.put("to", true);
map.put("tre", true);
System.out.println(map.get("to"));
System.out.println(map.get("fire"));
PrimitiveHashTable<Bad,Boolean> map2 = new PrimitiveHashTable<Bad,Boolean>(100);
map2.put(new Bad("en"), true);
map2.put(new Bad("to"), true);
map2.put(new Bad("tre"), true);
System.out.println(map2.get(new Bad("to")));
System.out.println(map2.get(new Bad("fire")));
}
}
class Bad {
private String s;
public Bad(String s) {
this.s = s;
}
@Override
public int hashCode() {
return 42;
}
@Override
public boolean equals(Object obj) {
return obj != null && obj instanceof Bad && s.equals(((Bad)obj).s);
}
@Override
public String toString() {
return s;
}
}
Java's er noget mere avanceret, men den her skulle vise ideen.