Est-il possible de créer une fonction de hachage parfaite minimale dans cette situation?

Je souhaite créer une carte de hachage (ou une autre structure, si vous avez des suggestions) pour stocker les paires clé-valeur. Les clés seront toutes insérées en même temps au moment de la création de la carte, mais je ne sais pas quelles seront les clés (chaînes de longueur arbitraire) avant l’exécution, lorsque je dois créer la carte.

J’parsing une chaîne de requête du type "x=100&name=bob&color=red&y=150" (mais la chaîne peut contenir un nombre illimité de variables et les variables peuvent avoir un nom quelconque).

Je souhaite l’parsingr une fois et créer une carte de hachage, de préférence minimale et dotée d’une fonction de hachage parfaite pour répondre aux exigences de stockage linéaire. Une fois la carte créée, les valeurs ne seront ni modifiées ni supprimées. Aucune paire clé / valeur clé ne sera ajoutée à la carte. La carte entière est donc en réalité une constante. Je suppose qu’une variable ne figure pas deux fois dans la chaîne (IE. "x=1&x=2" n’est pas valide).

Je code en C et possède actuellement une fonction que je peux utiliser, comme get("x") qui renverra la chaîne "100" , mais analysant la chaîne de requête à chaque fois, ce qui prend O(n) fois. Je voudrais l’parsingr une fois lors de son premier chargement car il s’agit d’une très grande chaîne de requête et chaque valeur sera lue plusieurs fois. Même si j’utilise C , je n’ai pas besoin de code en C pour répondre. Pseudocode, ou toute suggestion serait génial!

Essayez GPL’d gperf , ou l’implémentation du domaine public de Bob Jenkins en C

Procédure:

  • recevoir une chaîne de requête et identifier le domaine de la fonction de hachage parfaite en énumérant la liste des clés

  • fournissez ces clés et la taille de la liste (la plage sera 1..size) à la fonction de génération de hachage parfaite dérivée des implémentations de référence ci-dessus

  • Utilisez la fonction de hachage parfaite générée pour créer le HashMap

  • Utilisez la même fonction de hachage parfaite pour traiter les demandes d’ get dans HashMap

Edit Necrolis a noté dans le commentaire ci-dessous que les implémentations de référence produisaient des fonctions de hachage parfait dans le code source C, vous devez donc les modifier pour générer à la place un type de code binary pour une machine virtuelle. Vous pouvez également utiliser un langage interprétatif tel que Scheme intégré ou Lua.

Il serait intéressant de savoir si cela vaut la peine de déployer des efforts sur une simple HashMap (non parfaite) lorsque les frais généraux liés à la création de la fonction de hachage parfait sont amortis au cours des recherches.

Une autre option est le hachage de coucou qui comporte également des recherches O (1).

Il existe de très bonnes routines de hachage; Cependant, prouver que l’un d’entre eux est proche de la perfection nécessite une grande connaissance des entrées. Il semble que vos entrées ne soient pas suffisamment contraintes pour rendre une telle preuve presque impossible.

En règle générale, une routine parfaite (ou presque parfaite) est sensible à chaque bit / octet d’entrée. Pour la vitesse, la combinaison est généralement XOR. La manière dont ces routines empêchent deux octets identiques de s’annuler consiste à décaler ou à faire pivoter les bits. Toutefois, ce décalage doit être effectué avec un nombre premier par rapport au nombre maximal pouvant être représenté. sinon, les motifs de l’entrée pourraient être partiellement annulés par l’entrée précédente. Cela réduit l’entropie dans la solution, augmentant les risques de collision.

La solution typique est de

 Start with a number that is a prime (all primes are relative primes) while (more bytes to be considered) { take the next byte of input and multiply it by a second prime determine the number of bits that might be lost in a left shift, capture them in a buffer shift the bits in the hash "buffer" to the left. restore the high order bit(s) in the low position take the next byte of input and multiply it by a second prime mask the multiplied result into the buffer } 

