Benutzer:Riemer

Aus ProgrammingWiki

Archivierte Version vom 2012-03-30T09:08:22+00:00. Aktuelle Version

Klassen-Definitionen

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++;
		/*	if (steps > arraySize) {
				System.out.println(key + " konnte nicht eingefügt werden");
				return;
			}*/
			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;
			} else {
			        ++hashVal;
			        hashVal = temp + steps*steps;
			        hashVal %= arraySize;
                        }
                        steps++;
		}
                System.out.println("Sondierungen: " + steps);
		return null;
	}

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

		while (hashArray[hashVal] != null) {
                        steps++;
			if (hashArray[hashVal].getKey() == key) {
                                System.out.println("Sondierungen: " + steps);
				return hashArray[hashVal];
                        } else {
			        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);
        }
}

size = 17;
n = 10;

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

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!");
}

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();

Benutzer:Riemer

Suche