fast perfekte oder perfekte Hash der Speicheradressen in c

Question

Ich habe eine Liste von Speicheradressen von 0xc0003000 bis 0xc04a0144 gibt es viele Lücken und < 4096 Einträge in der Liste. Es ist zur Kompilierzeit bekannt und ich möchte einen perfekten Hash dafür machen.

Aber nachschlagen perfekt Hashing online gibt mir Informationen, die meisten im Zusammenhang mit Hashing-Strings und sie scheinen nicht gut zu übersetzen.

Um klar zu sein Ich möchte in der Lage sein, die Speicheradresse zur Laufzeit zu erhalten und zu überprüfen, dass es im Hash schnell ist. Momentan verwende ich eine binäre Suche, die im Durchschnitt etwa 8 Schleifen enthält, um die Antwort zu finden.

Irgendwelche Ideen welchen Baum ich bellen sollte?

Answer 1

Hier ist ein Beispiel gperf Programm. Ich habe eine NUL und eine neue Zeile in die Beispieldaten eingefügt, um zu beweisen, dass sie nicht zum Ausfall führen.

%{ 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <inttypes.h> 
#include <arpa/inet.h> 
%} 
%% 
"\xc0\x01\x02\x03" 
"\xc0\xff\xff\xff" 
"\xc0\xff\x00\xff" 
"\xc0\x0a\xff\xff" 
%% 
int main(int argc, const char **argv) 
{ 
    int i; 

    for(i=1;i<argc;++i) { 
     uint32_t addr = ntohl(strtoul(argv[i], 0, 16)); 
     if(in_word_set((char *)&addr, 4)) 
      printf("0x%08"PRIx32" is in the list.\n", htonl(addr)); 
     else 
      printf("0x%08"PRIx32" is not in the list.\n", htonl(addr)); 
    } 
    return 0; 
} 

Speichern als addrs.gperf, kompilieren und zu testen mit

gperf -l addrs.gperf > addrs.c 
gcc addrs.c -o addrs 
./addrs c0000000 c0010203 c0ffffff c00affff c0ff0aff c0ffff00 c0ff00ff