Probleme mit eigener Hashmap

[vogelstrauss]

Hallo zusammen,

Ich bin momentan dabei, mir eine eigene Hashmap zu schreiben. Es funktioniert auch alles so weit. Um etwas in die Hashmap einzutragen, übergebe ich als Schlüssel einen String und Value ein Int. Wenn ich jetzt allerdings beispielsweise 28 Schlüssel eintrage, werden nicht alle 28 eingetragen sondern nur z.B. 25. Ich hab keine Ahnung woran das liegen könnte. Schon eingetragene Schlüssel werden nicht nochmal eingetragen und eigentlich sollten auch keine Schlüssel überschrieben werden. Vielleicht blickt von euch einer durch.

public class Hashmap{

	private Entry[] entry;
	private int index, counter = 0;

	public Hashmap(){
		init(100);
	}

	public Hashmap(int size){
		init(size);
	}

	private void init(int size){
		entry = new Entry[size];
		for (int i = 0; i < entry.length; i++){
			entry[i] = new Entry();
		}

	}

	private int hashing(String str){
		String alphNum = null, strNum = null, codeStr = null;
		int code = 0;
		char comp;
		char[] alphabet = {'a','b','c','d','e','f','g','h','i','j','k',
				'l','m','n','o','p','q','r','s','t','u','v','w','x','y','z',' ','ä','ü','ö'};
		str = str.trim().toLowerCase();

		for (int i=0; i < str.length(); i++){
			for (int j=0; j < alphabet.length; j++){
				comp = str.charAt(i);
				if ( comp == alphabet[j]){
					alphNum = Integer.toString(j+1);
				}
				strNum = Integer.toString(i+1);
				codeStr = alphNum + strNum + alphNum;

			}
			code = code +  Integer.parseInt(codeStr);

		}
		return code;
	}

	public void put(String key, int v) {
	
			System.out.println(counter + "Länge: " + entry.length);
		  if (counter == entry.length){
		    Entry[] entryClone = new Entry[entry.length * 2]; 
		    for(int i=0; i<entryClone.length; i++){
		    	entryClone[i] = new Entry();
		    }
		    

		    System.arraycopy(entry, 0, entryClone, 0, entry.length);

		    entry = new Entry[entryClone.length];
		  
		    System.arraycopy(entryClone, 0, entry, 0, entryClone.length);
		    
		  }
		
		if (!containsKey(key)){
			entry[index].setKey(key);
			entry[index].setValue(v);
			entry[index].setReserved(true);
			counter += 1;
		}
//		showEntries();

	}

	public int get(String key){
		if (!containsKey(key)){
			return entry[index].getValue();
		}
		return -1;
	}

	public boolean containsKey(String key){
		key = key.trim().toLowerCase();
		index = hashing(key) % entry.length;
		while (entry[index].isReserved() && key.equals(entry[index].getKey())){
			index += 1 % (entry.length); 
		}
		if (key.equals(entry[index].getKey()) && entry[index].isReserved()) return true;
		else return false;
	}

