Minimale perfekte Hashfunktion

[ArniBoy]

Hi Forum,

ich schreibe gerade ein java-Programm, dass eine Bibliothek verwaltet. Diese Bibliothek wird an einem bestimmten Punkt erschaffen, und von ihr wird häufig etwas eingelesen. Das ganze wird später auf relativ kleinen Geräten laufen, sprich, benötigter Platz der Bib und Geschwindigkeit der Suchaufträge wollen stark optimiert werden.
Was mich zu einer minimalen perfekten Hashfunktion brachte; die wäre das totale Optimum für mein Problem. Im Netz findet man leider nur relativ undurchsichtige Implementationsanweisungen (wie der hier. Auch beim 10. mal durchlesen, weiß ich immer noch nicht, wie man son Ding baut.. komische Konstruktordoku -.-)

Also, ist hier zufälligerweise jemand, der schon mal eine minimale perfekte Hashfunktion (wenn sie nicht minimal war.. auch nicht so schlimm ^^) für eine java Hastable gebaut hat, oder weis, wie die Klasse aus dem Link funktioniert?

Gruß,
Arne

 

[XHelp]

Auf welche Daten willst du denn deine Hash-Funktion anwenden? Was genau willst du damit erreichen?
In deinem Link musst du (auf den ersten Blick) die gesamte Menge der Daten vorher wissen.

 

[ArniBoy]

Das tue ich. Die Bibliothek wird nur einmal erstellt, und dann wird nur noch aus ihr gelesen. Key-values sind Strings.

edit: Was ich damit erreichen will ist schnellstmögliches Zugreifen auf die Werte ohne die Hashtable doppelt so groß wie die benutzte Datenmenge machen zu müssen. Speicherplatz ist knapp.

 

[XHelp]

Du willst die Bibliothek auf deinen "kleinen Geräten" komplett gespeichert halten? Wieso nicht auf einen Server auslagern? Definiere überhaupt "relativ kleines Gerät", bist du dir zu 100% sicher, dass es zum Flaschenhals wird?

 

[ArniBoy]

Über Server habe ich nicht nachgedacht.. hört sich gut an, deutlich besser sogar als das ganze immer lokal zu machen.
Okay, aber prinzipiell ist ne perfekte Hashfunktion auch auf dem Server ne feine Sache..

edit: Ich lasse diesen Thread trotzdem mal als ungelöst stehen, vielleicht taucht ja noch jemand auf, der was dazu weiß.

 

[bERt0r]

Warum nimmst du keine ArrayList? Wenn deine Daten sich nicht verändern hast du mit einer ArrayList kürzeren Zugriff auf deine Daten als deine Hashmap und brauchst auch weniger Speicher.
Ausserdem: Speichert eine Hashmap denn die Hashwerte der Keys extra ab? Wird nicht einfach die Position des Elements durch die Hashfunktion berechnet? Habe nicht in die Eingeweide von Java Hashmaps geblickt, käme mir aber seltsam vor.

 

[Empire Phoenix]

Hm ej nach größe kann mand as intelligenter angehen.

Zb anhand des ersten buchstaben erkennen auf welchen serverr die zugehörigen daten sind (db erste hälfte auf server a, rest auf server b). Dann dort die suchanfrage machen. Theoretisch könnte man das auf mehrere hundert Server damit skalieren (Und behält noch die möglichkeit zum schreiben).

Es empfiehlt sich evtl. hierfür auch nen SQL Server zu verwenden, da deren interne Algorithmik sehr fortschrittlich ist.

 

[ArniBoy]

Warum nimmst du keine ArrayList?

Weil ich einen assoziativen Datentyp brauche. Es gibt viele Vergleiche, ob String x vorhanden ist oder nicht, weswegen ich immer mit dem Inhalt selber nach den Einträgen suche, und nicht über Indices. Da Umfang der Bib schon deutlich über 100.000 Einträgen ist habe ich die andere Möglichkeit, einen Baum, auch ausgeschlossen, da dessen Tiefe und Suchdauer pro Eintrag mit mind. 17 immernoch 17 mal höher ist als bei einer Hashsuche.

Ausserdem: Speichert eine Hashmap denn die Hashwerte der Keys extra ab? Wird nicht einfach die Position des Elements durch die Hashfunktion berechnet? Habe nicht in die Eingeweide von Java Hashmaps geblickt, käme mir aber seltsam vor.

Ja, du liegst richtig. Da ich aber nur nach einem key suche, den ich zu dem Zeitpunkt auch verfügbar habe, weiß ich auch seinen Hashwert. Oder habe ich dich falsch verstanden?

Hm ej nach größe kann mand as intelligenter angehen.