Les problèmes avec une telle routine sont connus. Fondamentalement, l’entrée varie peu, ce qui rend la dispersion de l’entrée non idéale. Cela dit, cette technique permet une bonne dispersion des bits d’entrée sur l’ensemble du domaine des sorties, à condition que l’entrée soit suffisante pour s’éloigner du nombre premier initial. Malheureusement, choisir un numéro de départ aléatoire n’est pas une solution, car il devient alors impossible de recalculer avec précision le hachage.

Dans tous les cas, le nombre premier à utiliser dans la multiplication ne doit pas déborder de la multiplication. De même, la capture des bits de poids fort doit être replacée dans le ordre bas si vous voulez éviter de perdre les effets de dispersion de l’entrée initiale (et que le résultat ne soit groupé que dans ces derniers bits / octets). La sélection du nombre premier affecte la dispersion, et parfois un réglage optimal est nécessaire.

À présent, vous devriez pouvoir facilement vous rendre compte qu’un hachage presque parfait prend plus de temps de calcul qu’un hachage décent moins que presque parfait. Les algorithmes de hachage sont conçus pour prendre en compte les collisions et la plupart des structures de hachage Java sont redimensionnées au seuil d’occupation (généralement dans la plage de 70%, mais paramétrable). Étant donné que le redimensionnement est intégré, tant que vous n’écrivez pas un hachage terrible, les structures de données Java continueront de vous ajuster afin de réduire les risques de collision.

Les optimisations permettant d’accélérer un hachage incluent le calcul sur des groupes de bits, la suppression d’octets occasionnels, les tables de consultation de pré-calcul des nombres multipliés couramment utilisés (indexés par entrée), etc. Les détails de la machine, et “l’âge” de l’optimisation, parfois les hypothèses de l’optimisation ne tiennent plus et l’application de l’optimisation augmente en réalité le temps nécessaire pour calculer le hachage.

Il n’y a pas de hasch parfait dans ce que vous décrivez. Un hachage parfait serait l’entrée originale. Si vous êtes assuré que vos données ne contiendront que certaines choses (telles que l’ASCII basé sur le latin ou seulement certaines clés), alors vous pouvez effectuer un hachage correct, mais parfait? Non possible. Vous devez également créer un mécanisme d’absence de hachage de liste de liens ou de vecteur. Toute variante du système (comme le nombre d’entrées dans votre cas) invalidera le concept de hachage parfait.

Ce que vous voulez défie les lois des mathématiques.

Vous pouvez atteindre près de O (1), mais il y a des questions sans réponse ici. Les questions sont:

  1. Pourquoi faut-il que ce soit un stockage linéaire?
  2. Les suppressions de la table sont-elles communes (vous avez uniquement spécifié que les paires clé-valeur ne seraient pas ajoutées après la création initiale)?
  3. Quelle est la taille de la table susceptible de croître par rapport à la plage de hachage?
  4. Quelle est la fréquence des insertions par rapport à la répétition de données?
  5. La mémoire est-elle un facteur important?

Bien qu’un hachage parfait ne soit pas possible, il devient tout à fait académique de disposer simplement d’une simple liste chaînée avec une taille de compartiment d’au moins deux écarts types par rapport à la moyenne de vos hachages uniques potentiels. C’est une mémoire minimale (relativement parlant bien sûr et en fonction de la taille potentielle totale), facile à supprimer, et qui prendrait presque un temps de consultation de 1 (1) tant que la question 3 reçoit une réponse du type “beaucoup plus petite”.

