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); } }
size = 17; n = 10; hashTable = HashTable(size); fillHashTable(hashTable, n); hashTable.displayTable();
ausführen
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();