Hi,
Einen kleinen Hinweis kann ich mir aber nicht verkneifen: dem Rechner
kann es nicht passieren, das er irgendwo etwas vergißt oder sich
vertippt. Der entscheidende Vorteil eines Compilers übrigens.
Mag ja sein, aber der Code-erzeugende Algorithmus kann fehlerhaft sein.
Es heißt ja eigentlich, das man seine Eltern ehren solle?
[...] Falls mich meine Erinnerung da nicht getäuscht hat und Du an die
Ausgabe rankommst, [...]
Ich wuesste nicht wie. Ich koennte mal in der Fachbereichsbibliothek
nachschauen, aber ich bezweifele es ehrlich gesagt.
Ist auch nicht gar so wichtig, wer liest denn schon die hintendran gelistete Literatur? Doch nur die Autoren und auch nur die Liste, ob sie denn auch brav alle vorkommen. Hätte mich auch nur mal interessiert, ob ich richtig liege.
Die Hashfunktion selber habe ich gefunden, da sie mit passender Quellangabe an der einen oder anderen Stelle verbraten wurde (Google.de spuckte als erstes Ghostscript aus):
Ist ein bunt durchmischter Bytehaufen (genauer: eine zufällige Permutation der Werte von 0-255), der einem Schieberegister als Seed dient. Die Leute von Alladin behaupten, das das folgendes Array das Originale wäre:
uint8_t hash_seed[256]={
1,87,49,12,176,178,102,166,121,193,6,84,249,230,44,163,
14,197,213,181,161,85,218,80,64,239,24,226,236,142,38,200,
110,177,104,103,141,253,255,50,77,101,81,18,45,96,31,222,
25,107,190,70,86,237,240,34,72,242,20,214,244,227,149,235,
97,234,57,22,60,250,82,175,208,5,127,199,111,62,135,248,
174,169,211,58,66,154,106,195,245,171,17,187,182,179,0,243,
132,56,148,75,128,133,158,100,130,126,91,13,153,246,216,219,
119,68,223,78,83,88,201,99,122,11,92,32,136,114,52,10,
138,30,48,183,156,35,61,26,143,74,251,94,129,162,63,152,
170,7,115,167,241,206,3,150,55,59,151,220,90,53,23,131,
125,173,15,238,79,95,89,16,105,137,225,224,217,160,37,123,
118,73,2,157,46,116,9,145,134,228,207,212,202,215,69,229,
27,188,67,124,168,252,42,4,29,108,21,247,19,205,39,203,
233,40,186,147,198,192,155,33,164,191,98,204,165,180,117,76,
140,36,210,172,41,54,159,8,185,232,113,196,231,47,146,120,
51,65,28,144,254,221,93,189,194,139,112,43,71,109,184,209
};
Hashfunktion selber ist ein simples Schieberegister. Daran gäbe es einiges zu mäkeln, ich gebe es hier aber unverändert wieder (zwar Typen aufgelöst, aber nicht passend gemacht):
uint32_t pearson_hash(const unsigned char *s, size_t length){
uint32_t hash = 0;
size_t n = length;
while(--n > 0){
hash = (hash << 8) |
hash_seed[(unsigned char)hash ^ *s++];
}
return hash;
}
Wenn die Permutationen des Seedarrays echt(!) zufällig sind, erzeugt jede solcher Permutationen eine gleichwertige Hashfunktion. Die Qualität dürfte sich dabei im einheitlichem Rahmen bewegen: nicht gerade spitze, aber auch nicht wirklich schlecht. Wäre evt interessant für Kollisionsbehandlung mittels weiterer Hashfunktionen aber auch - und sogar vor allem für Bloomfilter [Bloom1970]. Eine schmählich vernachlässigte Erfindung. Siehe auch http://www.cs.wisc.edu/~cao/papers/summary-cache/node8.html ff. für eine kurze Übersicht.
[...] könntest Du mir den Artikel ja mal zukommen lassen. Nein, sowas
würde unter Privatkopie laufen und ist immer noch legal.
Ja, das weiss ich :)
Du warst ja auch nicht wirklich gemeint, aber bei der heutzutage herrschenden künstlichen Hysterie auf dem Gebiet dachte ich mir: schreib's lieber nochmal dran, man weiß ja nie wer mitliest.
so short
Christoph Zurnieden
Bibligraphie
{Bloom1970} Burton Bloom.
Space/time trade-offs in hash coding with allowable errors.
Communications of ACM, pages 13(7):422-426, July 1970