Java-Dateien für PK (2013W) Blatt 7 Aufgabe 5

IntHashtable.java

// Hashtabelle ist Beispiel für die Nutzung von Zufall und Wahrscheinlichkeit

// Hashtabelle ganzer Zahlen
// verwendet verkettete Liste zum Umgang mit Kollisionen
public class IntHashtable {

	public static final int TABSIZE = 1024;                 // Größe der Hashtabelle
	private IntListNode[] tab = new IntListNode[TABSIZE];   // die eigentliche Hashtabelle
	
	// berechne den Hashwert von elem
	private int hash(int elem) {                            // O(1)
		return Math.abs((elem + elem / TABSIZE) % TABSIZE);
	}
	
	// füge elem in die Hashtabelle ein
	public void add(int elem) {                             // O(1)
		int h = hash(elem);
		tab[h] = new IntListNode(elem, tab[h]);
	}
	
	// ist elem in der Hashtabelle?
	public boolean contains(int elem) {                     // maximal O(n); minimal O(1) 
		IntListNode node = tab[hash(elem)];                 // durchschnittlich knapp über O(1) wenn n viel kleiner als TABSIZE
		return node != null && node.contains(elem);         // durchschnittlich nahe O(n) wenn n größer TABSIZE
	}
	
	// entferne ein Vorkommen von elem aus der Hashtabelle
	// keine Veränderung wenn elem nicht in der Hashtabelle ist
	public void remove(int elem) {                          // Aufwand wie contains
		int h = hash(elem);
		if (tab[h] != null) {
			tab[h] = tab[h].remove(elem);
		}
	}
	
	public String toString() {
		String s = null;
		for (int i = 0; i < TABSIZE; i++) {
			if (tab[i] != null) {
				if (s == null) {
					s = tab[i].toString();
				} else {
					s += "," + tab[i];
				}
			}
		}
		return  "[" + s + "]";
	}
	
	// nur für Testzwecke, gehört eigentlich nicht in diese Klasse
	public static void main(String[] args) {
		
		IntHashtable table = new IntHashtable();
		
		table.add(3300);
		table.add(2);
		table.add(55);
		table.add(800000);
		table.add(-12);
		System.out.println(table);
		System.out.println(table.contains(2));
		System.out.println(table.contains(5));
		table.remove(32);
		table.remove(55);
		System.out.println(table);

	}

}

IntListNode.java

// Listenknoten, verwendet nur von IntList und IntHashtable (daher nicht public)
class IntListNode {

	private int elem;          // das eigentliche Listenelement
	private IntListNode next;  // nächster Knoten in der Liste
	
	IntListNode(int e, IntListNode n) {
		elem = e;
		next = n;
	}
	
	// e im Rest der Liste (beginnend mit this) vorhanden?
	// rekursive Suche
//	boolean contains(int e) {
//		return elem == e
//				|| (next != null && next.contains(e));
//	}
	
	// e im Rest der Liste (beginnend mit this) vorhanden?
	// iterative Suche
	boolean contains(int e) {
		IntListNode node = this;
		do {
			if (node.elem == e) {
				return true;
			}
			node = node.next;
		} while (node != null);
		return false;
	}
	
	// entferne e aus Listenrest (beginnend mit this)
	// Rückgabewert ist Listenrest nach dem Entfernen
	// rekursive Variante
//	IntListNode remove (int e) {
//		if (elem == e) {
//			return next;
//		}
//		if (next != null) {
//			next = next.remove(e);
//		}
//		return this;
//	}
	
	// entferne e aus Listenrest (beginnend mit this)
	// Rückgabewert ist Listenrest nach dem Entfernen
	// iterative Variante
	IntListNode remove (int e) {
		if (elem == e) {
			return next;
		}
		IntListNode node = this;
		while (node.next != null) {
			if (node.next.elem == e) {
				node.next = node.next.next;
				return this;
			}
			node = node.next;
		}
		return this;
	}
	
	// rekursive Variante
	public String toString() {
		return elem + (next == null ? "" : "," + next);
	}

	// iterative Variante
//	public String toString() {
//		String s = "" + this.elem;
//		IntListNode node = next;
//		while (node != null) {
//			s += "," + node.elem;
//			node = node.next;
//		}
//		return s;
//	}

	// rekursive Variante
	public boolean equals(Object that) {
		if (that == null || this.getClass() != that.getClass()) {
			return false;
		}
		IntListNode other = (IntListNode)that;
		return this.elem == other.elem
				&& (this.next == null ? other.next == null : this.next.equals(other.next));
	}

	// iterative Variante
//	public boolean equals(Object that) {
//		if (that == null || this.getClass() != that.getClass()) {
//			return false;
//		}
//		IntListNode thisnode = this;
//		IntListNode thatnode = (IntListNode)that;
//		while (thisnode != null && thatnode != null) {
//			if (thisnode.elem != thatnode.elem) {
//				return false;
//			}
//			thisnode = thisnode.next;
//			thatnode = thatnode.next;
//		}
//		return thisnode == thatnode;
//	}
	
	// Listenelemente aufsteigend sortieren
	public void sort() {
		boolean changed;  // hat sich Liste bei letztem Durchlauf geändert?
		
		do {
			changed = false;
			IntListNode lower = this;   // niedrigerer Wert
			IntListNode higher = next;  // höherer Wert
			
			while (higher != null) {
				if (higher.elem < lower.elem ) {
					int help = higher.elem;
					higher.elem = lower.elem;
					lower.elem = help;
					changed = true;
				}
				lower = higher;
				higher = higher.next;
			}
		} while (changed);
	}
	
	// Restliste ausgeben
	void print() {
		System.out.println(elem);
		if (next != null) {
			next.print();
		}
	}
	
	// einfache Übungsaufgabe: iterative Variante von print
	
}