Ich arbeite an einem elektronischen Projekt mit einem Mikrocontroller, der in C programmiert ist.
Ich muss einige IDs und die zugehörigen Informationen in einem Flash-Speicher (SD) speichern. Diese IDs sind 16 Bytes lang, also gibt es 2 ^ 128 mögliche Werte. Obwohl sie 16 Byte sind, werden nur 50000 (eindeutige) Werte verwendet. Es ist physikalisch unmöglich, alle möglichen (2 ^ 128) IDs in einer SD zu speichern.
Ich könnte nur die 50000 verwendeten Werte speichern, aber dann müsste ich alle (im schlimmsten Fall) durchqueren, um den zu finden, den ich brauche. Außerdem müsste für jeden von ihnen ein 16-Byte-Wertevergleich erstellt werden, was ihn ziemlich langsam macht.
Also ich denke, ich würde eine Art von (Hash?) -Funktion benötigen, die die 2 ^ 128 Werte auf 50000 (Karte 16 Bytes bis 2 Bytes) abbildet. Es ist offensichtlich, dass einige der ursprünglichen Werte auf den gleichen Wert / Index abgebildet werden. Die Idee ist, dass, wenn ich eine ID bekomme, ich eine Hash-Funktion verwende, die mir einen Index zwischen 0 und ~ 50000 (0-65535) gibt. Mit diesem Index kann ich direkt auf die SD-Sektoren zugreifen, in denen die ID und die zugehörigen Informationen gespeichert sind. Wie bereits erwähnt, wird sich dieser Index auf eine Speicherposition beziehen, bei der verschiedene IDs koexistieren, da einige IDs auf denselben Indexwert abgebildet werden. Ich würde die richtige ID finden müssen, aber es würde nur ein paar Vergleiche statt der 50000 ursprünglichen kosten.
Jede Idee / Meinung würde wirklich geschätzt werden.
Vielen Dank im Voraus.
Da die ID 16 Byte lang ist, möchte ich wissen, dass sie in einer ASCII-Zeichenkette gespeichert ist, also funktioniert ELFhash vielleicht.
%Vor%wobei M eine Primzahl kleiner als 65536 oder 50000 ist.
Es ist wahrscheinlicher, dass das Präfix vieler ID-Strings identisch ist, weil sie für eine bestimmte Messung stehen. Daher sollten Sie vorsichtiger sein, um Kollisionen zu vermeiden, oder die verknüpfte Liste wird sehr lang sein.
Sure Mat's ist in Ordnung, dies jedoch durch Verwendung eines Primes sollte zu weniger Kollisionen führen, wo uuid[x] == uuid[y] (und x!=y )
Oder diese Version ist noch besser, weil sie Zusammenstöße reduziert, bei denen die xor der ersten 16 Bits und die zweiten 16 Bits übereinstimmen.
%Vor%Ich arbeite an einem elektronischen Projekt mit einem Mikrocontroller, der in C programmiert ist.
Ich muss einige IDs und die zugehörigen Informationen in einem Flash-Speicher (SD) speichern. Diese IDs sind 16 Bytes lang, also gibt es 2 ^ 128 mögliche Werte. Obwohl sie 16 Byte sind, werden nur 50000 (eindeutige) Werte verwendet. Es ist physikalisch unmöglich, alle möglichen (2 ^ 128) IDs in einer SD zu speichern.
Ich könnte nur die 50000 verwendeten Werte speichern, aber dann müsste ich alle (im schlimmsten Fall) durchqueren, um den zu finden, den ich brauche. Außerdem müsste für jeden von ihnen ein 16-Byte-Wertevergleich erstellt werden, was ihn ziemlich langsam macht.
Also ich denke, ich würde eine Art von (Hash?) -Funktion benötigen, die die 2 ^ 128 Werte auf 50000 (Karte 16 Bytes bis 2 Bytes) abbildet. Es ist offensichtlich, dass einige der ursprünglichen Werte auf den gleichen Wert / Index abgebildet werden. Die Idee ist, dass, wenn ich eine ID bekomme, ich eine Hash-Funktion verwende, die mir einen Index zwischen 0 und ~ 50000 (0-65535) gibt. Mit diesem Index kann ich direkt auf die SD-Sektoren zugreifen, in denen die ID und die zugehörigen Informationen gespeichert sind. Wie bereits erwähnt, wird sich dieser Index auf eine Speicherposition beziehen, bei der verschiedene IDs koexistieren, da einige IDs auf denselben Indexwert abgebildet werden. Ich würde die richtige ID finden müssen, aber es würde nur ein paar Vergleiche statt der 50000 ursprünglichen kosten.
Jede Idee / Meinung würde wirklich geschätzt werden.
Vielen Dank im Voraus.
Wenn die Bits in Ihrem 128-Bit-Wert "gleichmäßig verteilt" sind, können Sie einfach Folgendes tun:
%Vor%Es gibt wahrscheinlich andere schlauere Wege, aber diese ist sehr einfach und kann gut genug funktionieren.
Sure Mat's ist in Ordnung, dies jedoch durch Verwendung eines Primes sollte zu weniger Kollisionen führen, wo %code% (und %code% )
%Vor%Oder diese Version ist noch besser, weil sie Zusammenstöße reduziert, bei denen die xor der ersten 16 Bits und die zweiten 16 Bits übereinstimmen.
%Vor%Verwenden Sie einfach 16 MSB der aktuellen ID. Es ist dumm, aber mit Ihren Details wird es funktionieren.
Da die ID 16 Byte lang ist, möchte ich wissen, dass sie in einer ASCII-Zeichenkette gespeichert ist, also funktioniert ELFhash vielleicht.
%Vor%wobei M eine Primzahl kleiner als 65536 oder 50000 ist.
Es ist wahrscheinlicher, dass das Präfix vieler ID-Strings identisch ist, weil sie für eine bestimmte Messung stehen. Daher sollten Sie vorsichtiger sein, um Kollisionen zu vermeiden, oder die verknüpfte Liste wird sehr lang sein.