Algorithme de hachage rapide des chaînes de caractères avec de faibles taux de collision avec un nombre entier de 32 bits [fermé]

Murmure de Hachage est assez agréable.

pour un jeu de ficelles fixe, utilisez gperf.

si votre chaîne de caractères change, vous devez choisir une fonction de hachage. Ce sujet a déjà été abordé:

Quel est le meilleur algorithme de hachage à utiliser sur une chaîne stl en utilisant hash_map?

il y a aussi un bel article à eternallyconfuzzled.com .

le hash de Jenkins pour cordes devrait ressembler à quelque chose comme ceci:

#include <stdint.h>

uint32_t hash_string(const char * s)
{
    uint32_t hash = 0;

    for(; *s; ++s)
    {
        hash += *s;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

une autre solution qui pourrait être encore meilleure selon votre cas d'utilisation est cordes entrelacées . C'est ainsi que les symboles fonctionnent, par exemple dans Lisp.

une chaîne de caractères internée est un objet string dont la valeur est l'adresse des octets string actuels. Ainsi, vous créez un objet string interné en cochant une table globale: si la chaîne est là, vous initialisez la chaîne internée à l'adresse de cette chaîne. Si non, vous insérez il, et ensuite initialiser votre chaîne de caractères internée.

cela signifie que deux cordes internes construites à partir de la même corde auront la même valeur, qui est une adresse. Ainsi, si N est le nombre de chaînes internes dans votre système, les caractéristiques sont:

• Lente construction (besoins de recherche et, éventuellement, l'allocation de mémoire)
• nécessite des données globales et la synchronisation dans le cas de threads concurrents
• comparer Est O (1), parce que vous comparez des adresses, pas des octets de chaîne de caractères réels (cela signifie que le tri fonctionne bien, mais ce ne sera pas un tri alphabétique).

Cheers,

Carl

pourquoi ne pas utiliser Boost libraries? leur fonction de hachage est simple à utiliser et la plupart des choses dans Boost feront bientôt partie de la norme C++. Certains de il ne l'est déjà.

le hash Boost est aussi facile que

#include <boost/functional/hash.hpp>

int main()
{
    boost::hash<std::string> string_hash;

    std::size_t h = string_hash("Hash me");
}

vous pouvez trouver boost à boost.org

Il n'est jamais tard pour un bon sujet et je suis sûr que les gens seraient intéressés à mes conclusions.

j'ai eu besoin d'une fonction de hachage et après avoir lu ce post et faire un peu de recherche sur les liens donnés ici, je suis venu avec cette variation de L'algorithme de Daniel J. Bernstein, que j'ai utilisé pour faire un test intéressant:

unsigned long djb_hashl(const char *clave)
{
    unsigned long c,i,h;

    for(i=h=0;clave[i];i++)
    {
        c = toupper(clave[i]);
        h = ((h << 5) + h) ^ c;
    }
    return h;
}

cette variation hache les chaînes en ignorant le cas, qui convient à mon besoin de hachage utilisateurs des informations d'identification. "clave" est " key " en espagnol. Je suis désolé pour l'espagnol mais sa ma langue maternelle et le programme est écrit sur elle.

Eh bien, j'ai écrit un programme qui va générer des noms d'utilisateurs de 'test_aaaa' à 'test_zzzz', et-pour rendre les chaînes plus longues - je leur ai ajouté un domaine aléatoire dans cette liste: 'cloud-nueve.com", "yahoo.com", "gmail.com" et "hotmail.com". Par conséquent, chacun d'eux ressemblerait à:

test_aaaa@cloud-nueve.com, test_aaab@yahoo.com, 
test_aaac@gmail.com, test_aaad@hotmail.com and so on.

voici la sortie du test -'Colision entre XXX y XXX' signifie 'Collision of XXX and XXX'. 'palabras" signifie "mots" et "Total" est le même dans les deux langues.

    Buscando Colisiones...
    Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
    Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
    Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
    Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
    Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
    Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
    Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
    Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
    Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
    Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
    Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
    Total de Colisiones: 11
    Total de Palabras  : 456976

qui n'est pas mauvais, 11 collisions sur 456 976 (hors cours en utilisant le plein 32 bits comme longueur de tableau).

exécuter le programme en utilisant 5 caractères, c'est-à-dire de' test_aaaaa 'à' test_zzzzz', aboutit en fait à une perte de mémoire dans la construction de la table. Ci-dessous est la sortie. 'No hay memoria para insertar XXXX (insertadas XXX) "signifie" Il ne reste plus de mémoire pour insérer XXX (XXX inséré)". Essentiellement malloc() échoué à ce point.

    No hay memoria para insertar 'test_epjcv' (insertadas 2097701).

    Buscando Colisiones...

    ...451 'colision' strings...

    Total de Colisiones: 451
    Total de Palabras  : 2097701

qui signifie seulement 451 collisions sur 2 097 701 cordes. Notez que dans aucune des occasions, il y a eu plus de 2 collisions par code. Que je confirme c'est un grand hachage pour moi, ce dont j'ai besoin est de convertir l'ID de connexion à un 40 bits identifiant unique pour l'indexation. Donc j'utilise ceci pour convertir les identifiants de connexion en Le hachage 32 bits et l'utilisation des 8 bits supplémentaires pour gérer jusqu'à 255 collisions par code, qui lookign sur les résultats d'essai serait presque impossible à générer.

Espère que ce sera utile à quelqu'un.

EDIT:

comme la boîte de test est AIX, Je l'exécute en utilisant LDR_CNTRL=MAXDATA=0X20000000 pour lui donner plus de mémoire et il exécute plus longtemps, les résultats sont ici:

Buscando Colisiones... Total de Colisiones: 2908 Total de Palabras: 5366384

C'est-à-dire 2908 après 5 366 384 essais!!

très IMPORTANT : compiler le programme avec-maix64( donc non signé long est 64 bits), le nombre de collisions est 0 pour tous les cas!!!

regardez GNU gperf .

la fonction de hachage Hsieh est assez bonne, et a quelques repères/comparaisons, comme une fonction de hachage général en C. Selon ce que vous voulez (ce n'est pas complètement évident), vous pourriez vouloir considérer quelque chose comme cdb à la place.

Bob Jenkins a de nombreuses fonctions de hachage disponibles , qui sont toutes rapides et ont de faibles taux de collision.

vous pouvez voir ce que .NET utilise sur la chaîne.Méthode GetHashCode () utilisant le réflecteur.

je me hasarderais une supposition que Microsoft a passé beaucoup de temps à l'optimiser. Ils ont également imprimé dans toute la documentation MSDN qu'elle est susceptible d'être modifiée en permanence. Donc clairement, c'est sur leurs "performances peaufiner radar" ;-)

serait assez trivial à porter sur C++ aussi j'aurais pensé.

il y a une bonne discussion dans ce question précédente

et un bel aperçu de la façon de choisir les fonctions de hachage, ainsi que des statistiques sur la distribution de plusieurs communs ici

décrit ici est une façon simple de mettre en œuvre vous-même: http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

Un extrait de la poste:

si disons que nous avons un jeu de caractères du capital anglais, les lettres, la longueur du jeu de caractères est de 26 où l'Un peut être représenté par le nombre 0, B par le nombre 1, C par le numéro 2 et ainsi de suite jusqu'à Z par le nombre de 25. Maintenant, quand nous voulons cartographier une chaîne de ce jeu de caractères à un nombre unique , nous effectuons la même conversion que nous l'avons fait dans le cas du format binaire

CRC-32 . Il ya environ un trillion de liens sur google pour elle.