Perfektes Hashing / perfekte Hashfunktion

[Professor Chaos]

Hallo allerseits,

kennt von euch jemand eine bereits vorhandene, freie Implementierung von perfekten Hashfunktionen?
Ich finde es ein wenig seltsam, dass ich nichts dazu im Netz finden kann. Außerdem möchte ich das nicht selbst schreiben...

Falls also jemand bereits eine Implementierung dafür kennt, hätte ich gerne einen Link.
Ein Java-Package wäre natürlich noch schöner, konnte in der API aber nichts finden.

 

[0x7F800000]

http://java.sun.com/j2se/1.4.2/docs/api/java/lang/Object.html#hashCode() ???:L

 

[Professor Chaos]

Ich kann mir ehrlich gesagt kaum vorstellen, dass dieser Aufruf tatsächlich einen perfekten Hashwert liefert. Schließlich muss zur Konstruktion einer perfekten Hashfunktion die endliche Schlüsselmenge angegeben werden, was hier nicht der Fall nicht.
In der API steht, dass der int-Wert der Adresse des Objekts als Hashwert zurückgeben wird. Dann scheint der Hashwert auch eindeuitg zu sein, okay. Ich nehme aber an, dass diese Variante dann deutlich ineffizienter ist, als die Hashfunktion im Vorfeld vorzuberechnen (wie das bei perfektem Hashing üblich ist).

 

[Professor Chaos]

Ich merke gerade, dass es sich tatsächlich nicht um "richtiges" perfektes Hashing handelt.
Gerade, WEIL die Adresse des Objektes zurückgegeben wird, handelt es sich ja nur um perfektes Hashing bezüglich eines Objekts, aber nicht bezüglich eines abtrakten Kriteriums.

Beispiel:

	public static void main(String[] args) {
		HashSet<String> set1 = new HashSet<String>();
		set.add("a");
		System.out.println(set1.hashCode()); // liefert 97
		
		HashSet<String> set2 = new HashSet<String>();
		set.add("a");
		System.out.println(set2.hashCode()); // liefert 0
	}

Natürlich soll der Hashcode von set1 und set2 identisch sein, da auch equals() true liefert. Der HashCode beider Mengen ist aber unterschiedlich.

Meine Frage bleibt daher bestehen:
Kennt jemand eine freie Implementierung perfekter Hashfunktionen?

 

[Ark]

1. Kaum eine Hash-Funktion ist perfekt (und wenn doch, ist aus dem Wert das Original wieder rekonstruierbar).
2. Eine Hash-Funktion kann niemals perfekt sein, wenn die Anzahl aller möglichen Eingaben größer ist als die Anzahl an möglichen Ausgaben.
3. Hash-Funktionen sind im Allgemeinen nicht dazu gedacht, perfekt zu sein.
4. Welche Hash-Funktion möglichst günstige Streuwerte liefert, hängt von der Beschaffung der Eingaben ab.
5. Lass dir von Eclipse eine Hash-Funktion generieren.

Ark

 

[Professor Chaos]

1. Kaum eine Hash-Funktion ist perfekt (und wenn doch, ist aus dem Wert das Original wieder rekonstruierbar).

"Kaum" ist formal falsch, da Hashfunktionen von Hand konstruiert sind und man (wahrcheinlich) eine bijektive Abbildung zwischen der Menge aller perfekten und der Menge aller nicht perfekten Hashfunktionen konstruieren kann. Es gibt also gleich viele.^^
Und der positive(!) Nebeneffekt, dass jede perfekte Hashfunktion bijektiv ist, ist in meiner Anwendung nicht von Belang.

2. Eine Hash-Funktion kann niemals perfekt sein, wenn die Anzahl aller möglichen Eingaben größer ist als die Anzahl an möglichen Ausgaben.

Ich weiß. Mit anderen Worten: Die Schlüsselmenge sollte eine Teilmenge des Universums sein. Dies erfüllt mein Szenario.

3. Hash-Funktionen sind im Allgemeinen nicht dazu gedacht, perfekt zu sein.

Naja... Hashfunktionen sind dazu da, in annähernd O(1) an ein Datum zu kommen. Ob nun perfektes Hashing zwingend notwendig ist oder nicht ist dann natürlich szenarioabhängig. Aber ich stimmte dir zu, in fast ausnahmslos allen Szenarien ist perfektes Hashing nicht notwendig.

