mikrocontroller.net

Forum: Compiler & IDEs Einfache Hashsumme


Autor: Christian S. (vuurwerk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hi,

ich bin derzeit auf der Suche nach einem Algorithmus zum Erstellen einer 
einfachen Hashsumme. Dabei sollte die Summe eine Ganzzahl sein (32bit). 
Ich möchte diese gern verwenden um Indizes zu erstellen zum einfachen 
wiederauffinden von Datensätzen in einer Datei (Quasi wie das indizieren 
in einer Datenbanken). Jetzt sind mir natürlich Algorithmen wie SHA1, 
MD5 usw. gut bekannt, allerdings sind die, so denke ich zumindestens, 
viel zu komplex für das was ich erreichen will. Ich möchte aus einem 
String/Byte-Array eben diesen Index generieren. Das ganze müsste jedoch 
auf einem 32-bit Toshiba CMOS mit 40MhZ und 2MB Flash laufen.

Kann mir dazu jemand etwas empfehlen? Links oder Namen der 
entsprechenden Algorithmen reichen mir vollkommen aus, den Rest wie 
Implementierung etc. mache ich dann selbst. Ich hoffe nur das gerade 
hier im Forum jemand effiziente Algorithmen kennt womit man auf solchen 
Controllern arbeiten kann.

Vielen Dank schonmal
Christian

Autor: Christian S. (vuurwerk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ok, mir fiel gerade ein das man das ja ggf. ganz einfach lösen könnte. 
Da die Bezeichnung aus der ich einen Index generieren möchte nur aus 
ASCII-Zeichen besteht und die Zeichenkette nie länger als 25 Zeichen 
besteht, könnte man den ASCII-Wert multipliziert mit dem Index in der 
Zeichenkette (jedoch beginnend bei 1) aufsummieren und man erhält eine 
eindeutige Zahl. Worst-Case bei einer Zeichenkette bestehend nur aus 'z' 
und einer länge von 25, läge der Index somit bei 991250 was noch 
gemütlich in ein 32bit integer passt.

Sollte jemand die Erfahrung gemacht haben das mein Denkansatz nicht 
funktioniert der möge sich bitte melden, Danke!

Grüße
Christian

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christian S. schrieb:
> den ASCII-Wert multipliziert mit dem Index in der
> Zeichenkette (jedoch beginnend bei 1) aufsummieren und man erhält eine
> eindeutige Zahl.
Eindeutig ist die nicht:
'z' = 1 * 122 = 122
und
' -' = 1 * 32 + 2 * 45 = 122

Autor: Huch (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Tschuldigung, wenn das harsch klingt: Da braucht man keine Erfahrung 
sondern nur Mathematik.

Nehmen wir es sind Gross-, Kleinbuchstaben und Ziffern verwendet. Das 
gäbe 27+27+10 verschieden Zeichen, also 64 zu deren Kodierung 7 Bit 
benötigt werden. Bei 25 solcher Zeichen sind das 175 Bit die nötig sind.

Nach welchem Verfahren Du auch rechnest: Jedes, das weniger als 175 Bit 
Summe ergibt, ergibt auf gar keinen Fall eine eindeutige Summe . Das 
geht garnicht.

Kannst Du auch sorum denken. Wenn ein String nur dadurch eindeutig 
darstellbar ist, dass 8-Bit für das Zeichen, sukzessive mit 2^0, 2^8, 
2^16, 2^24 etc. multipliziert werden, wie kann dann eine Multiplikation 
mit 1, 2, 3, 4, 5 etc, auch eine eindeutige Darstellung ergeben?

Autor: Christian S. (vuurwerk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Christian S. schrieb:
>> den ASCII-Wert multipliziert mit dem Index in der
>> Zeichenkette (jedoch beginnend bei 1) aufsummieren und man erhält eine
>> eindeutige Zahl.
> Eindeutig ist die nicht:
>
> 'z' = 1 * 122 = 122
> 
> und
>
> ' -' = 1 * 32 + 2 * 45 = 122
> 

Ok, da hast Du recht, dann müsste man an der Stelle noch mit der Länge 
arbeiten, Summe mit länge des Strings multiplizieren bspw.?

-- Christian

Autor: Manuel Kasten (draradech)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Weder dein Algorithmus noch eine andere Hashfunktion ergeben eine 
eindeutige Zuordnung.

Bei dir sind Kollisionen sogar sehr einfach zu erzeugen (auch bei 
gleichlangen Strings):
"BB", "DA" = 198
"BBBB", "BDBA", "FBBA" = 660

Also musst du überlegen wie du mit Kollisionen umgehst. Je besser die 
Hashfunktion, um so seltener sind Kollisionen, vermeidbar sind sie aber 
prinzipbedingt nie.

Den Prozessor kenne ich zwar nicht, aber er klingt erstmal locker 
schnell genug für eine der üblichen Hashfunktionen.

Gruß,
    Manuel

Autor: Christian S. (vuurwerk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Huch schrieb:
> Tschuldigung, wenn das harsch klingt: Da braucht man keine Erfahrung
> sondern nur Mathematik.
>
> Nehmen wir es sind Gross-, Kleinbuchstaben und Ziffern verwendet. Das
> gäbe 27+27+10 verschieden Zeichen, also 64 zu deren Kodierung 7 Bit
> benötigt werden. Bei 25 solcher Zeichen sind das 175 Bit die nötig sind.
>
> Nach welchem Verfahren Du auch rechnest: Jedes, das weniger als 175 Bit
> Summe ergibt, ergibt auf gar keinen Fall eine eindeutige Summe . Das
> geht garnicht.
>
> Kannst Du auch sorum denken. Wenn ein String nur dadurch eindeutig
> darstellbar ist, dass 8-Bit für das Zeichen, sukzessive mit 2^0, 2^8,
> 2^16, 2^24 etc. multipliziert werden, wie kann dann eine Multiplikation
> mit 1, 2, 3, 4, 5 etc, auch eine eindeutige Darstellung ergeben?

Ok, von der Seite habe ich das noch nicht betrachtet. Ich fand meinen 
Denkansatz auch nicht wirklich ausgereift aber meine Beispiel-Rechnungen 
hatten funktioniert :)

Was haltet Ihr von Adler-32? Schneller als CRC32 ist auch recht kompakt.

-- Christian

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christian S. schrieb:

> Ok, da hast Du recht, dann müsste man an der Stelle noch mit der Länge
> arbeiten, Summe mit länge des Strings multiplizieren bspw.?

Oder das tun, was man beim Hashen immer tun muss:
Eine Kollisionsstrategie entwickeln.

Eine einfache Strategie ist es zb:
Hsahcode ausrechnen.
Datensatz von dort lesen.

a) Ist es der gewünschte?
Wenn ja -> fertig
Wenn nein -> nächsten Datensatz holen
     Ist er leer?
     Wenn ja, dann gibt es den Suchbegriff nicht
     Wenn nein weiter bei a)


Wie du allerdings einen Hashcode als Index in eine Datei nehmen willst, 
noch dazu mit 32 Bit, ist mir nicht ganz geheuer.


Vielleicht solltest du dir überlegen, was du mit dem Hashcode überhaupt 
machen willst, ehe du jetzt Verfahren erfindest.
Wenn es nur darum geht, einen schnelle Variante von "ist es der 
gewünschte" zu haben, dann ist es auch nicht weiter schlimm wenn der 
Code nicht eindeutig ist. Du kannst deinen Hashcode sowieso maximal als 
Vortest nehmen. Wenn der Hashcode eine Übereinstimmung anzeigt, musst du 
dann sowieso immer noch den kompletten Vergleich machen um festzustellen 
ob es auch wirklich der richtige ist. Dein Hashcode ist also ein 
abweisender Vortest. Wenn er sagt, dass es keine Übereinstimmung im 
Hashcode gibt, dann kann es auch nicht der richtige Datensatz sein. Im 
anderen Fall könnte er es sein, aber nix genaues weiß man nicht, ehe man 
nicht den ausfürlichen Test gemacht hat.


(Das ist nämlich ein häufig gemachter Denkfehler: Da ein Hashcode 
prinzipbedingt nicht eindeutig sein kann, darf man sich auch nicht 
darauf verlassen, dass ein übereinstimmender Hashcode auch 
übereinstimmende Daten bedeutet.)

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Kollisionen sind ja auch nicht böse.

Du musst für deinen Anwendungsfall entscheiden, wie viele Kollisionen am 
effizientesten sind. Wenn sämtliche Eingabeworte kollidieren und 
dasselbe Code(Hash)wort liefern, ist das in der Praxis genauso 
ineffizient, wie wenn kein Wort kollidiert und du dafür eine Tabelle mit 
4 Millionen Einträgen brauchst, von denen 2/3 leer sind.

Irgendwo dazwischen liegt die Wahrheit :-)
Karl-heinz Buchegger hat schon eine gängige Mechanik angesprochen: Per 
Hash (der bewusst Kollisionen liefert) in eine Tabelle von Listen 
greifen.

Autor: Christian S. (vuurwerk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> Vielleicht solltest du dir überlegen, was du mit dem Hashcode überhaupt
> machen willst, ehe du jetzt Verfahren erfindest.

Meine Idee war es eigentlich meine Datensätze die ich zwischenspeichern 
muss (in meinem Fall ein Scanner mit proprietären System) zu indizieren 
um sie später schneller wiederfinden zu können. Beim Schlüssel handelt 
es sich um einen max. 25 Zeichen langen String. Dieser String ist 
eindeutig da wie gesagt Schlüssel. Jetzt wird der Barcode gescannt und 
ich bekomme diesen max. 25 Zeichen langen String. Um nun den passenden 
Datensatz dazu zu finden (mit weiteren Infos wie Bezeichnungen etc.) 
Wollte ich nun ein Array aufbauen wo der erzeugte index ein index in 
einem Array mit relativen Dateipositionen ist. Wenn ich dann in der 
Datei an die Dateiposition springe und meinen Datensatz auslese habe ich 
meinen Datensatz gefunden. Wenne es keine Position dafür im Index-Array 
gibt dann gibt es auch nicht diesen Datensatz.

Ich weiß das ist alles recht primitiv aber für den Fall wo ich es 
benötige wäre es eine gängige Alternative. Statt einem linearen Array 
könnte man auch noch über einen einfachen Baum nachdenken aber dazu 
müsste ich den Baum erst implementieren und deswegen erschien mir die 
"Lösung", mit dem linearen Array aus Dateipositionen dessen index der 
index/hash des Schlüssels vom Datensatz ist, am einfachsten.

Jetzt wo ich das aber gerade mit dem Baum schrieb scheint es mir fast 
schon die bessere Lösung zu sein ... hmmm

-- Christian

Autor: Sven P. (haku) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Selbst-ausbalancierende Binärbäume sind bereits erfunden :-)

Schau mal:
- AVL-Baum
- Rot-Schwarz-Baum
- GNU libavl

Autor: Christian S. (vuurwerk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Sven P. schrieb:
> Selbst-ausbalancierende Binärbäume sind bereits erfunden :-)
>
> Schau mal:
> - AVL-Baum
> - Rot-Schwarz-Baum
> - GNU libavl

Jap, das weiß ich schon, mir ging es um die Implementierung. Eine 
Fremd-Lib wird auf dem CMOS nicht/kaum gehen, selbst der Compiler von 
Toshiba bietet gerade mal die grundlegensde Standard-Bibliothek an, und 
das noch nicht mal vollständig.

-- Christian

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christian S. schrieb:

> ich bekomme diesen max. 25 Zeichen langen String. Um nun den passenden
> Datensatz dazu zu finden (mit weiteren Infos wie Bezeichnungen etc.)
> Wollte ich nun ein Array aufbauen wo der erzeugte index ein index in
> einem Array mit relativen Dateipositionen ist.

Überleg einfach mal wie groß dein Array sein muss, wenn du 32 Bit als 
Index haben willst und jeder Index prinzipiell möglich ist :-)

