come cercare usando il doppio hash in c

Ho un server per ricevere la richiesta da più client. L’ho fatto con i thread. Voglio inserire un nome utente e una password nella tabella hash. Per quello sto usando il doppio metodo di hash. È stato inserito con successo Ma voglio sapere quando l’utente inserisce un nome utente, ho bisogno di cercare sulla tabella hash se questo nome utente già presente. Ma non posso farlo ora. Conosco il concetto come usare l’hashing. Ottieni l’indice usando hashfunction1 attraverso il nome utente e usa il doppio hash come questo. Ma come posso scrivere quel codice?

Il mio codice:

int HashFunc1 (char *key,int size) { int i = 0,value = 0; for(i = 0 ; key[i] != '\0'; i++) { value += ( key[i] + ( i + 1 ) ); } return value % size; } int HashFunc2 (char *key,int size) { int i = 0,value = 0; for(i = 0; key[i] != '\0'; i++) { value += ( key[i] + ( i + 1 ) ); } return (value * size - 1) % size; } int Findindex(char *key,struct HashTable **htable) { int hashVal = 0, stepSize = 0; hashVal = HashFunc1(key, (*htable)->size); stepSize= HashFunc2(key, (*htable)->size); /*to avoid collisions)*/ while ( (*htable)->table[hashVal].username != NULL) { /*double hahsing process*/ hashVal = hashVal + stepSize; hashVal = hashVal % (*htable)->size; } return hashVal; } int insert_to_hashtable(char *key,char *password,struct HashTable **htable) { int pos = 0; /*find the index to insert new user datas*/ pos = Findindex(key,htable); //code to insert to coresponding data if this empty } 

Come posso scrivere codice per cercare un nome utente già presente usando il doppio hashing dalla tabella hash in C? Penso che attraversare l’intero tavolo hash non sia una buona pratica … è così?

Il tuo hashtable ha una dimensione fissa S, quindi puoi inserire al massimo S elementi.

L’idea dell’hash doppio con i codici hash H1 e H2 è: Se c’è già una voce nella posizione H1, attraversa la larghezza hash della falcata H2. La taglia S è un numero primo. Ciò significa che con qualsiasi passo H2

Certo, se trovi uno spazio vuoto, lo prendi. In un hash scarsamente popolato, di solito devi fare solo pochi passi dal valore originale per trovare uno slot emty.

Più il tuo hash diventa popolato, meno efficiente sarà la ricerca della chiave. Una soluzione è quella di tenere traccia del numero di elementi e ridimensionare l’hash a una dimensione maggiore quando, per esempio, oltre il 75% delle voci è occupato. Naturalmente, anche le nuove dimensioni devono essere prime.

Nota anche questi problemi nel tuo codice: potresti generare un valore hash pari a 0 per la dimensione del passo e se la tua tabella hash è piena, la tua ricerca di uno slot vuoto verrà ripetuta all’infinito. Inoltre, non è necessario passare la tabella hash come riferimento, poiché non si modifica mai il puntatore stesso, ma solo i suoi membri struct. Puoi anche rendere const sia key che htable .

Così:

 int Findindex(const char *key, const struct HashTable *htable) { int hashVal, stepSize, startVal; hashVal = HashFunc1(key, htable->size); if (htable->table[hashVal].username == NULL) return hashVal; startVal = hashVal; stepSize = HashFunc2(key, (*htable)->size - 1) + 1; do { hashVal = (hashVal + stepSize) % htable->size; if (hashVal == startVal) return -1; } while (htable->table[hashVal].username); return hashVal; } 

Questo codice restituisce un valore speciale -1 per indicare che non ci sono spazi vuoti nella tabella hash.

Se vuoi cercare un nome utente, usi la stessa strategia. Qui, devi inoltre confrontare la chiave per ogni nodo, poiché chiavi diverse potrebbero condividere lo stesso codice hash. Se trovi uno spazio vuoto, la voce non è nella tabella.

Questa funzione restituisce un puntatore ai dati dell’utente (il cui tipo ho chiamato struct data , non viene mostrata la definizione della struct della tabella hash) associata alla chiave o NULL se l’utente non può essere trovato:

 struct data *FindKey(const char *key, const struct HashTable *htable) { int hashVal, stepSize, startVal; hashVal = HashFunc1(key, htable->size); if (htable->table[hashVal].username == NULL) return NULL; if (strcmp(htable->table[hashval].username, key) == 0) { return &htable->table[hashVal]; } startVal = hashVal; stepSize = HashFunc2(key, (*htable)->size - 1) + 1; for(;;) { hashVal = (hashVal + stepSize) % htable->size; if (hashVal == startVal) return NULL; if (htable->table[hashVal].username == NULL) return NULL; if (strcmp(htable->table[hashval].username, key) == 0) { return &htable->table[hashVal]; } } return NULL; } 

Avvertenza: non ho testato questo codice, ma spero che tu capisca il funzionamento di base.