4. Welche Hash-Funktion möglichst günstige Streuwerte liefert, hängt von der Beschaffung der Eingaben ab.
5. Lass dir von Eclipse eine Hash-Funktion generieren.

4 und 5 sind für mich irrelevant, da ich auf perfektes Hashing angewiesen bin.

Danke für die Hinweise, aber ich komme um perfektes Hashing nicht herum. Werde es wohl von Hand implementieren müssen.
Dennoch bin ich um weitere Hinweise nach freiem Code dankbar!

 

[Marco13]

Solange du nicht sagst, WELCHE Objekte gehasht werden sollen, kann man die Frage m.E. nicht beantworten. Es gibt (potentiell und theoritisch) unendlich viele zu hashende Objekte, und nur endlich viele Hashwerte. Etwas vereinfacht und plakativ gesagt wäre eine perfekte Hash-Funktion ja eine Funktion, die jedes Objekt auf einen eindeutigen index abbildet.....

 

[Professor Chaos]

Solange du nicht sagst, WELCHE Objekte gehasht werden sollen, kann man die Frage m.E. nicht beantworten.

Tut mir leid, ich ging vom einfachsten Fall aus und fäschlicher Weise davon, dass das klar sei.
Gegeben: fixe Schlüsselmenge S, die beliebige Teilmenge eines endlichen Universums U ist, welches aus natürlichen Zahlen von 0 bis N besteht.
Gesucht: für dieses Szenario eine perfekte HashFunktion.

Leider habe ich mittlerweile erkannt, dass eine solche perfekte HashFunktion für meine Zwecke doch nicht ausreichend ist. Ich muss mir wohl weitere Gedanken machen, wie ich mein Problem löse.

Falls es aber noch andere geben sollte, die eine perfekte HashFunktion benötigen, bitte ich dennoch darum, eine Referenz zu posten, falls eine solche existiert.

 

[Marco13]

Oh-ho :shock: Wenn "perfekt" nicht ausreicht, hast du glaubich ein Problem :wink:

Bei den "natürlichen Zahlen von 0 bis N" handelt es sich (hoffentlich) um ints, zwischen 0 und ca. 2Mrd. Aber irgendwie kapier' ich das Problem glaubich immernoch nicht ???:L Wenn du schon eine Menge von (eindeutigen) Zahlen/IDs hast, dann SIND das ja schon Hashwerte... Die könnten mit
index = ID % tableSize
auf den Index gemappt werden, den sie in der HashTable (bzw. dem dahinterliegenden Array) haben, aber das wäre nicht eindeutig... Hm... Ich weiß nicht, ob das jetzt ein rein akademisches Problem ist, wenn es genau DARUM geht: Ein Mathematik-Fachidiot würde jetzt vielleicht sagen, dass man so eine Hashfuktion "perfekt" machen kann, indem man eine Hashtabelle verwendet, die die schon vorhandene, eindeutige ID auf einen simplen Index mappt.... ( :autsch: ???:L )

 

[Professor Chaos]

Oh-ho :shock: Wenn "perfekt" nicht ausreicht, hast du glaubich ein Problem :wink:

lol.
Nein, ich dachte zunächst, dass in meinem Szenario tatsächlich das Problem "gegeben S, Teilmenge von U, gesucht h()" vorläge, habe dann aber bemerkt, dass mein Problem leicht anders aussieht.

Bei den "natürlichen Zahlen von 0 bis N" handelt es sich (hoffentlich) um ints, zwischen 0 und ca. 2Mrd.

Nun, es handelt sich zumindest um eine Zahl von 0 bis zu einer natürlichen Zahl, die den Integer-Bereich nicht überschreitet.

Aber irgendwie kapier' ich das Problem glaubich immernoch nicht ???:L

Okay, ich fürchte, dass ich nochmal das Konzept des perfekten Hashings erklären muss.
Da ich dafür aber nochmals recht lange benötige (damit das auch eindeutig und unmissverständlich ist), möchte ich mir heute dafür keine Zeit mehr nehmen. Ich werde wahrscheinlich morgen (aber definitiv irgendwann demnächst) nochmals etwas dazu schreiben. Versprochen!

 

[Marco13]