	public void showEntries(){
		int count=0;
		for (int i=0; i < entry.length; i++){
			if((entry[i].getKey()) != null){
				System.out.println(entry[i].getKey() + "\t" + get(entry[i].getKey()));
				count++;
			}

		}
		System.out.println(count + " Entries");
	}

public static void main(String[] args){
		Hashmap map = new Hashmap();

		
		String[] test = {"Emperor Maredudds entrance hall", "Lady Aderyns dining room", 
				"Emperor Maredudds entrance hall", "Couple Kendalls tee room",
						"Emperor Maredudds entrance hall", "Countess Morwennas concert hall",
				"Lady Aderyns dining room", "Lord Bronwyns bedroom",
				"Lord Bronwyns bedroom", "Princess Cathryns dressing room",
				"Princess Cathryns dressing room", "Count Dylans training room",
				"Princess Cathryns dressing room", "Sir Gwythyrs treasure room",
				"Count Dylans training room", "Marchioness Emlyns kittchen",
				"Count Dylans training room", "Duke Gruffydds hall",
				"Marchioness Emlyns kittchen", "Count Dylans training room",
				"Marchioness Emlyns kittchen", "Earl Folands tower",
				"Earl Folands tower", "Lord Glendowers smoking room",
				"Earl Folands tower", "Lady Gwendolines ball room",
				"Lord Glendowers smoking room", "Lady Gwendolines ball room",
				"Lady Gwendolines ball room", "Duke Gruffydds hall",
				"Duke Gruffydds hall", "Marchioness Emlyns kittchen",
				"Sovereign Baroness Heulwens bath room", "Baroness Hyless store",
				"Baroness Hyless store", "Grand Duke Illtyds hunt room",
				"Baroness Hyless store", "Countess Ithels shrine",
				"Grand Duke Illtyds hunt room", "Sovereign Baroness Heulwens bath room",
				"Grand Duke Illtyds hunt room", "Countess Ithels shrine",
				"Couple Kendalls tee room", "Viscountess Lleucus rest room",
				"Couple Kendalls tee room", "Queen Mairwens dancing hall",
				"Couple Kendalls tee room", "Countess Morwennas concert hall",
				"Viscountess Lleucus rest room", "Archduke Llywellyn armoury",
				"Archduke Llywellyn armoury", "Sovereign Baroness Heulwens bath room",
				"Sovereign Baroness Heulwens bath room","Archduke Llywellyn armoury",
				"Archduke Llywellyn armoury", "Queen Mairwens dancing hall",
				"Countess Morwennas concert hall", "Couple Kendalls tee room",
				"Countess Morwennas concert hall", "Viceroy Neifions library",
				"Countess Morwennas concert hall", "Lady Sawyls dancing saloon",
				"Viceroy Neifions library", "Lady Olwyns gallery",
				"Olwyns gallery", "Viceroy Neifions library",
				"Lady Olwyns gallery", "Knight Pryces arsenal",
				"Knight Pryces arsenal", "Lady Olwyns gallery",
				"Knight Pryces arsenal", "Viscount Rhydderchs torture chamber",
				"Viscount Rhydderchs torture chamber", "Duchess Rhiannon sleeping room",
				"Lady Sawyls dancing saloon", "Vicereine Tiwlips sweets corner",
				"Vicereine Tiwlips sweets corner", "Lady Sawyls dancing saloon",
				"Vicereine Tiwlips sweets corner", "King Trevors assembly hall",
				"Vicereine Tiwlips sweets corner", "Esquire Yoraths hiding place",
				"King Trevors assembly hall", "Electoral prince Vaughans stable",
				"King Trevors assembly hall", "Lordliness Wynfors trophy chamber",
				"Electoral prince Vaughans stable", "Lordliness Wynfors trophy chamber",};
		
		for (int i= 0; i<test.length; i++){
			map.put(test[i], i);
		}

		map.showEntries();


	}




}

Die Klasse Entry:

public class Entry {
	
	private String key = null;
	private int value = -1;
	private boolean reserved = false;
	
	public void setValue(int v){
		this.value = v;
	}
	
	public void setKey(String k){
		this.key = k;
		
	}
	
	public String getKey(){
		
		return key;
	}
	
	public int getValue(){
		
		return value;
	}
	
	public boolean isReserved(){
		
		return this.reserved;
	}
	
	public void setReserved(boolean b){
		reserved = b;
		
	}

}

Ich bin dankbar für jeden Hinweis.

vogelstrauss

 

[SlaterB]

String liefert doch schon einen hashCode(),
den kannst du doch zumindest testweise verwenden, um deine Hash-Methode als Fehlerursache zu identifizieren

private int hashing(String str){
reutrn str.hashCode();
}

--------

in jedem Falle fehlt eine main-Methode mit den 28 Strings, wenn ich nicht ganz blind bin,
die zum Ausprobieren wäre doch deutlich besser als rein in der Theorie den Code anzuschauen

 