Ce qui suit devrait vous aider à démarrer, mais je vais laisser les décisions concernant l’algorithme de hachage à utiliser jusqu’à vous …

 #include  #include  #include  // Dummy value type to test comstack. Replace throughout #define YOUR_VALUE_T int // See below where the charmap is //#define HTABLE_USE_CHARMAP // Maintain a true linked list that's manageable and iterateable #define HTABLE_MAINTAIN_LIST // Count lookup misses and such #define HTABLE_KEEP_STATS // Fast deletion = faster deletion but more memory consumption //#define HTABLE_FAST_DELETES #ifdef HTABLE_USE_CHARMAP // This is used to quickly collapse the input from full 8-bit to the minimal character set of truely expected data. // The idea here is to boil down the data. This should only be done if you're confident enough to develop a custom // hashing algorithm for this particular known range const char hashing_charmap[256] = { // Each data point that is unused (such as control characters or high 8-bit characters) // should be 0, while each used character should be represented with a unique sequential value (1, 2, 3, etc) // I'm not going to build this for you because it's very custom to your needs. // A chunk might look look like... /* 0, 0, 0, 0, 17, 18, 19, 0, 0, 20, 21, */ }; #endif static inline uint32_t hash_str(register const char* s, const size_t len) { register uint32_t hash = 5381; // hash seed here. This could be different depending on the actual algorithm chosen register char symbol; // This could be unrolled because we known ssortingng length as well. for (register size_t i=0; i < len; i++) { #ifdef HTABLE_USE_CHARMAP if (!(symbol = hash_charmap[s[i]])) continue; #else // Actually s[i] could simply be used (which would be faster) if no mapping is needed. symbol = s[i]; #endif // True hash algorithm per-symbol operation here /* Keep in mind that certain algorithms are optimized for certain things. An example: Stock DJBX33A is very fast but effectively only represents the end of a long input. It's really meant for short inputs (like variable names) A MurmurHash or tuned FNV variant are likely to be a good picks since we've reduced symbol range and we are dealing with potential long inputs. It's also important to understand that the entire hash will likely not be used. Only the lower-end bits will be used (you'll see why in the actual functionality). If you're hashing algorithm is good though, this shouldn't matter because the distribution should be normal. I'll just use Jenkins one-at-a-time hash here (because it's easy) */ hash += symbol; hash += (hash << 10); hash ^= (hash >> 6); } // Finialize jenkins one-at-a-time hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return hash; }; typedef struct _hash_entry { char* key; size_t key_len; uint32_t hash; // Whatever your value type is (likely a pointer to your own record or something) YOUR_VALUE_T value; // Internal linking maintains order. // If you don't need proper order maintentence, you don't need these #ifdef HTABLE_MAINTAIN_LIST struct _hash_entry* prev; struct _hash_entry* next; #endif #ifdef HTABLE_FAST_DELETES struct _hash_entry* bucket_prev; #endif // This is required for the occassional hash miss struct _hash_entry* bucket_next; } hash_entry_t; typedef struct _hash_table { // Counts size_t entry_count; uint32_t bucket_count; unsigned int growth_num; unsigned int growth_den; #ifdef HTABLE_KEEP_STATS // How many times we missed during lookup size_t misses; // (entry_count - used_buckets) tells you how many collisions there are (the lower the better) uint32_t used_buckets; #endif // Internal linking. Same conditions as in hash_entry_t so feel free to remove as necessary. #ifdef HTABLE_MAINTAIN_LIST hash_entry_t* first; hash_entry_t* last; #endif // Buckets, the soul of the hash table uint32_t hash_mask; hash_entry_t** buckets; } hash_table_t; // Creates a hash table // size_hint - Tells to table how many buckets it should initially allocate. // If you know (for example) that you'll have about 500 entries, set it // to 500 // growth_num and growth_den - This is the ratio of how many entries to how // many buckets that you want to guarantee. // It's in two integers to avoid floating point math for speed. // The logic after an insertion is... // if (entry_count == growth_num * (bucket_count / growth_den)) then // grow the bucket array // For example, when growth_num is 4 and growth_den is 5... // (entry_count == 4 * (bucket_count / 5)) // ...would be true when entry count is 80% of the bucket count // This can result in a greater than 1.0 ratio (such as 5/4 or something // like that) if you prefer. This would mean that there are less buckets // than there are entries, so collisions are guaranteed at that point, but // you would save on both memory and often a bucket expansion occurs (which // is costly during an insert operation). static hash_table_t* htable_create(const size_t size_hint, const unsigned int growth_num, const unsigned int growth_den); // Frees a hash table static void htable_free(hash_table_t* table); // Mostly used internally. You probably want htable_get(), htable_value(), or htable_exists() static hash_entry_t* htable_find_entry(hash_table_t* table, const char* key, size_t key_len, uint32_t* hash, size_t* true_len); // Get the pointer to a value stored in the table (or NULL on non-existant) static YOUR_VALUE_T* htable_value(const hash_table_t* table, const char* key, size_t key_len); // Get the value of an entry, or the default value if the entry doesn't exist static YOUR_VALUE_T htable_get(const hash_table_t* table, const char* key, size_t key_len, const YOUR_VALUE_T default_value); // Test for the existance of a value static int htable_exists(const hash_table_t* table, const char* key, size_t key_len); // Add a new entry (but don't update if it already exists). Returns NULL if it already exists static hash_entry_t* htable_add(hash_table_t* table, const char* key, size_t key_len, YOUR_VALUE_T value); // Update an entry OR add aa new entry it doesn't already exist static hash_entry_t* htable_set(hash_table_t* table, const char* key, size_t key_len, YOUR_VALUE_T value); // Update an entry but don't add aa new entry it doesn't already exist. Returns NULL if doesn't exist static hash_entry_t* htable_update(hash_table_t* table, const char* key, size_t key_len, YOUR_VALUE_T value); // Delete an entry. Returns 1 on success or 0 if the entry didn't exist static int htable_delete(hash_table_t* table, const char* key, size_t key_len); // Pack the table. // This is here because... // - If HTABLE_FAST_DELETES is set, and if you delete a bunch of entries, it's // possible that you can free up some memory by shrinking the bucket array. // You would have to call this manually to make that happen. // - If HTABLE_FAST_DELETES is NOT set however, this get's called automatically // on each delete, so the buckets are guaranteed to be packed. static void htable_pack(hash_table_t* table); /*********************************\ Implementation... \*********************************/ static hash_table_t* htable_create(const unsigned long size_hint, const unsigned int growth_num, const unsigned int growth_den) { hash_table_t* res = malloc(sizeof(hash_table_t)); if (!res) return NULL; res->entry_count = 0; #ifdef HTABLE_MAINTAIN_LIST res->first = NULL; res->last = NULL; #endif #ifdef HTABLE_KEEP_STATS res->misses = 0; res->used_buckets = 0; #endif if ((!growth_num) || (!growth_den)) { // Grow only when the entry count matches the bucket count res->growth_num = 1; res->growth_den = 1; } else { res->growth_num = growth_num; res->growth_den = growth_den; } /* For computational speed and simplicity we'll grow the bucket array exponentially. Not growing the buckets exponentially is possible but requires a different entry lookup mechanism (because hash & hash_mask would no longer work) and would likely involve the modulas operator which is very slow. If memory is uber important however, this might be a good solution. */ // We'll go ahead and assume it's a reasonably small table and only allocate 256 buckets. int bits = 8; if (size_hint) { unsigned long target = (size_hint * res->growth_den) / res->growth_num; // First check is to prevent overflow as it would be 0 when bits is 31 on a 32 bit system while ((1 << (bits + 1)) && ((1 << bits) < target)) bits++; } res->bucket_count = 1 << bits; res->hash_mask = (1 << bits) - 1; if ((res->buckets = (hash_entry_t**)calloc(res->bucket_count, sizeof(hash_entry_t*))) == NULL) { free(res); return NULL; } memset(res->buckets, 0, sizeof(hash_entry_t*) * res->bucket_count); return res; }; // Destroy a table static void htable_free(hash_table_t* table) { hash_entry_t* entry; hash_entry_t* next; #ifdef HTABLE_MAINTAIN_LIST entry = table->first; while (entry) { next = entry->next; free(entry->key); free(entry); entry = next; } #else for (uint32_t i=0; i < table->bucket_count; i++) { entry = table->buckets[i]; while (entry) { next = entry->bucket_next; free(entry->key); free(entry); entry = next; } } #endif free(table->buckets); free(table); } // Find an entry: (mostly used internally) // returns NULL when the entry isn't found static hash_entry_t* htable_find_entry(hash_table_t* table, const char* key, size_t key_len, uint32_t* hash, size_t* true_len) { if (!key_len) key_len = strlen(key); if (true_len != NULL) *true_len = key_len; uint32_t h = hash_str(key, key_len); if (hash != NULL) *hash = h; uint32_t bucket = h & table->hash_mask; // Best case is here is O(1) because table->buckets[bucket] would be the entry hash_entry_t* entry = table->buckets[bucket]; // ... but if we miss, then the time increases to as much as O(n) where n is the number of ensortinges in // the particular bucket (good hash + good ratio management means that n would usually be only 1) while ((entry) && ((entry->hash != h) || (entry->key_len != key_len) || (memcmp(entry->key, key, key_len)))) { #ifdef HTABLE_KEEP_STATS table->misses++; #endif entry = entry->bucket_next; } return entry; } // Insertion of entry into bucket. Used internally static inline int _htable_bucket_insert(hash_entry_t** buckets, hash_entry_t* entry, const uint32_t hash_mask) { hash_entry_t* bentry; #ifdef HTABLE_FAST_DELETES entry->bucket_prev = NULL; #endif entry->bucket_next = NULL; uint32_t bidx = entry->hash & hash_mask; int res = 0; if ((bentry = buckets[bidx]) == NULL) { res = 1; buckets[bidx] = entry; } else { while (bentry->bucket_next) bentry = bentry->bucket_next; bentry->bucket_next = entry; #ifdef HTABLE_FAST_DELETES entry->bucket_prev = bentry; #endif } return res; } // Bucket array growing/shrinking. Used internally static void _htable_adjust_as_needed(hash_table_t* table) { int change = (((table->bucket_count << 1) != 0) && (table->entry_count >= table->growth_num * (table->bucket_count / table->growth_den))); if (!change) { if ((table->bucket_count > (1 << 8)) && (table->entry_count < table->growth_num * ((table->bucket_count >> 1) / table->growth_den))) { change = -1; } else { return; } } uint32_t new_bucket_count = (change < 0) ? table->bucket_count >> 1 : table->bucket_count << 1; uint32_t new_hash_mask = new_bucket_count - 1; hash_entry_t** new_buckets = (hash_entry_t**)calloc(new_bucket_count, sizeof(hash_entry_t*)); if (!new_buckets) return; memset(new_buckets, 0, new_bucket_count * sizeof(hash_entry_t*)); #ifdef HTABLE_KEEP_STATS table->used_buckets = 0; #endif hash_entry_t* entry; #ifdef HTABLE_MAINTAIN_LIST entry = table->first; while (entry) { int r = _htable_bucket_insert(new_buckets, entry, new_hash_mask); #ifdef HTABLE_KEEP_STATS table->used_buckets += r; #endif entry = entry->next; } #else hash_entry_t* next; for (uint32_t i=0; i < table->bucket_count; i++) { entry = table->buckets[i]; while (entry) { next = entry->bucket_next; int r = _htable_bucket_insert(new_buckets, entry, new_hash_mask); #ifdef HTABLE_KEEP_STATS table->used_buckets += r; #endif entry = next; } } #endif free(table->buckets); table->buckets = new_buckets; table->bucket_count = new_bucket_count; table->hash_mask = new_hash_mask; } // Get the pointer to the value of the entry or NULL if not in table static YOUR_VALUE_T* htable_value(const hash_table_t* table, const char* key, size_t key_len) { // un-const table so that find_entry can keep statistics hash_entry_t* entry = htable_find_entry((hash_table_t*)table, key, key_len, NULL, NULL); return (entry != NULL) ? &entry->value : NULL; } static YOUR_VALUE_T htable_get(const hash_table_t* table, const char* key, size_t key_len, const YOUR_VALUE_T default_value) { // un-const table so that find_entry can keep statistics hash_entry_t* entry = htable_find_entry((hash_table_t*)table, key, key_len, NULL, NULL); return (entry != NULL) ? entry->value : default_value; } static int htable_exists(const hash_table_t* table, const char* key, size_t key_len) { // un-const table so that find_entry can keep statistics return (htable_find_entry((hash_table_t*)table, key, key_len, NULL, NULL) != NULL); } // Add a new entry (but don't update if it already exists) // Returns NULL if the entry already exists (use set() if you want add or update logic) static hash_entry_t* htable_add(hash_table_t* table, const char* key, size_t key_len, YOUR_VALUE_T value) { uint32_t hash; hash_entry_t* res = htable_find_entry(table, key, key_len, &hash, &key_len); if (res != NULL) return NULL; if ((res = (hash_entry_t*)malloc(sizeof(hash_entry_t))) == NULL) return NULL; if ((res->key = (char*)malloc(key_len + 1)) == NULL) { free(res); return NULL; } memcpy(res->key, key, key_len + 1); res->key_len = key_len; res->hash = hash; res->value = value; #ifdef HTABLE_MAINTAIN_LIST res->prev = NULL; res->next = NULL; if (table->first == NULL) { table->first = res; table->last = res; } else { res->prev = table->last; table->last->next = res; table->last = res; } #endif int r = _htable_bucket_insert(table->buckets, res, table->hash_mask); #ifdef HTABLE_KEEP_STATS table->used_buckets += r; #endif table->entry_count++; _htable_adjust_as_needed(table); return res; } static hash_entry_t* htable_set(hash_table_t* table, const char* key, size_t key_len, YOUR_VALUE_T value) { uint32_t hash; hash_entry_t* res = htable_find_entry(table, key, key_len, &hash, &key_len); if (res != NULL) { res->value = value; return res; } if ((res = (hash_entry_t*)malloc(sizeof(hash_entry_t))) == NULL) return NULL; if ((res->key = (char*)malloc(key_len + 1)) == NULL) { free(res); return NULL; } memcpy(res->key, key, key_len + 1); res->key_len = key_len; res->hash = hash; res->value = value; #ifdef HTABLE_MAINTAIN_LIST res->prev = NULL; res->next = NULL; if (table->first == NULL) { table->first = res; table->last = res; } else { res->prev = table->last; table->last->next = res; table->last = res; } #endif int r = _htable_bucket_insert(table->buckets, res, table->hash_mask); #ifdef HTABLE_KEEP_STATS table->used_buckets += r; #endif table->entry_count++; _htable_adjust_as_needed(table); return res; } // Update an entry but don't add aa new entry it doesn't already exist. Returns NULL if doesn't exist static hash_entry_t* htable_update(hash_table_t* table, const char* key, size_t key_len, YOUR_VALUE_T value) { hash_entry_t* res = htable_find_entry(table, key, key_len, NULL, NULL); if (res == NULL) return NULL; res->value = value; return res; } // Delete an entry. Returns 1 on success or 0 if the entry didn't exist static int htable_delete(hash_table_t* table, const char* key, size_t key_len) { uint32_t hash; hash_entry_t* entry = htable_find_entry(table, key, key_len, &hash, &key_len); if (entry == NULL) return 0; #ifdef HTABLE_MAINTAIN_LIST if (entry == table->first) table->first = entry->next; if (entry == table->last) { table->last = entry->prev; } if (entry->prev != NULL) entry->prev->next = entry->next; if (entry->next != NULL) entry->next->prev = entry->prev; #endif uint32_t bucket = hash & table->hash_mask; hash_entry_t* bhead = table->buckets[bucket]; hash_entry_t* bprev = NULL; #ifdef HTABLE_FAST_DELETES bprev = entry->bucket_prev; #else if (bhead != entry) { bprev = bhead; while (bprev->bucket_next != entry) bprev = bprev->bucket_next; } #endif if (bprev != NULL) bprev->bucket_next = entry->bucket_next; #ifdef HTABLE_FAST_DELETES if (entry->bucket_next != NULL) entry->bucket_next->bucket_prev = entry->bucket_next; #endif if (bhead == entry) { table->buckets[bucket] = entry->bucket_next; #ifdef HTABLE_KEEP_STATS if (entry->bucket_next == NULL) table->used_buckets--; #endif } free(entry->key); free(entry); table->entry_count--; #ifndef HTABLE_FAST_DELETES htable_pack(table); #endif return 1; } static void htable_pack(hash_table_t* table) { _htable_adjust_as_needed(table); } 

