Assoziative Datenstrukturen:

public interface Assoc {
String put(String k, String v);
String get(String k); //gets v
boolean containsKey(String k);
boolean containsValue(String v);
}

public interface Map {
String put(String key, String value);
String get(String key);
String remove(String key);
boolean containsKey(String key);
boolean containsValue(String value);
Collection keys();
Collection values();
int size();
}

Implementierung

public class SimpleAssoc {
private int top; //index of top elem in array
private String[] ks = new String [8];
private String[] vs = new String [8];
private int find(String s, String[] a) {
int i = 0;
//linear search
if (s == null){
while (i < top &&	!(null == a[i]))
i++;
return i;
} else {
while (i < top &&	!(s.equals(a[i])))
i++;
return i;
}
}
public String put(String k, String v) {
int i = find(k, ks); //find index of k in ks
//double size
if (i == top && ++top == ks.length) {
String[] nks = new String[(top * 2)];
String[] nvs = new String[(top * 2)];
for (int j = 0; j < i; j++) {
nks[j] = ks[j]; nvs[j] = vs[j];
}
ks = nks; vs = nvs;
}
ks[i] = k;
//actual operation
String old = vs[i];
vs[i] = v;
return old;
}
public String remove(String k) {
int i = find(k, ks);
String old = vs[i];
if (i < top) {
//last array entry [top] = null to prevent index out of bound
ks[i] = ks[--top]; //fill hole
ks[top] = null;
vs[i] = vs[top];
vs[top] = null;
}
return old;
}
public String get(String k) {
return vs[find(k, ks)];
}
public boolean containsKey(String k) {
return find(k, ks) < top;
}
public boolean containsValue(String v) {
return find(v, vs) < top;
}
public int size() { return top; }
}

HashTab

public class HashTab implements Assoc {
private String[] ks = new String[65];
private String[] vs = new String[65];
private int count = 0;public HashTab() {
clear();
}//search ks
private int find(String k) {
if (k == null)
return ks.length - 1; // ks[ks.length-1] = null// linear search
int i = k.hashCode() & (ks.length - 2);
while (ks[i] != null && !ks[i].equals(k)) { //if not there because of collision
i = (i + 1) & (ks.length - 2);
}
return i;
}public String put(String k, String v) {
if (k == null) {
return null;
}int i = find(k);
String old = vs[i];
vs[i] = v;if (ks[i] == null) {
ks[i] = k;
// doubles size
if (++count >= 0.75 * ks.length) {
String[] oks = ks, ovs = vs;
ks = new String[(oks.length * 2) - 1];
vs = new String[(oks.length * 2) - 1];
for (int j = 0; j < oks.length; j++) {
if (oks[j] != null) {
ks[i = find(oks[j])] = oks[j];
vs[i] = ovs[j];
}
}
}
}
return old;
}public String get(String k) {
return vs[find(k)];
}public boolean containsKey(String k) {
return ks[find(k)] != null;
}public boolean containsValue(String v) {
// linear search in vs[]
for (int i = 0; i < vs.length - 1; i++) {
if (v == null ? (ks[i] != v && vs[i] == v) : v.equals(vs[i]))
return true;
}
return false;
}public String toString() {
String s = "";
for (int i = 0; i < ks.length - 1; i++) {
if (ks[i] != null)
s += (s.isEmpty() ? "(" : ", (") + ks[i] + ", " + vs[i] + ")";
}
return "{" + s + "}";
}public boolean equals ( Object o) {
if (this == o) { return true; }
if (o == null || o.getClass() != HashTab.class)
return false ;
HashTab t = ( HashTab )o;
if (count != t.count) return false;
for (int i = 0; i < ks. length - 1; i++) {
if (ks[i] != null && (vs[i] == null ? {
!t.containsKey(ks[i]) || t.get(ks[i]) != null : !vs[i].equals(t.get(ks[i]))))
return false;
}
}
return true;
}public int hashCode() {
int h = count;
for (int i = 0; i < ks.length - 1; i++) {
if (ks[i] != null) {
h += ks[i].hashCode();
if (vs[i] != null)
h += vs[i].hashCode();
}
}
return h;
}public void clear() {
ks = new String[65];
vs = new String[65];
count = 0;
}public String remove(String k) {
int i = find(k);
String result = vs[i];
if (i < ks.length - 1) {
ks[i] = vs[i] = null;
count--;
for (i = (i + 1) & (ks.length - 2); ks[i] != null; i = (i + 1) & (ks.length - 2)) {
String ki = ks[i], vi = vs[i];
ks[i] = vs[i] = null;
count--;
put(ki, vi);
}
}
return result;
}public int size() {
return count;
}public Collection keys() {
return new KeySet(this);
}public int keyArray(String[] keys) {
int i = 0, j = -1;
while (i < keys.length && ++j < ks.length - 1) {
if (ks[j] != null) {
keys[i++] = ks[j];
}
}
return i;
}public Iterator keyIterator() {
return new HashTabKeyIter(ks);
}
}public Collection values() { ... }
}

Iteration über Keys

public class KeySet implements Collection {
private HashTab tab;public KeySet(HashTab t) {
tab = t;
}public void add(String element) {
if (!tab.containsKey(element))
tab.put(element, null);
}public int contains(String e) {
return tab.containsKey(e) ? 1 : 0;
}public int removeAll(String e) {
if (tab.containsKey(e)) {
tab.remove(e);
return 1;
}
return 0;
}public void clear() {
tab.clear();
}public int size() {
return tab.size();
}public String[] toArray() {
String[] keys = new String[size()];
tab.keyArray(keys);
return keys;
}public Iterator iterator() {
return tab.keyIterator();
}public String toString() {
String s = "";
for (String e : this)
s += s.equals("") ? e : ", " + e;
return "{" + s + "}";
}public boolean equals ( Object o) { ... }public int hashCode () { ... }
}

public class HashTabKeyIter implements Iterator {
private String[] ks;
private int i;public HashTabKeyIter(String[] a) {
ks = a;
}public boolean hasNext() {
for (int j = i; j < ks.length - 1; j++) {
if (ks[j] != null) {
return true;
}
}
return false;
}public String next() {
while (i < ks.length - 1 && ks[i] == null)
i++;
return ks[i++];
}
}

Java Library

Die meisten eher ineffzient

HashMap<K,V>

TreeMap<K,V>