Hashfunktion gesucht

Kellerautomat

Hallo Leute,

Ich suche eine Hashfunktion, die mir ints auf Array-Indizes mapt, mit folgenden Eigenschaften:

Alle Keys (und Values) sind im Vorhinein bekannt
Keys vorgegeben, koennen nicht an das Verfahren angepasst werden
Keine Kollisionen
Moeglichst schnell berechenbar (< 5 Instructions, je weniger desto besser)
Sehr niedrige Anzahl an Keys, meist sogar < 5

Gibt es da irgendwelche Verfahren, wie man so eine Funktion berechnen kann?

Gruesse,
Der Kellerautomat

volkard

Kellerautomat schrieb:

Gibt es da irgendwelche Verfahren, wie man so eine Funktion berechnen kann?

Ich würde mir ein paar Verfahren ausdenken, die mit Parametern arbeiten, die ich bruteforcen kann.

#include <iostream>
#include <array>
using namespace std;

bool isGoodFactor(unsigned int factor,unsigned int (&keys)[5]){
	bool hit[5]={};
	for(auto k:keys){
		unsigned int v=k*factor%15;
		if(v>=5) return false;
		if(hit[v]) return false;
		hit[v]=true;
	}
	return true;
}

int main(){
	unsigned int keys[]={42,4711,0xdeadbeef,73,37};
	unsigned int factor=0;
	do{
//		if(factor%1048576==0) cout<<factor<<'\n';
		if(isGoodFactor(factor,keys))
			cout<<"good factor: "<<factor<<endl;
	}while(++factor!=0);
}

edit:

unsigned int v=__builtin_popcount(k&factor);

Kellerautomat

Sorry, aber ich verstehe so gut wie gar nichts. Koenntest du das etwas weiter ausfuehren?

volkard

Kellerautomat schrieb:

Sorry, aber ich verstehe so gut wie gar nichts. Koenntest du das etwas weiter ausfuehren?

Mal angenommen, die keys sind
{42,4711,0xdeadbeef,73,37}
das Programm sucht eine Zahl factor, die wenn man berechnet
v=k*factor%15
daß die 5 keys auf die Arrayplätze 0 bis 4 abgebildet werden.

Alsgabe des Programms zum Beispiel:

good factor: 547347003

Also v=k*547347003%15 würde die 5 keys auf 5 unterschiedliche Arrayplätze abbilden.

- Alle Keys (und Values) sind im Vorhinein bekannt
Jo. Das habe ich ausgenutzt.

-Keys vorgegeben, koennen nicht an das Verfahren angepasst werden
Ok.

-Keine Kollisionen
Nicht erfüllt, ist ja auch eine Hashfunktion. Aber die 5 vorgegebenen keys kollidieren nicht. Kannst ein Array der Values an den richtigen Plätzen anlegen und schauen, ob an arr[v]==k vorliegt.

-Moeglichst schnell berechenbar (< 5 Instructions, je weniger desto besser)
Sehr niedrige Anzahl an Keys, meist sogar < 5
Jo, k*factor%15 sind recht wenige Instriktionen, v=__builtin_popcount(k&factor) ist auch recht schlank. Aber bei nur 5 Keys könnten 5 if-Verzweigungen doch noch schneller sein. Bei 20 Keys und %23 kriege ich noch Ergebnisse, dort dürfte hashen dann aber schneller als 20 ifs sein.

gperf

Kellerautomat

Warum gerade 15 als Modul? Und was hats mit dem v auf sich, insbesondere dem popcount?

gperf funktioniert soweit ich das gesehen habe nur mit Strings.

volkard

Kellerautomat schrieb:

Warum gerade 15 als Modul?

Willkür. Mit 15 war noch ein wenig Platz nach oben, wenns mal mehr keys sein sollten. Gerade Zahlen als Modul scheinen nicht so gut zu sein.

Kellerautomat schrieb:

Und was hats mit dem v auf sich,

v ist der errechnete Array-Index.

Kellerautomat schrieb:

insbesondere dem popcount?

Nur, um zur Abwechslung was anderes als % zu nehmen, um das Ergebnis kleiner zu machen. Und Du kannst Dir weitere so Funktionen einfallen lassen.

volkard schrieb:

Gerade Zahlen als Modul scheinen nicht so gut zu sein.

Doch damit wurden schon sehr gute Ergebnisse erziehlt.