Exemples d’utilisation (comme assertions) et tests d’efficacité. Utiliser int comme type de valeur de données …

 hash_table_t* ht = htable_create(0, 0, 0); assert(ht != NULL); // Table was created successfully // Testing basic adding/updating/getting... assert(htable_add(ht, "hello-world", 0, 234) != NULL); // hello-world set to 234 assert(htable_add(ht, "goodbye-world", 0, 567) != NULL); // goobye-world set to 567 assert(ht->entry_count == 2); // Two ensortinges exist (hello-world and goodbye-world) assert(htable_exists(ht, "hello-world", 0) == 1); // hello-world exists assert(htable_exists(ht, "goodbye-world", 0) == 1); // goodbye-world exists assert(htable_exists(ht, "unknown-world", 0) == 0); // unknown-world doesn't exist assert(*htable_value(ht, "hello-world", 0) == 234); // hello-world has a value of 234 assert(*htable_value(ht, "goodbye-world", 0) == 567); // goodbye-world has a value of 567 assert(htable_get(ht, "hello-world", 0, -1) == 234); // hello-world exists and has a value of 234 assert(htable_get(ht, "goodbye-world", 0, -1) == 567); // goobye-world exists and has a value of 567 assert(htable_get(ht, "unknown-world", 0, -1) == -1); // unknown-world does not exist so the default value of -1 is returned *htable_value(ht, "hello-world", 0) = -1; // hello-world's value is directly set via reference to -1 *htable_value(ht, "goodbye-world", 0) = -2; // goodbye-world's value is directly set via reference to -2 assert(*htable_value(ht, "hello-world", 0) == -1); // hello-world has a value of -1 assert(*htable_value(ht, "goodbye-world", 0) == -2); // goodbye-world has a value of -2 assert(htable_update(ht, "hello-world", 0, 1000) != NULL); // hello-world set to 1000 assert(htable_update(ht, "goodbye-world", 0, 2000) != NULL); // goodbye-world set to 2000 assert(htable_update(ht, "unknown-world", 0, 3000) == NULL); // unknown-world not set (it doesn't exist); assert(ht->entry_count == 2); // Two ensortinges exist (hello-world and goodbye-world) assert(htable_set(ht, "hello-world", 0, 1111) != NULL); // hello-world set to 1111 assert(htable_set(ht, "goodbye-world", 0, 2222) != NULL); // goodbye-world set to 2222 assert(htable_set(ht, "unknown-world", 0, 3333) != NULL); // unknown-world added with a value of 3333 assert(ht->entry_count == 3); // Three ensortinges exist (hello-world, goodbye-world, and unknown-world) printf("%s\n", "After all additions and changes:"); #ifdef HTABLE_MAINTAIN_LIST // A foreach iteration hash_entry_t* entry = ht->first; while (entry != NULL) { printf("\"%s\" = %i\n", entry->key, entry->value); entry = entry->next; } #endif #ifdef HTABLE_KEEP_STATS assert(ht->entry_count - ht->used_buckets == 0); // Means that no hash collisions occured assert(ht->misses == 0); // Means that each lookup was in O(1) time #endif // Testing basic deletion... assert(htable_delete(ht, "not-a-world", 0) == 0); // not-a-world not deleted (doesn't exist) assert(htable_delete(ht, "hello-world", 0) == 1); // hello-world deleted assert(htable_delete(ht, "hello-world", 0) == 0); // hello-world not deleted (doesn't exist) assert(htable_exists(ht, "hello-world", 0) == 0); // hello-world doesn't exit assert(htable_exists(ht, "goodbye-world", 0) == 1); // goobye-world still exists assert(htable_exists(ht, "unknown-world", 0) == 1); // unknown-world still exists assert(ht->entry_count == 2); // Two ensortinges exists (goodbye-world and unknown-world) assert(htable_delete(ht, "unknown-world", 0) == 1); // unknown-world deleted assert(htable_exists(ht, "unknown-world", 0) == 0); // unknown-world doesn't exit assert(htable_exists(ht, "goodbye-world", 0) == 1); // goodbye-world still exists assert(ht->entry_count == 1); // One entry exists (goodbye-world) #ifdef HTABLE_MAINTAIN_LIST // A foreach iteration printf("%s\n", "After deletion:"); entry = ht->first; while (entry != NULL) { printf("\"%s\" = %i\n", entry->key, entry->value); entry = entry->next; } #endif #ifdef HTABLE_KEEP_STATS assert(ht->entry_count - ht->used_buckets == 0); // Means that no hash collisions occured assert(ht->misses == 0); // Means that each lookup was in O(1) time #endif htable_free(ht); 