Aber abgesehen davon:
Ja du kannst das schon so machen.
Nur brauchst du eben eine Kollisionsstrategie.
Die einfachst mögliche:
Beim Einfügen eines neuen Satzes: Wenn der Slot schon belegt ist, dann
  einfach den nächsten freien Slot nehmen
Beim Suchen: Über den Index aufsuchen und wenn das der falsche war,
  dann mit dem nächsten Eintrag im Array weitermachen und so quasi
  von der Hashposition aus linear weitersuchen, bis man entweder
    den gesuchten Satz hat
    oder eben feststeht, dass er nicht drinnen ist, weil der Index-
    eintrag (der Slot) leer ist.


Das ist eine gängige Kollisionsstrategie. Es gibt auch noch andere. Aber 
für den Hausgebrauch reicht das schon.

Du musst dich einfach nur von der Vorstellung trennen, dass der Hashcode 
eindeutig ist. Alles andere folgt dann daraus.


Sowas ist doch schnell implementiert und war früher gang und gäbe als 
die Festplatten und Magnetbänder noch das Laufen lernten. Bei IBM hies 
sowas eine "ISAM-Datei" wenn ich mich recht erinnere (wenn auch die 
Kollisionsstrategie eine andere war)

Autor: U.R. Schmitt (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Mach das was Karl Heinz sagt, er hat das perfekt erklärt.
Einzig hinzuzufügen wäre, daß das natürlich nur solange effizient 
funktioniert wie dein Index(Array) deutlich größer ist als die maximale 
Anzahl von Einträgen, damit es bei der Kollisionserkennung genügend 
leere Einträge gibt.
Ich würde einen max. Füllgrad von 0,2 bis 0,4 vorschlagen.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
U.R. Schmitt schrieb:

> Ich würde einen max. Füllgrad von 0,2 bis 0,4 vorschlagen.

Klingt nicht schlecht.

Was man auch nicht vergessen darf: Die Datei (und damit der Index) muss 
reorganisiert werden, wenn die Größe des Index höher gestellt wird. D.h. 
da muss man ev. ein Hilfsprogramm vorsehen.

Was noch nicht erwähnt wurde: Der Index wird selbstverständlich mit in 
die Datei gespeichert und beim Öffnen der Datei von dort in den Speicher 
geholt.


Das alles klingt jetzt vielleicht furchtbar kompliziert. Es ist aber im 
Grunde genommen furchtbar einfach. Muss es auch sein, sonst hätten es 
die Mainframes aus dem letzten Jahrhundert nicht gepackt :-)

