Benutzer:Riemer

Wiki-Quelltext dieser Seite.

<language>Java</language>
<popup name="Klassen-Definitionen">
<code id="4f6ca2b733235">
public Object Elem(int d) {
	int data = d;
	int getKey() {
		return data;
	}
        return this;
}
public Object HashTable(int size) {
	int arraySize = size;
        int steps;

	Object[] hashArray = new Object[arraySize];
	for(i = 0; i < arraySize; i++) {
                hashArray[i] = null;
        }

	void displayTable() {
		for (int i = 0; i < arraySize; i++) {
			if (hashArray[i] != null)
				System.out.print(hashArray[i].getKey() + " ");
			else
				System.out.print("# ");
		}
		System.out.println("");
	}

	int hashFunction(int key) {
		return key % arraySize;
	}

	void insert(elem) {
		steps = 0;
		int key = elem.getKey();
		int hashVal = hashFunction(key);
                int temp = hashVal;

		while (hashArray[hashVal] != null) {
                        steps++;
			hashVal = temp + steps*steps;
			hashVal %= arraySize;
		}
		hashArray[hashVal] = elem;
		System.out.println(steps + " Sondierungen für " + key);
	}

	Object remove(int key) {
                steps = 0;
                tempElem = null;
		int hashVal = hashFunction(key);
                int temp = hashVal;

		while (hashArray[hashVal] != null) {
			if (hashArray[hashVal].getKey() == key) {
                                System.out.println("Sondierungen: " + steps);
                                tempElem = hashArray[hashVal];
				hashArray[hashVal] = null;
                                return tempElem;
			}
                        steps++;
			hashVal = temp + steps*steps;
			hashVal %= arraySize;
		}
                System.out.println("Sondierungen: " + steps);
		return null;
	}

	Object find(int key) {
                steps = 0;
		int hashVal = hashFunction(key);
                int temp = hashVal;

		while (hashArray[hashVal] != null) {
			if (hashArray[hashVal].getKey() == key) {
                                System.out.println("Sondierungen: " + steps);
				return hashArray[hashVal];
                        }
                        steps++;
			hashVal = temp + steps*steps;
			hashVal %= arraySize;
		}
                System.out.println("Sondierungen: " + steps);
		return null;
	}
        return this;
}

void fillHashTable(Object hashTable, int numberOfKeys) {

        for (int i = 0; i < numberOfKeys; i++) {
	        key = (int) (Math.random() * 10 * size);
	        elem = Elem(key);
	        hashTable.insert(elem);
        }
}
</code></popup>
<run id="4f6ca2b73358e">
size = 17;
n = 10;

hashTable = HashTable(size);
fillHashTable(hashTable, n);
hashTable.displayTable();
</run>

<run id="4f74a205a5d00">
size = 17;
n = 10;

hashTable = HashTable(size);
fillHashTable(hashTable, n);

hashTable.displayTable();

key = (int) (Math.random() * 10 * size);
dataItem = hashTable.find(key);

if (dataItem != null) {
	System.out.println(key + " wurde gefunden!");
} else {
	System.out.println(key + " konnte nicht gefunden werden!");
}
</run>

<run id="4f74a7ce5891c">
size = 17;
n = 10;

hashTable = HashTable(size);
fillHashTable(hashTable, n);

hashTable.displayTable();

key = (int) (Math.random() * 10 * size);
dataItem = hashTable.remove(key);

if (dataItem != null) {
	System.out.println(key + " wurde gelöscht!");
} else {
	System.out.println(key + " konnte nicht gelöscht werden!");
}

hashTable.displayTable();
</run>