algorytm Hash w C do 16 map bajt wartości do 2 bajt wartości

Question

pracuję nad projektem elektronicznym z mikroprocesorem, który jest zaprogramowany w C

muszę przechowywać niektóre identyfikatory i towarzyszące mu informacje pamięć flash (SD). Te ID mają długość 16 bajtów, więc są 2^128 możliwych wartości. Chociaż mają 16 bajtów, zostanie użytych tylko 50000 (unikalnych) wartości. Jest fizycznie niemożliwe, aby zapisać wszystkie możliwe (2^128) identyfikatory w SD.

Mógłbym przechowywać tylko 50000 użytych wartości, ale wtedy musiałbym przejść wszystkie (w najgorszym) z nich, aby znaleźć to, czego potrzebuję. Poza tym należałoby obliczyć 16-bajtowe porównanie wartości dla każdego z nich, co sprawia, że ​​jest dość powolny.

Więc myślę, że potrzebowałbym jakiejś funkcji (hash?), Która odwzorowuje wartości 2^128 na 50000 (mapa 16 bajtów na 2 bajty). Jest oczywiste, że niektóre z pierwotnych wartości będą odwzorowywać tę samą wartość/indeks. Chodzi o to, że kiedy otrzymam identyfikator, stosuję funkcję skrótu, która daje mi indeks od 0 do ~ 50000 (0-65535). Dzięki temu indeksowi mogę uzyskać bezpośredni dostęp do sektora (-ów) SD, w którym przechowywany jest identyfikator i powiązane z nim informacje. Jak już wspomniałem, indeks ten będzie odnosił się do pozycji pamięci, w której różne identyfikatory będą współistnieć ze względu na różne identyfikatory przypisywane do tej samej wartości indeksu. Musiałbym znaleźć poprawny identyfikator, ale kosztowałoby to tylko kilka porównań zamiast 50000 oryginalnych.

Każdy pomysł/opinia byłaby naprawdę doceniana.

Z góry dziękuję.

Answer 1

Assumign bitów w swojej wartości 128-bitowego „równomiernie rozłożone”, można po prostu zrobić coś takiego:

uint32_t uuid[4]; 

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    hash ^= (uuid[i] & 0xffff)^(uuid[i] >> 16); 
} 

Istnieją zapewne inne, bardziej sprytne sposoby, ale ten jest bardzo prosty, a może działać wystarczająco dobrze.

Answer 2

Po prostu użyj 16 MSB rzeczywistego identyfikatora. To głupie, ale z twoimi danymi to zadziała.

Answer 3

Jasne Mat jest w porządku, to jednak poprzez zastosowanie sile powinno skutkować mniej kolizji, gdzie uuid[x] == uuid[y] (i x!=y)

uint32_t uuid[4]; 

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    // hash *= 31; //next line does this, note 31 is a prime 
    hash = (hash << 5) - hash; 
    hash += (uuid[i] & 0xffff)^(uuid[i] >> 16); 
} 

Albo ta wersja jest jeszcze lepsza, ponieważ zmniejsza starć gdzie XOR pierwsze 16 bitów i drugie 16 bitów pasują do siebie.

uint16_t hash = 0; 
for(i = 0; i < 4; i++) 
{ 
    hash = (hash << 5) - hash; //(*=31) 
    hash += uuid[i] & 0xffff; 
    hash = (hash << 5) - hash; //(*=31) 
    hash += uuid[i] >> 16; 
} 

Answer 4

jako identyfikator ma długość 16 bajtów, ja guees który jest przechowywany w ciągu znaków ASCII, więc ELFhash chyba działa.

int ELFhash(char *key) { 
    unsigned long h = 0; 
    while(*key) { 
     h = (h << 4) + *key++; 
     unsigned long g = h & 0xf0000000L; 
     if (g) h ^= g >> 24; 
     h &= -g; 
    } 
    return h & M; 
} 

gdzie M jest liczbą pierwszą mniejszy niż 65536 lub 50000.

Jest bardziej prawdopodobne, że przedrostek wielu ciągów ID są takie same, ponieważ stanowią one dla określonego meaaing, więc powinno być bardziej ostrożny, aby zapobiec kolizjom lub lista linków będzie bardzo długa.