[vogelstrauss]

ja, dass mir String ein hashcode() bereitstellt ist mir klar. Ich wollte nur was angepasstes und eigenes. Werde es gleich mal ausprobieren, ob damit der Fehler auch auftritt.

Habe oben die main() noch nachträglich hinzugefügt.

 

[SlaterB]

containsKey() errechnet den index:
> index = hashing(key) % entry.length;
wie bei Hashfunktionen üblich, ist der aber nicht eindeutig,
sowohl "King Trevors assembly hall" als auch "Lady Gwendolines ball room" führen zu Index 78,
ungeprüft überschreibt dann einer von beiden den anderen älteren Eintrag, am Ende fehlt einer (insgesamt 4x)

zu jedem Index muss eine Liste von Einträgen vorhanden sein,
oder zumindest muss man an einen Entry per Referenz noch weitere Entries ranhängen können, quasi eine LinkedList,

bei get/ contains muss dann die ganze Liste zum Index geprüft werden,
Kollisionen gehören zu so einem Verfahren dazu

------

dass nur durch den Aufruf von containsKey() als Seiteneffekt das Klassenattribut index gesetzt wird,
ist fast noch ein größerer Schnitzer

 

[vogelstrauss]

Ok, Danke.
dein deispiel wäre dann ein Hashing mit Verkettung. Ich wollte es mit Openadressing versuchen. containesKey() sucht auch einen freien Platz, wenn der vom Hashcode generierte Platz nicht mehr frei ist und schreibt es an den nächsten freien Platz. Die Variable index sollte dann auf den Platz zeigen.


>76 freier Platz
>77 freier Platz
>78 King Trevors assembly hall > kein Platz mehr für "Lady Gwendolines ball room" also schreibs an den nächsten freien Platz.
>79 Lady Gwendolines ball room

 

[SlaterB]

ok, hab nicht so genau geschaut,
die while-Bedingung geht nur dann einen Platz weiter, wenn die Keys übereinstimmen, das ist gerade falsch,
wenn key.equals(entry.key) dann bist du fertig, dann ist das der richtige Index,

-----

index += 1 % (entry.length);
wird so nicht funktionieren,
teste das dochmal
int x = 99;
x += 2 % 100

------

wenn die Map ganz voll ist, droht eine Endlosschleife, da wird aber wohl vorher schon die Map vergrößert

 

[vogelstrauss]

Ok, danke. Man muss wohl index = (index+1) % entry.length schreiben.

die while-Bedingung geht nur dann einen Platz weiter, wenn die Keys übereinstimmen, das ist gerade falsch,
wenn key.equals(entry.key) dann bist du fertig, dann ist das der richtige Index,

Also kann ich es nur über meine isReserved-Methode überprüfen, ob der Platz belegt ist?
Ich stehe gerade ein wenig auf dem Schlauch. Verstehe aber das Problem. Die Keys können also den gleichen Hashcode haben aber sich nicht gleichen.

 

[SlaterB]

&& !key.equals(entry[index].getKey())
könnte schon eine Besserung sein gegenüber
&& key.equals(entry[index].getKey())

 

[vogelstrauss]

Ja, klar. Wenn der jetzige Schlüssel ungleich mit dem eingetragenen Schlüssel an der Stelle index ist, dann erhöhe den index um 1 und überprüfe den nächsten Platz.
Allerdings sagt mir meine Hashmap jetzt, dass alle eingetragen Schlüssel nicht vorhanden wären. Versteh ich nicht

 

[SlaterB]

das zweite equals im if danach hast du hoffentlich nicht auch verändert?
bau doch paar System.out.println ein, um zu verstehen, was genau verglichen wird

 

[vogelstrauss]

So, ich habs gelöst. Anstatt equals() equalsIgnoreCase() und das Ding läuft.
Danke dir vielmals für die Hilfe.