De plus, j’ai effectué des tests avec 100 000 clés ASCII générées aléatoirement, d’une longueur comprise entre 5 et 1 000 caractères.

  • Après des entrées aléatoires en utilisant les parameters par défaut :
    • Entrées: 100000
    • Seaux: 131072
    • Godets d’occasion: 69790
    • Collisions: 30210
    • Misses: 71394
    • Efficacité du hachage / seau: 69.79%
  • Après des entrées aléatoires utilisant un taux de croissance de 1/2 :
    • Entrées: 100000
    • Seaux: 262144
    • Godets d’occasion: 83181
    • Collisions: 16819
    • Misses: 35436
    • Efficacité de hachage / seau: 83.18%
  • Après des entrées aléatoires utilisant un taux de croissance de 2/1 :
    • Entrées: 100000
    • Seaux: 65536
    • Godets usagés: 51368
    • Collisions: 48632
    • Misses: 141607
    • Efficacité de hachage / seau: 51.37%

Comme vous pouvez le constater, il peut potentiellement très bien fonctionner. Une efficacité de 80% signifie qu’environ 80% des recherches sont O (1), environ 16% des recherches sont O (2), environ 3,2% des recherches sont O (3) et environ 0,8% des recherches sont O (4+). Cela signifie qu’en moyenne, une recherche prendrait O (1.248).

