[C] Hash Table: roba che si mangia?

[gurutech]

Ciao,
dato un URL in ingresso ad un programma devo confrontarlo per una corrispondenza in una luuuunga lista di URL.
da quello che ho capito la funzionalità che mi serve è implementata da qualcosa chiamato Hash Table.
http://en.wikipedia.org/wiki/Hash_table
Mi date qualche riferimento per documentarmi meglio, magari con del codice di esempio? tenete presente che io so programmare solo in C (eccetto per i linguaggi di scripting) e che comunque il resto del codice l'ho già scritto in C.

cosa ne pensate di queste implementazioni?
http://www.ipd.bth.se/ska/sim_home/libghthash.html
http://cmph.sourceforge.net/
http://uthash.sourceforge.net/userguide.html

grazie

[cionci]

Per corrispondenza intendi uguaglianza ?
IMHO fai prima a calcolarti un hash di ogni url ed a salvarti questo hash insieme all'url. Dopo quello che ti serve è solo un'indicizzazione degli hash. Per calcolare l'hash puoi usare md5.

Un md5 è qualcosa di questo tipo: 5308a79f5e652edba5be84644ee14b09

Ad esempio: con un indice a due livelli.
Immagina di avere una lista di strutture:

struct url_list {
    char *url;
    struct url_list *next;
};

typedef struct url_list * url_list_pointer;

url_list_pointer hash_table[256][256]; /* da inzializzare a NULL */

Per indicizzare la tabella usa i primi 2 byte della stringa md5 (sono in esadecimale).
Quindi:

int get_hex_value_from_char(char c)
{
    return (c < '9' && c > '0') ? c - '0' : (c < 'f' && c > 'a') ? c - 'a' + 10 : 0;
}

int row_index = get_hex_value_from_char(md5_string[0]) * 16 + get_hex_value_from_char(md5_string[1]);

int column_index = get_hex_value_from_char(md5_string[2]) * 16 + get_hex_value_from_char(md5_string[3]);

hash_table[row_index][column_index] conterrà la lista di tutti gli url che hanno gli stessi primi due byte dell'hash !!!

Grazie al md5 gli url si andranno a distribuire uniformemente su tutta la tabella. Ovviamente dovrai pensare anche a come inserire un url nella lista

Una volta che accedi ad una lista della tabella, se l'elemento contiene NULL allora non ci sono match, se contiene una lista valida allora devi fare un confronto fra le stringhe in tutta la lista, ma grazie alla distribuzione quasi uniforme il numero di confronti sarà mediamente di NUMERO_DI_URL / 2^16.

Se hai un numero di url molto maggiore di 2^16...che so...molto maggiore di 2^24 allora ti conviene ampliare la tabella, ad esempio andando a lavorare su 2^12 bit per indice (3 cifre esadecimali per indice). In questo modo arrivi tranquillamente a gestire 2^32 url facendo un numero di confronti fra stringhe massimo pari a 2^8
In alternativa c'è anche la possibilità di aumentare il numero di livelli dell'indicizzazione

[gurutech]

Inizialmente avevo pensato di usare MD5 oppure SHA1, calcolare un hash della URL e metterlo in un DB tipo sqlite. Il programma una volta online deve solo leggere dal DB non scrivere. il punto è che avrò circa 10^6 URL da controllare in tempo reale per emettere un verdetto "si puoi navigare" / "no no puoi navigare". Poi però leggendo qua:

Originariamente inviato da http://en.wikipedia.org/wiki/Hash_table

[...]
Choosing a good hash function
[...]
Simplicity and speed are readily measured objectively (by number of lines of code and CPU benchmarks, for example), but strength is a more slippery concept. Obviously, a cryptographic hash function such as SHA-1 would satisfy the relatively lax strength requirements needed for hash tables, but their slowness and complexity makes them unappealing. However, using cryptographic hash functions can protect against collision attacks when the hash table modulus and its factors can be kept secret from the attacker,[citation needed] or alternatively, by applying a secret salt.
[...]

ho pensato che forse non era la cosa adatta.
Quanto è veloce la macchina a calcolare un hash MD5?
tenete presente che devo fare tutto su un AMD Geode LX800 @ 500 MHz con 256 MB di RAM.

il fatto di immagazzinare tutto in un DB mi era comodo perchè devo aggiornare la lista di URL frequentemente sulla base di dati che mi vengono inviati.

[gurutech]

potrei anche fare un mix: caricare tutto in un DB e all'avvio del programma precaricare una tabella di hash come quella che mi ha illustrato cionci ....

[cionci]

Originariamente inviato da gurutech

potrei anche fare un mix: caricare tutto in un DB e all'avvio del programma precaricare una tabella di hash come quella che mi ha illustrato cionci ....

Certo...ovviamente gli hash degli url devono essere precalcolati (basta salvarsi i primi byte dell'hash o direttamente gli indici), non è il caso di andare a calcolarteli ogni volta. Per l'inserimento nella tabella direi che andarseli ad inserire a runtime nella lista corrispondente dovrebbe costare relativamente poco dal punto di vista computazionale (fai un inserimento in testa, più il calcolo degli indici della tabella).

Sicuramente un hash come md5 per un problema di questo tipo è sovradimensionato, ma in fondo a runtime si tratta di calcolarlo solo una volta per ogni url di cui verifichi la presenza.