À l'aide de hashcode pour un ID unique

Je travaille dans une java-based système où j'ai besoin de mettre un id pour certains éléments dans l'affichage visuel. Une catégorie d'éléments de Chaînes, j'ai donc décidé d'utiliser la Chaîne de caractères.hashCode() méthode pour obtenir un identifiant unique pour ces éléments.

Le problème que j'ai rencontré, cependant, est que le système que je suis en train de travailler dans borks si l'id est négatif et String.hashCode souvent renvoie des valeurs négatives. Une solution rapide est d'utiliser les Mathématiques.abs() autour de la hashcode appel à la garantie d'un résultat positif. Ce que je me demandais à propos de cette approche est de savoir quelles sont les chances que deux éléments distincts ayant le même hashcode?

Par exemple, si une chaîne de caractères retourne un hashcode de -10 et une autre chaîne de caractères retourne un hashcode de 10 une erreur se produit. Dans mon système, nous parlons des collections d'objets qui ne sont pas plus de 30 éléments de grandes généralement, donc je ne pense pas que ce serait vraiment un problème, mais je suis curieux de savoir ce que les mathématiques dit.

Si vous pouvez être sûr d'une petite limite supérieure du nombre d'objets que vous avez, vous pouvez vérifier pour une collision chaque fois que vous calculez un id. Si vous en trouvez un, vous pouvez ajouter 1 jusqu'à ce que vous avez obtenu une valeur unique, par exemple, en faisant attention de dépassement d'entier. Ou tout simplement faire les id 1,2,3, ...
Il n'y a pas de Math.abs(Integer.MIN_VALUE) comme -MIN_VALUE == MIN_VALUE == 0x8000_0000. Utilisation hc & Integer.MAX_VALUE au lieu de cela, si vous restez avec votre stratégie.

OriginalL'auteur IcedDante | 2014-01-26

  1. 11

    Des codes de hachage peuvent être considérés comme des nombres pseudo-aléatoires. Statistiquement, avec un positif int code de hachage de la probabilité d'une collision entre deux éléments atteint 50% lorsque la taille de la population est d'environ 54K (et 77K pour tout int). Voir Problème D'Anniversaire Probabilité De Table de collision probabilités de différents code de hachage de taille.

    Aussi, votre idée d'utiliser Math.abs() seul est erronée: Il ne renvoie pas toujours un nombre positif! En 2 du compliment de l'arithmétique, de la valeur absolue de Integer.MIN_VALUE est lui-même! Célèbre, le code de hachage de "polygenelubricants" est cette valeur.

    OriginalL'auteur Bohemian

  2. 7

    Les hachages sont pas unique, donc ils ne sont pas appropriés pour uniqueId.

    Que la probabilité de collision de hachage, vous avez pu lire sur le paradoxe d'anniversaire. En fait (d'après ce que je me souviens) lors de l'établissement à partir d'une distribution uniforme de N valeurs, vous devriez vous attendre de la collision après un tirage de $\sqrt(N)$ (vous pourriez obtenir collision beaucoup plus tôt). Le problème, c'est que Java est la mise en œuvre de hashCode (et surtout quand le hachage des chaînes courtes) ne marche pas à assurer une distribution uniforme, de sorte que vous aurez collision beaucoup plus tôt.

    Intéressant. Comme je l'ai dit, mes ensembles de données ne devrait pas être plus gros que 30 à 50 valeurs (et ce serait pour un système qui ne serait pas à l'échelle) donc je suppose que je serais en sécurité ici.
    Oui. Mais pour un système avec de 30 à 50 valeurs de tout autre système serait également le travail... et la plupart seraient plus en sécurité. Si vous ne prévoyez pas d'avoir plus de 50 valeurs, juste assingn id unique à la main.

    OriginalL'auteur jb.

  3. 3

    Vous pouvez déjà obtenir deux chaînes avec le même hashcode. Cela devrait être évident, si vous pensez que vous avez un nombre infini de chaînes et seulement 2^32 possible hashcodes.

    Vous venez de rendre un peu plus probable lors de la prise de la valeur absolue. Le risque est faible, mais si vous besoin un identifiant unique, ce n'est pas la bonne approche.

    OriginalL'auteur Denys Séguret

  4. 1

    Ce que vous pouvez faire lorsque vous avez seulement 30 à 50 valeurs comme vous l'avez dit enregistrer chaque Chaîne que vous obtenez dans une table de hachage avec une course contre la valeur:

    HashMap StringMap = new HashMap<String,Integer>();

StringMap.add("Test",1);
StringMap.add("AnotherTest",2);

    Vous pouvez obtenir votre ID unique par l'appel de cette:

    StringMap.get("Test"); //returns 1

    OriginalL'auteur Dakkaron