Zb anhand des ersten buchstaben erkennen auf welchen serverr die zugehörigen daten sind (db erste hälfte auf server a, rest auf server b). Dann dort die suchanfrage machen. Theoretisch könnte man das auf mehrere hundert Server damit skalieren (Und behält noch die möglichkeit zum schreiben).

Es empfiehlt sich evtl. hierfür auch nen SQL Server zu verwenden, da deren interne Algorithmik sehr fortschrittlich ist.

Sollte ich tatsächlich dazu kommen das ganze als app zu portieren (was der Plan ist) werde ich mit Servern arbeiten. Bin vorher nicht drauf gekommen, war blöd von mir. Aber ich verstehe nicht, warum ich mehrere Server benutzen sollte. Und warum das ganze gegen eine Lagerung in Hashtables spricht. Also, wenn die Suche dadurch verkürzt werden würde, wenn die Bib kleiner wäre, dann klar. Wobei da die günstigste Möglichkeit meiner Meinung nach ein Baum wäre.. aber das gilt ja für ein Hashtable nicht. Da ist die Suchdauer approximiert immer konstant. Und bei einer perfekten Hashfunktion ist sie es auch tatsächlich.

 

[Empire Phoenix]

Guck dir mal die Datenstruktur B-Baum an, wenn du wirklich eine DB selber Programmieren willst. Allerdings kann ich empfehlen eine Db wie HyperSQL oder Derby oder gleich einen richtigen SQL server zu verwenden worauf die einzelnen Programme dann zugreifen. Der Overhead den das Queryparsen im Server verursacht ist minimal verglichen mit dem was du durch intelligente Algorithmen rausholen wirst(zumal man prepared Statements nehmen kann)
Es gibt auch durchaus SQL server die kommerziel kompatible Lizenzen haben.
Bevor du versuchst sowas selber zu programmieren empfehle ich dir sofern du ncoh nie was mit SQL gemacht hast dir das umbedingt anzugucken.


Aber ich verstehe nicht, warum ich mehrere Server benutzen sollte.
-> Dachte an ein high load Szenario, damit kann man die hauptlast auf mehrere server verteilen, da der hauptserver nur den ersten buchstaben der suchanfrage verarbeiten muss und das dann weiterschickt.

 

[bERt0r]

Warum solltest du dann eine Minimale Hashfunktion benötigen, und nicht mit einer normalen HashMap/Hashtable zufrieden sein? Die einfachste Hashfunktion die ich kenne ist % n. Das heisst bei einer Hashmap mit Kapazität n wird der Key mod n gerechnet, und an die "key mod n"-te Stelle im reservierten Speicher kommt der Datensatz.

 

[XHelp]

Ich habe auch noch das Gefühl, dass du die Funktionsweise der Hashmap etwas falsch verstehst. Die Hashfunktion muss nicht zwingend perfekt sein:

public class Tester {
	public static void main(String[] args) {
		System.out.println("Hashcode von Aa: "+"Aa".hashCode());
		System.out.println("Hashcode von BB: "+"BB".hashCode());
		Map<String, Integer> testMap = new HashMap<String, Integer>();
		testMap.put("Aa", 20);
		testMap.put("BB", 42);
		System.out.println("Aa: "+testMap.get("Aa"));
		System.out.println("BB: "+testMap.get("BB"));
	}
}

 

[ArniBoy]

Ich habe auch noch das Gefühl, dass du die Funktionsweise der Hashmap etwas falsch verstehst. Die Hashfunktion muss nicht zwingend perfekt sein:

public class Tester {
	public static void main(String[] args) {
		System.out.println("Hashcode von Aa: "+"Aa".hashCode());
		System.out.println("Hashcode von BB: "+"BB".hashCode());
		Map<String, Integer> testMap = new HashMap<String, Integer>();
		testMap.put("Aa", 20);
		testMap.put("BB", 42);
		System.out.println("Aa: "+testMap.get("Aa"));
		System.out.println("BB: "+testMap.get("BB"));
	}
}

Hab das Beispiel verstanden. Ich weiß, dass sie nicht perfekt sein muss. Mit einer minimalen Hashfunktion braucht die HashMap aber weniger Speicherplatz. Und wenn sie perfekt ist ist sie schneller (In diesem Beispiel sowohl lookup als auch write von "BB" doppelt so schnell =D ). Und da ich die Bedingungen dafür erfüllte, dass eine minimale perfekte erstellt werden kann, wollte ich sie haben.. bzw, am Anfang dachte ich auch noch, dass es relevant für das gelingen des Projekt an sich war; unser Emulator starb immer, weil zu wenig Speicher zur Verfügung stand. Die Application als client zu implementieren löst das Problem, jetzt könnten wir höchstens noch eine offline-Version machen. Und da würde eine dufte Hashfunktion bestimmt ziemlich helfen! ^^

 

