Für Knobler: Perfekte Hash-Funktion für Matrizen gesucht

Hi Leute,

ich bin auf der suche nach einer "perfekten" Hash-Funktion.
Die Hashfunktion soll eine bestimmte Position in einer Beliebig
großen Matrix eindeutig durch eine Zahl bestimmen. Z.B. könnte
die Zahl 385 die Position der Zeile 17 und der spalte 9 sein.

Genauer: der Schlüssel sind zwei INT variablen, die die Zeile
und die Spalte darsetllen sollen. Ich will also sozusagen allen
Positionen in der Matrix eine bestimmte Nummer geben (index des
späteren Hash-Vektors).

Aber VORSICHT! In der Hash-Tabelle sollen später nur Einträge/Werte
stehen, die NICHT 0 sind (ich will vermeiden, dass viel Platz mit "0"
Einträgen verschwendet wird, denn die gibt es in meinen Matrizen oft)

Ich hoffe ich habe nichts vergessen.
Vielleicht hat ja jemand Lust zu knobeln.

Vielen Dank
atata

Soweit bin ich schon selbst gekommen

int hash(int zeile, int spalte){
     return _______;
}

volkard

atata schrieb:

int hash(int zeile, int spalte){
     return _______;
}

guter anfang. ne gute wahl ist oft, mit ner toll irrationalen zahl zu plutimizieren.

size_t hash(size_t zeile, size_t spalte)
{
     //sicherastellen, daß size_t 32 bit hat
     size_t const GOLDEN=2654435769;//evtl primzahl in der nähe suchen
        //das hier ist schlicht 2^32 geteilt durch (sqrt(5)+1)/2, 
        //sozusagen der irrationalesten zahl
     return zeile*GOLDEN+spalte;
}

fast gut. die häufungen, weil leute gerne diagonalen schreiben, sind schonmal (meistens) weg.
hab jetzt noch probleme mit dem unverschlüsselten "+spalte". schreibt jemand ne spalte voll und die matrix ist so breit wie die hashtable, dann haben wir ein böses problem.

return (zeile*GOLDEN+spalte)*GOLDEN;

so, dem würde ich mich schon anvertrauen. sehe aber probleme.
a) zwei multiplikationen sind nicht unbedingt eine leckere geschwindigkeit. evtl ist zeile16+spalte (keine multiplikation) bereits ausreichend. kannst das nur über ausmessen rausfinden.
b) return zeileGOLDEN+spalte; hat ein problem, wenn GOLDEN%tablesize==0 oder ==1 oder ==-1. dann wäre zeile ignoriert (schlimmster fall) oder es wäre wieder das diagonalenproblem da.
welche hasttable-größen kommen überhaupt vor? ach, eigentlich haste hier die wahl, welche zu nehmen, die besonders gut mit GOLDEN harminieren bzw du suchst dir gute größen aus und suchst danach nen wert statt GOLDEN, der gut funktioniert.

ich würde als hashtablegrößen nen klassiker nehmen, wie z.B. bei 101 anfangen (unterer primzahlenzwilling) und immer, wenn die table zu klein wird (z.B. bei füllstand>80%) ungefähr verdoppeln. die fertige verdopplungsreihe in ein array rein und benutzen. evtl die aus <hashmap> klauen. und erstmal davon ausgehen, daß GOLDEN keine probleme damit hat. falls doch, statt GOLDEN einfach ne andere zahl nehmen.

Hi

ich hab da grad was nicht ganz kapiert, soll eine hashfunktion umkehrbar sein? oder nicht? für mich sind hashfunktionen im normalfall nicht umkehrbar. D.h. das mehrere Objekte den gleichen Hashwert generieren können.

wenn ich das jetzt richtig errate:
du versuchst eine optimierte speichermöglichkeit für matritzen zu finden, indem du alles was 0 ist nicht speicherst. diene Hashfunktion soll dabei aus Spalte und Zeile einen key für ne Hashtabel liefern in der du dann den Wertn ablegtst. Schluss folgerung, die Hashfunktion muss umkehrbar sein, um damit überhaupt weiterzurechnen.

momentanes problem ist. du versuchst 2 Int werte auf einen Int wert abzubilden. was nicht umkehrbar ist. ( in bestimmten grenzfällen ) somit musst du einschränkungen machen. MaxSpalte * MaxZeile darf die MaxInterger nicht überschreiten.

wir haben mal was ganz gemeines mit abzählung in numerik gemacht was sich auch auf matritzen anwenden lässt nur krig ich grad nicht mehr die formel zusammen.

muss nach mal knobeln. sah in ewa so aus

X->
     0  1  2  3  4  

Y 0  0  1  3  6 10
  1  2  4  7 11 
| 2  5  8 12 
V 3  9 13
  4 14

gruss Termite

so hier mal die verwendete formel für den abzählreim

änderungen: zeilen und spalten numerirung fängt mit 1 an nicht mit 0
Zellennumer ist um eins erhöht.

$(\sum_{n=0}^{x+y-2} n )+ y$

X->
     1  2  3  4  5  

Y 1  1  2  4  7 11
  2  3  5  8 12 
| 3  6  9 13 
V 4 10 14
  5 15

gruss Termite

Vielen Dank für den Support!
hat mir weiter geholfen!
bis bald
atata