Benutzer:Riemer

Aus ProgrammingWiki
Archivierte Version vom 2012-03-18T15:52:02+00:00. Aktuelle Version
public Object DataItem(int d) {
	private int data = d;

	public int getKey() {
		return data;
	}
}


public Object HashTable() {
	private DataItem[] hashArray;

	private int arraySize;

	// private DataItem bufItem; // for deleted items

	public HashTable(int size) {
		arraySize = size;
		hashArray = new DataItem[arraySize];
		// bufItem = new DataItem(-1); // deleted item key is -1
	}

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

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

	public void insert(DataItem item) {
		int key = item.getKey();
		int hashVal = hashFunction(key); // hash the key
		// until empty cell or -1,
		while (hashArray[hashVal] != null/* && hashArray[hashVal].getKey() != -1 */) {
			++hashVal; // go to next cell
			hashVal %= arraySize; // wraparound if necessary
		}
		hashArray[hashVal] = item; // insert item
	}

	public DataItem delete(int key) {
		int hashVal = hashFunction(key);

		while (hashArray[hashVal] != null) // until empty cell,
		{
			if (hashArray[hashVal].getKey() == key) {
//				DataItem temp = hashArray[hashVal]; // save item
				// hashArray[hashVal] = bufItem; // delete item
				return hashArray[hashVal] = null;
//				return temp;
			}
			++hashVal; // go to next cell
			hashVal %= arraySize; // wraparound if necessary
		}
		return null; // can't find item
	}

	public DataItem find(int key) // find item with key
	{
		int hashVal = hashFunction(key); // hash the key

		while (hashArray[hashVal] != null) // until empty cell,
		{
			if (hashArray[hashVal].getKey() == key)
				return hashArray[hashVal]; // found, return item
			++hashVal; // go to next cell
			hashVal %= arraySize; // wraparound if necessary
		}
		return null; // can't find item
	}
}

DataItem aDataItem;
int aKey, size;

size = 15;
HashTable theHashTable = new HashTable(size);

aKey = 1;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
		
aKey = 3;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
		
aKey = 4;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
		
aKey = 8;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
		
aKey = 9;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
	
aKey = 12;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
		
aKey = 13;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);

theHashTable.displayTable();
		
aKey = 23;
aDataItem = new DataItem(aKey);
theHashTable.insert(aDataItem);
theHashTable.displayTable();

theHashTable.delete(9);
theHashTable.displayTable();
		
aDataItem = theHashTable.find(aKey);
if (aDataItem != null) {
	System.out.println(aKey + " wurde gefunden!");
} else {
	System.out.println(aKey + " wurde nicht gefunden!");
}
Benutzer:Riemer

Suche