[ArniBoy]

Guck dir mal die Datenstruktur B-Baum an, wenn du wirklich eine DB selber Programmieren willst. Allerdings kann ich empfehlen eine Db wie HyperSQL oder Derby oder gleich einen richtigen SQL server zu verwenden worauf die einzelnen Programme dann zugreifen. Der Overhead den das Queryparsen im Server verursacht ist minimal verglichen mit dem was du durch intelligente Algorithmen rausholen wirst(zumal man prepared Statements nehmen kann)
Es gibt auch durchaus SQL server die kommerziel kompatible Lizenzen haben.
Bevor du versuchst sowas selber zu programmieren empfehle ich dir sofern du ncoh nie was mit SQL gemacht hast dir das umbedingt anzugucken.


Aber ich verstehe nicht, warum ich mehrere Server benutzen sollte.
-> Dachte an ein high load Szenario, damit kann man die hauptlast auf mehrere server verteilen, da der hauptserver nur den ersten buchstaben der suchanfrage verarbeiten muss und das dann weiterschickt.

B-Baum: read & write in O(log n)
HashTable: read & write in O(1)

Lese mir SQL grade trotzdem mal durch.. wird langsam eh mal Zeit.

Das mit den mehreren Servern: Wir müssen das Ding erstmal nur vorstellen, sprich, nur ein einziger client existiert ^^ um high-load Szenarien kümmern wir uns wohl erst, wenn wir daran vorbei sind

 

[faetzminator]

[...] In diesem Beispiel sowohl lookup als auch write von "BB" doppelt so schnell =D [...]

HashTable: read & write in O(1)

Schneller als [c]O(1)[/c]? Ist das dann [c]O(4/5)[/c] :bae: ?

 

[Empire Phoenix]

SQL löst auch dein Ram problem ^^
Letzendlich ist Bibliothekverwaltung so ziemlich einer der Zwecke für die Datenbanken ursprünglich mal gedacht waren.

 

[ice-breaker]

Schneller als [c]O(1)[/c]?

[c]O(1)[/c] heisst ja auch nur, dass der Aufwand der Operation konstant ist und von keiner anderen Menge abhängt. Es kann also Implementierungen geben, die auch nur O(1) sind aber schneller als andere Implementierungen.

Eine minimale Hashfunktion zu erstellen ist wirklich sehr viel Arbeit, ich würde da auch eher zu einem perfekt gefüllten B-Baum raten, wenn man den richtig aufbaut, kann man in alle Knoten die maximale Anzahl Elemente packen ohne dass es viele halbvolle Knoten geben sollte, dann sollte das eventuell auch schon effizient genug sein, wir kennen die Anforderung und Menge der Daten nicht.

 

[bERt0r]

Hab das Beispiel verstanden. Ich weiß, dass sie nicht perfekt sein muss. Mit einer minimalen Hashfunktion braucht die HashMap aber weniger Speicherplatz. Und wenn sie perfekt ist ist sie schneller (In diesem Beispiel sowohl lookup als auch write von "BB" doppelt so schnell =D ). Und da ich die Bedingungen dafür erfüllte, dass eine minimale perfekte erstellt werden kann, wollte ich sie haben.. bzw, am Anfang dachte ich auch noch, dass es relevant für das gelingen des Projekt an sich war; unser Emulator starb immer, weil zu wenig Speicher zur Verfügung stand. Die Application als client zu implementieren löst das Problem, jetzt könnten wir höchstens noch eine offline-Version machen. Und da würde eine dufte Hashfunktion bestimmt ziemlich helfen! ^^

Ich glaube da täuschst du dich, die Menge an Speicherplatz die die Daten benötigen hängt nicht von der Hashfunktion ab. Eine minimale, perfekte hashfunktion vermeidet ja nur die Kollisionen, gespeichert werden müssen die Daten aber trotzdem.

 

[faetzminator]

[c]O(1)[/c] heisst ja auch nur, dass der Aufwand der Operation konstant ist und von keiner anderen Menge abhängt. Es kann also Implementierungen geben, die auch nur O(1) sind aber schneller als andere Implementierungen.

Natürlich. Aber eine langsame Implementierung von [c]O(1)[/c] ist wohl immer noch besser als [c]O(log n)[/c] oder was auch immer... Ich würde mir ATM gar keine Gedanken um das machen und zuerst mal schauen, was mit "normalen" Hashs passiert. Viele Entwickler überlegen sich viel zu früh, wo denn was der Flaschenhals sein könnte. @TO: Läuft das Programm denn bereits unoptimiert auf dem Gerät?

 