Grob-Intuitiv heißt das ja (wenn ich mich an's 3. Semester noch richtig erinnere) in erster Linie, dass keine zwei Keys den gleichen Hashwert bekommen. Darüber, dass die Hashtable (bzw. der Array) weniger als Integer.MAX_VALUE Einträge haben sollte, wird dabei ja nichts gesagt :wink:

 

[Professor Chaos]

Besser spät als nie.
Ich wollte zwar "morgen" (also vor knapp drei Wochen) antworten, vergaß es dann aber.^^

Grob-Intuitiv heißt das ja (wenn ich mich an's 3. Semester noch richtig erinnere) in erster Linie, dass keine zwei Keys den gleichen Hashwert bekommen.

Jap, genau das macht perektes Hashing.


Bevor ich die nächsten Antworten geben kann, benötigen wir einige Definitionen. Ich habe diese bereits genannt, aber egal...
Sei U={0,...,N-1} das Universum, also die Menge aller Schlüssel, die rein theoretisch vorkommen könnten. Es gilt |U|=N, N endlich.
Sei S Teilmenge von U mit |S|=n die Schlüsselmenge, d.h. S ist die Menge aller Schlüssel, die tatsächlich vorhanden ist. Diese ist vor Beginn der Konstruktion der Hashfunktion bekannt.

Darüber, dass die Hashtable (bzw. der Array) weniger als Integer.MAX_VALUE Einträge haben sollte, wird dabei ja nichts gesagt :wink:

Nein, aber es gibt perfekte Hashfunktionen, die es ermöglichen, eine Hashtabelle zu verwenden, die lediglich O(n) Platz benötigt, statt exakt N.

Aber irgendwie kapier' ich das Problem glaubich immernoch nicht[. Denn wenn] du schon eine Menge von (eindeutigen) Zahlen/IDs hast, dann SIND das ja schon Hashwerte... Die könnten mit
index = ID % tableSize auf den Index gemappt werden, den sie in der HashTable (bzw. dem dahinterliegenden Array) haben, aber das wäre nicht eindeutig...

GENAU DAS ist der Punkt!! Diese Werte wären nicht eindeutig! Und damit wäre diese intuitive Hashfunktion nicht perfekt. Und damit wäre kein O(1)-Zugriff mehr möglich.

Hm... Ich weiß nicht, ob das jetzt ein rein akademisches Problem ist, wenn es genau DARUM geht: Ein Mathematik-Fachidiot würde jetzt vielleicht sagen, dass man so eine Hashfuktion "perfekt" machen kann, indem man eine Hashtabelle verwendet, die die schon vorhandene, eindeutige ID auf einen simplen Index mappt.... ( )

Naja, falls du eine Java-HashTable verwendest, löst du das Problem ja nicht. Schließlich verwendet eine HashTable eine Hashfunktion um das Mapping zwischen Bild und Urbild vorzunehmen. Und diese Funktion ist im Allg. nicht perfekt. Also haben wir noch immer keine perfekte Hashfunktion.

Die intuitivste Variante wäre, ein Array anzulegen mit N Einträgen. Jeder Eintrag x aus diesen Array ist genau dann 1, falls x aus S und 0 sonst. Damit hätte man eine perfekte Hashfunktion. Diese Vorgehensweise hat aber einen Speicherbedarf von exkat N. Wie oben bereits gesagt ist es möglich eine Hashfunktion zu konstruieren, die mit O(n) Speicherbedarf auskommt. Und dies kann szenarioabhängig eine gigantische Einsparung sein.

Wie bereits gesagt bin ich nicht mehr auf perfektes Hashing angewiesen, dennoch lasse ich diesen Thread als ungelöst stehen, da nach wie vor keine freie Implementierung von perfekten Hashfunktionen genannt wurde.

 

[Perfekte HaxXxfunktion]

Hallo,

ich habe mir die Bibliothek zwar nicht angeschaut, aber in dem Dokument http://www.itu.dk/courses/SPT/E2008/wads07.pdf wird auf eine freie Bibliothek (LGPL), die im Rahmen des Papers entstanden ist, verwiesen. Sie ist allerdings in C.

Ich selber habe mal das Verfahren "Hash and Displace" in C implementiert. Perfekte Hashfunktionen sind echt was feines ) Leider haben sie ein Image-Problem - viele wissen nicht mal, dass es sowas gibt ("Perfekte Hashfunktion? Sowas geht doch gar nicht..."). Aber ich kanns nur empfehlen!

Viele Grüße,
Johannes