Indirizzamento aperto e concatenamento separato

Question

Quale schema di gestione della collisione hashmap è migliore quando il fattore di carico è vicino a 1 per garantire uno spreco di memoria minimo?

Personalmente ritengo che la risposta sia un indirizzamento aperto con sondaggio lineare, poiché non richiede spazio di archiviazione aggiuntivo in caso di collisione. È corretto?

Answer 1

Rispondere alla domanda: Quale schema di gestione della collisione hashmap è migliore quando il fattore di carico è vicino a 1 a garantire uno spreco di memoria minimo?

Aprire l'indirizzamento/sondaggio che consente un riempimento alto. Perché come hai detto tu stesso, non c'è spazio aggiuntivo richiesto per le collisioni (solo, beh, forse il tempo - ovviamente anche questo presuppone che la funzione di hash non sia perfetta).

Se non hai specificato "load factor close to 1" o incluso "cost" metriche nella domanda, sarebbe completamente diverso.

Felice codifica.

Answer 2

Una mappa di hash che è completa si degraderà in una ricerca lineare, quindi sarà necessario mantenerle al di sotto del 90%.

Hai ragione sull'indirizzamento aperto utilizzando meno memoria, il concatenamento richiederà un puntatore o un campo di offset in ciascun nodo.

Ho creato una struttura dati hasharray per quando ho bisogno di hashta molto leggeri che non avranno molti inserti. Per mantenere l'utilizzo della memoria basso tutti i dati sono incorporati nello stesso blocco di memoria, con la struttura di HashArray all'inizio, quindi due array per i valori di hash &. Hasharray può essere utilizzato solo con la chiave di ricerca memorizzata nel valore.

typedef uint16_t HashType; /* this can be 32bits if needed. */ 
typedef uint16_t HashSize; /* this can be made 32bits if large hasharrays are needed. */ 
struct HashArray { 
    HashSize length;  /* hasharray length. */ 
    HashSize count;   /* number of hash/values pairs contained in the hasharray. */ 
    uint16_t value_size; /* size of each value. (maximum size of value 64Kbytes) */ 
    /* these last two fields are just for show, they are not defined in the HashArray struct. */ 
    uint16_t hashs[length]; /* array of hashs for each value, this helps with resolving bucket collision */ 
    uint8_t values[length * value_size]; /* array holding all values. */ 
}; 
#define hasharray_get_hashs(array) (HashType *)(((uint8_t *)(array)) + sizeof(HashArray)) 
#define hasharray_get_values(array) ((uint8_t *)(array)) + sizeof(HashArray) + \ 
             ((array)->length * sizeof(HashType)) 
#define hasharray_get_value(array, idx) (hasharray_get_values(array) + ((idx) * (array)->value_size)) 

Le macro hasharray_get_hashs & hasharray_get_values ​​vengono utilizzati per ottenere & array 'valori' il 'hashs'.

L'ho utilizzato per aggiungere la ricerca rapida di oggetti complessi già archiviati in una matrice. Gli oggetti hanno un campo 'nome' stringa che viene utilizzato per la ricerca. I nomi vengono sottoposti a hash e inseriti nell'hashray con l'indice degli oggetti. I valori memorizzati nell'harryray possono essere indici/puntatori/oggetti interi (utilizzo solo valori di indice a 16 bit piccoli).

Se si desidera imballare l'hasharray fino a quando non è quasi pieno, si vorrà utilizzare Hash full a 32 bit invece di quelli a 16 bit sopra definiti. I più grandi hash a 32 bit contribuiranno a mantenere le ricerche veloci quando l'hasharray è più pieno del 90%.

L'hasharray come definito sopra può contenere solo un massimo di 65535, il che va bene poiché non lo uso mai su qualcosa che avrebbe più di qualche centinaio di valori. Tutto ciò che ha bisogno di più che dovrebbe semplicemente usare un normale hashtable. Ma se la memoria è davvero un problema, il tipo HashSize può essere cambiato in 32 bit. Inoltre uso le lunghezze power-of-2 per mantenere veloce la ricerca hash. Alcune persone preferiscono utilizzare lunghezze di bucket prime, ma ciò è necessario solo se la funzione hash ha una distribuzione errata.