De même, une efficacité de 50% signifie que 50% des recherches sont O (1), 25% sont O (2), 12,5% sont O (3) et 12,5% sont O (4+).

Vous avez juste besoin de choisir (ou d’écrire) le bon algorithme de hachage pour vos facteurs connus et de peaufiner les choses pour vos besoins spécifiques.

Remarques:

  1. Ces affirmations / tests ont fonctionné pour moi, mais il n’est pas garanti que le logiciel soit sans bug . Cela semble assez stable. Il y a probablement un ou deux insectes qui circulent à l’intérieur.
  2. Si vous avez besoin de la gestion de liste, vous pouvez facilement append des choses comme move() , swap() , sort() , insert() , etc. en gérant entry->prev et entry->next
  3. Je ne pouvais pas inclure le code de test car je semble avoir atteint la limite de taille de réponse.
  4. Ni la fonction de hachage ni la comparaison de chaîne finale ne sont incluses dans l’parsing temporelle. Cela serait impossible à parsingr sans connaître toutes les statistiques sur l’entrée. Les deux fonctions devraient cependant être assez rapides et la comparaison de chaînes pourrait être complètement effacée si davantage d’informations sont connues sur les données d’entrée.

if you know the set of all possible variable names, then it would be possible to use to perfect hash the names to numbers

but each of the hash tables would end up having the same length an example is if X and y are the names then the map would always be of length 2

if perfect(str) turns 'x' and 'y' into 0 and 1; then the function get would be

 get(field, table) { return table[perfect(field)]; }