Autor: sebastians (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ändert sich die Liste der zu durchsuchenden Schlüssel zur Laufzeit?
Wenn nicht, dann ist es evtl. einfacher, statt dem Baum ein sortiertes 
Array mit binärer Suche zu durchsuchen.

http://en.wikipedia.org/wiki/Bsearch

Autor: Christian S. (vuurwerk)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sebastians schrieb:
> Ändert sich die Liste der zu durchsuchenden Schlüssel zur Laufzeit?
> Wenn nicht, dann ist es evtl. einfacher, statt dem Baum ein sortiertes
> Array mit binärer Suche zu durchsuchen.
>
> http://en.wikipedia.org/wiki/Bsearch

Ja das muss ich vorsehen das weitere Datensätze hinzukommen. Daher 
tendiere ich momentan zu einem binären Baum.

-- Christian

Autor: Michael Fischer (mifi)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo Christian,

sagt Dir Constant Data Base (CDB) was?
Schau mal hier:

http://cr.yp.to/cdb.html

Vielleicht könnte das auch was für Dich sein.

Gruß,
Michael

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christian S. schrieb:
> sebastians schrieb:
>> Ändert sich die Liste der zu durchsuchenden Schlüssel zur Laufzeit?
>> Wenn nicht, dann ist es evtl. einfacher, statt dem Baum ein sortiertes
>> Array mit binärer Suche zu durchsuchen.
>>
>> http://en.wikipedia.org/wiki/Bsearch
>
> Ja das muss ich vorsehen das weitere Datensätze hinzukommen.

Über wieviele Datensätze reden wir eigentlich?

> Daher
> tendiere ich momentan zu einem binären Baum.

Kann man auch machen. Ist verwaltungstechnisch aber auch nicht 
unaufwändiger.

Haben dich die Kollisionen abgeschreckt?
Mach da jetzt kein Totschlagargument draus! Wenn deine Hashfunktion 
nicht allzu primitiv ist, dann ist das in der Praxis überhaupt kein 
Problem. Du brauchst auch keine 'ausgefuchste' Hash-Funktion. Schau dir 
deine Schlüssel an. Die ersten 4 Bytes nehmen, das ganze Modulo der 
Tabellenlänge - fertig ist eine einfache Hashfunktion. Solange sich 
deine Schlüssel in den ersten 4 Buchstaben unterscheiden, wirst du nicht 
allzuviele Kollisionen bekommen und wenn, sind sie einfach zu behandeln.
Und wenn deine Artikelnummern in den ersten 4 Buchstaben alle gleich 
sind, dann nimmt man eben andere. Zb eine Kombination aus den ersten 2 
und den letzten 2. Irgendwas. Hauptsache die Chancen stehen gut, dass 
nicht allzuviele Artikel mit diesem Buchstabenextrakt zu gleichen 
Ergebnissen führen.

Das ist nichts, woraus man jetzt ein Drama machen müsste.

Und eine Verwaltung der Records auf dem File kriegst du damit gratis 
noch mit dazu.

Autor: Simon Huwyler (simi)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hashfunktionen sind durchaus eindeutig. Egal, wie oft Du den Hash 
machst, es kommt immer dasselbe raus.

Eineindeutig hingegen sind sie nicht, weil eben der umgekehrte Weg nicht 
mehr funktioniert. Ein Hash-Code kann von unzähligen Eingaben erzeugt 
worden sein.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.