#define hasharray_empty_hash 0xFFFF /* hash value to mark empty slots. */ 
void *hasharray_search(HashArray *array, HashType hash, uint32_t *next) { 
    HashType *hashs = hasharray_get_hashs(array); 
    uint32_t mask = array->length - 1; 
    uint32_t start_idx; 
    uint32_t idx; 

    hash = (hash == hasharray_empty_hash) ? 0 : hash; /* need one hash value to mark empty slots. */ 
    start_hash_idx = (hash & mask); 
    if(*next == 0) { 
    idx = start_idx; /* new search. */ 
    } else { 
    idx = *next & mask; /* continuing search to next slot. */ 
    } 

    /* find hash in hash array. */ 
    do { 
    /* check for hash match. */ 
    if(hashs[idx] == hash) goto found_hash; 
    /* check for end of chain. */ 
    if(hashs[idx] == hasharray_empty_hash) break; 
    idx++; 
    idx &= mask; 
    } while(idx != start_idx); 
    /* maximum tries reached (i.e. did a linear search of whole array) or end of chain. */ 
    return NULL; 

found_hash: 
    *next = idx + 1; /* where to continue search at, if this is not the right value. */ 
    return hasharray_get_values(array) + (idx * array->value_size); 
} 

collisioni hash che accadrà in modo che il codice che chiama hasharray_search() ha bisogno di confrontare la chiave di ricerca con quello memorizzato nel oggetto valore. Se non corrispondono, hasharray_search() viene chiamato di nuovo. Possono esistere anche chiavi non univoche, poiché la ricerca può continuare finché non viene restituito "NULL" per trovare tutti i valori che corrispondono a una chiave. La funzione di ricerca utilizza il rilevamento lineare per essere cache in modo indipendente.

typedef struct { 
    char *name; /* this is the lookup key. */ 
    char *type; 
    /* other field info... */ 
} Field; 

typedef struct { 
    Field *list;   /* array of Field objects. */ 
    HashArray *lookup; /* hasharray for fast lookup of Field objects by name. The values stored in this hasharray are 16bit indices. */ 
    uint32_t field_count; /* number of Field objects in 'list'. */ 
} Fields; 

extern Fields *fields_new(uint16_t count) { 
    Fields *fields; 
    fields = calloc(1, sizeof(Fields)); 
    fields->list = calloc(count, sizeof(Field)); 
    /* allocate hasharray to hold at most 'count' uint16_t values. 
    * The hasharray will round 'count' up to the next power-of-2. 
    * That power-of-2 length must be atleast (count+1), so that there will always be one empty slot. 
    */ 
    fields->lookup = hasharray_new(count, sizeof(uint16_t)); 
    fields->field_count = count; 
} 

extern Field *fields_lookup_by_name(Fields *fields, const char *name) { 
    HashType hash = str_to_hash(name); 
    Field *field; 
    uint32_t next = 0; 
    uint16_t *rc; 
    uint16_t idx; 

    do { 
    rc = hasharray_search(fields->lookup, hash, &next); 
    if(rc == NULL) break; /* field not found. */ 
    /* found a possible match. */ 
    idx = *rc; 
    assert(idx < fields->field_count); 
    field = &(fields->list[idx]); 
    /* compare lookup name with field's name. */ 
    if(strcmp(name, field->name) == 0) { 
     /* found match. */ 
     return field; 
    } 
    /* field didn't match continue search to next field. */ 
    } while(1); 
    return NULL; 
} 

Il caso peggiore ricerca si degrada ad una ricerca lineare di tutta la serie, se è pieno al 99% e la chiave non esiste. Se le chiavi sono numeri interi, una ricerca lineare non dovrebbe essere negativa, anche solo le chiavi con lo stesso valore di hash dovranno essere confrontate. Cerco di mantenere gli hasharry dimensionati in modo che siano pieni solo del 70-80%, lo spazio perso sugli slot vuoti non è molto se i valori sono solo a 16 bit. Con questo design si sprecano solo 4 byte per slot vuoto quando si utilizzano valori di indice a 16 bit per gli hashs & a 16 bit. La matrice di oggetti (strutture di campo nell'esempio precedente) non ha spazi vuoti.

Anche la maggior parte delle implementazioni di hashtable che ho visto non memorizza gli hash computati e richiede confronti a chiave completi per risolvere le collisioni con bucket. Il confronto degli hash aiuta molto poiché solo una piccola parte del valore hash viene utilizzata per cercare il bucket.

Answer 3

Come gli altri hanno detto, in sondaggio lineare, quando il fattore di carico vicino a 1, la complessità temporale vicino alla ricerca lineare. (Quando è pieno, è infinito.) Qui c'è un compromesso sull'efficienza della memoria. Mentre il concatenamento separato ci da sempre un tempo teoricamente costante.

Normalmente, sotto sondaggio lineare, si consiglia di mantenere il fattore di carico tra 1/8 e 1/2. quando l'array è pieno di 1/2, lo ridimensioniamo per raddoppiare la dimensione dell'array originale. (Riferimento: Algorithms. Di Robert Sedgewick, Kevin Wayne.). Quando elimini, ridimensioniamo l'array a 1/2 della dimensione originale. Se sei veramente interessato, è bene iniziare con il libro che ho menzionato sopra. In pratica, si dice che lo 0,72 sia un valore empirico che usiamo di solito.