[ice-breaker]

Ich glaube da täuschst du dich, die Menge an Speicherplatz die die Daten benötigen hängt nicht von der Hashfunktion ab. Eine minimale, perfekte hashfunktion vermeidet ja nur die Kollisionen, gespeichert werden müssen die Daten aber trotzdem.

bei der minimalen perfekten Hashfunktion geht es darum, dass du z.B. nur 50 feste fixxe Schlüssel hast und das auch nur in ein Array der Länge 50 speicherst, weil die Hashfunktion es so optimal abbilden kann.

Natürlich. Aber eine langsame Implementierung von [c]O(1)[/c] ist wohl immer noch besser als [c]O(log n)[/c] oder was auch immer...

natürlich

Ich würde mir ATM gar keine Gedanken um das machen und zuerst mal schauen, was mit "normalen" Hashs passiert. Viele Entwickler überlegen sich viel zu früh, wo denn was der Flaschenhals sein könnte. @TO: Läuft das Programm denn bereits unoptimiert auf dem Gerät?

jup, eventuell hat er aber auch wirklich nur Hardware zur Verfügung bei denen es nur wenige KB Ram hat, da macht sowas dann wirklich einen großen Unterschied.

 

[ArniBoy]

Natürlich. Aber eine langsame Implementierung von [c]O(1)[/c] ist wohl immer noch besser als [c]O(log n)[/c] oder was auch immer... Ich würde mir ATM gar keine Gedanken um das machen und zuerst mal schauen, was mit "normalen" Hashs passiert. Viele Entwickler überlegen sich viel zu früh, wo denn was der Flaschenhals sein könnte. @TO: Läuft das Programm denn bereits unoptimiert auf dem Gerät?

Nein, wir haben das Programm bis jetzt zwar noch nicht auf ein Smartphone gepackt sondern uns mit einem Emulator begnügt, aber der hing sich mittendrin auf, weil der Speicher voll war. Wie gesagt, das ganze als client zu bauen und das programm auf einem Server laufen zu lassen ist bei weitem besser, als das Programm komplett draufzuhauen und dazu zu versuchen es aufwändig abzuspecken. Mit der client Version sind wir zwar noch nicht fertig, aber ich denke, dass das alle Probleme bezüglich der Memory Engpässe klären sollte.

Ich interessiere mich im Moment nur noch für minimale perfekte Hashfunktionen, weil ich das Prinzip interessant finde, und es vielleicht an anderen Stellen sinnvoll zum Einsatz kommen kann.

Eine minimale Hashfunktion zu erstellen ist wirklich sehr viel Arbeit, ich würde da auch eher zu einem perfekt gefüllten B-Baum raten, wenn man den richtig aufbaut, kann man in alle Knoten die maximale Anzahl Elemente packen ohne dass es viele halbvolle Knoten geben sollte, dann sollte das eventuell auch schon effizient genug sein, wir kennen die Anforderung und Menge der Daten nicht.

Mit der Performance bin ich im Moment zufrieden, auf einem normalen Rechner läuft der Algorithmus (normale) Suchaufträge in <0.1 Sekunden ab. Warum würdest du einen B-Baum einer Hashtable vorziehen?

bei der minimalen perfekten Hashfunktion geht es darum, dass du z.B. nur 50 feste fixxe Schlüssel hast und das auch nur in ein Array der Länge 50 speicherst, weil die Hashfunktion es so optimal abbilden kann.

Genau, ein normaler Hashtable ist, je nach Implementierung, immer zu 30% bis 50% leer.

 

[Empire Phoenix]

Da währe ein sinnvoller paging auf die festplattte (selbst geschreiben oder über eine sql) danna ber trotzdem vorteilhaft, da das dann auch noch wenn die bibliothek mal größer wird funktioniert.

 

[bERt0r]

Genau, ein normaler Hashtable ist, je nach Implementierung, immer zu 30% bis 50% leer.

Eben darum musst du dir dann deine eigene Hashmap schreiben, die das besser macht. Da du dich eh nur mehr interessehalber dafür interessierst, es gibt schon einige Wissenschaftliche Artikel die dir da weiterhelfen können. Manches is aber schrecklich mathematisch Minimal Perfect Hash Function - Google Scholar "Minimal Perfect Hash Functions Made Simple" find ich aber interessant, könntest du mal versuchen.

 

[tuttle64]

Im Buch "Effective Java" von Joshua Bloch wird gut beschrieben, was eine "good hash function" ist, nämlich "A good hash function tends to produce unequal hash codes for unequal objects.". Falls erwünscht, kann ich auf konkrete Fragen noch mehr schreiben.