fonction de hachage fournissant uint unique à partir d'un nombre entier paire de coordonnées

Question

Le problème en général: J'ai un grand espace point 2d, peu peuplé avec des points. Pensez-y comme une grande toile blanche parsemée de points noirs. Je dois parcourir et rechercher à travers ces points beaucoup. La toile (espace point) peut être énorme, en bordure des limites int et sa taille est inconnue avant de les points là-bas.

Cela m'a amené à l'idée de hash:

Idéal: J'ai besoin d'une fonction de hachage en prenant un point 2D, un retour uint32 unique. Alors qu'aucune collision ne peut se produire. Vous pouvez supposer que le nombre de points sur la toile est facilement dénombrables par uint32.

IMPORTANT: Il est impossible de connaître la taille de la toile au préalable (Il peut même changer), si des choses comme

* canvaswidth y + x

sont malheureusement hors de question.

J'ai essayé aussi un très naïf

abs (x) + abs (y)

mais qui produit trop de collisions.

compromis: Une fonction de hachage qui fournit les clés avec un très faible probabilité de collision.

Toute personne d'idées? Merci pour toute aide.

Cordialement, Andreas T.

Edit: Je devais changer quelque chose dans le texte de la question: J'ai changé l'hypothèse « capable de compter le nombre de points de la toile avec uint32" en « capable de compter les points sur la toile (ou le nombre de paires de coordonnées pour stocker » par uint32. Ma question originale n'a pas beaucoup de sens, parce que je l'aurais eu un sqrt (max (uint32)) xsqrt (max (uint32)) de toile de taille, qui est unique représentable par un décalage de 16 bits et OR.

J'espère que cela est ok, car toutes les réponses font encore plus de sens avec les hypothèses mises à jour

Désolé pour cela.

Answer 1

une fonction de hachage qui est garanti sans risque de collision n'est pas une fonction de hachage:)

Au lieu d'utiliser une fonction de hachage, vous pouvez envisager d'utiliser des arbres de partition de l'espace binaire (BSPs) ou XY arbres (étroitement liés).

Si vous voulez hash deux en un seul uint32 de uint32, ne pas utiliser des choses comme Y & 0xFFFF parce que les rejets de la moitié des bits. Faites quelque chose comme

(x * 0x1f1f1f1f) ^ y

(vous avez besoin de transformer l'une des variables pour vous assurer que la fonction de hachage n'est pas commutative)

Answer 2

de paires

   n = ((x + y)*(x + y + 1)/2) + y

pourrait être intéressant, car il est le plus proche de votre canvaswidth originale * y + x mais fonctionnera pour tout x ou y. Mais pour un monde réel int32 hachage, plutôt que d'un mappage de paires d'entiers en entiers, vous êtes probablement mieux avec une manipulation de bits tel que Bob Jenkin mélanger et appeler cela avec x, y et un sel.

Answer 3

Comme Emil, mais poignées déversoirs en x d'une manière 16 bits qui produit moins de collisions, et prend moins d'instructions pour calculer:

hash = ( y << 16 ) ^ x;

Answer 4

Votre "idéal" est impossible.

Vous voulez une application (x, y) -> i où x, y, et moi toutes les quantités 32 bits, qui est garanti de ne pas générer des valeurs en double de i

.

Voici pourquoi: supposons qu'il y ait un hachage de fonction () de telle sorte que hachage (x, y) donne différentes valeurs entières. Il y a 2 valeurs ^ 32 (environ 4 milliards) pour x et 2 ^ 32 valeurs de y. hachage So (x, y) a 2 ^ 64 (environ 16 millions billion) résultats possibles. Mais il n'y a que 2 ^ 32 valeurs possibles dans un int 32 bits, de sorte que le résultat de hachage () ne rentre pas dans un int 32 bits.

Voir aussi http://en.wikipedia.org/wiki/Counting_argument

En général, vous devriez toujours concevoir vos structures de données pour traiter les collisions. (À moins que vos hash sont très longs (au moins 128 bits), très bon (utiliser les fonctions de hachage cryptographique), et vous vous sentez chanceux).

Answer 5

Peut-être?

hash = ((y & 0xFFFF) << 16) | (x & 0xFFFF);

fonctionne tant que x et y peuvent être stockées en tant que nombres entiers de 16 bits. Aucune idée sur le nombre de collisions cela provoque des entiers plus grands, cependant. Une idée pourrait être d'utiliser toujours le même schéma, mais le combiner avec un système de compression, par exemple en prenant le module de 2 ^ 16.

Answer 6

Si vous pouvez faire = ((y & 0xffff) << 16) | (X & 0xffff), vous pouvez ensuite appliquer un mélange réversible 32 bits à un, comme Thomas Wang

uint32_t hash( uint32_t a)
    a = (a ^ 61) ^ (a >> 16);
    a = a + (a << 3);
    a = a ^ (a >> 4);
    a = a * 0x27d4eb2d;
    a = a ^ (a >> 15);
    return a;
}

De cette façon, vous obtenez un résultat aléatoire à la recherche plutôt que de bits de poids fort d'une dimension et bits de poids faible de l'autre.

Answer 7

Vous pouvez faire

a >= b ? a * a + a + b : a + b * b

pris d'ici .

Cela fonctionne pour les points dans le plan positif. Si vos coordonnées peuvent être dans l'axe négatif aussi, alors vous devez faire:

A = a >= 0 ? 2 * a : -2 * a - 1;
B = b >= 0 ? 2 * b : -2 * b - 1;
A >= B ? A * A + A + B : A + B * B;

Mais pour limiter la sortie à uint vous devrez garder une limite supérieure pour vos entrées. et si oui, alors il se trouve que vous connaissez les limites. En d'autres termes dans la programmation de son impossible d'écrire une fonction sans avoir une idée sur le type entier vos entrées et la sortie peut être et si oui, il y aura certainement une limite supérieure et limite inférieure pour chaque type entier.

public uint GetHashCode(whatever a, whatever b)
{
    if (a > ushort.MaxValue || b > ushort.MaxValue || 
        a < ushort.MinValue || b < ushort.MinValue)
    {    
        throw new ArgumentOutOfRangeException();
    }

    return (uint)(a * short.MaxValue + b); //very good space/speed efficiency
    //or whatever your function is.
}

Si vous voulez une sortie à proprement parler uint pour une plage inconnue d'entrées, alors il y aura quantité raisonnable de collisions en fonction de cette plage. Ce que je suggère est d'avoir une fonction qui peut déborder mais décochée . La solution de Emil est grande, en C #:

return unchecked((uint)((a & 0xffff) << 16 | (b & 0xffff))); 

Voir Mapping deux entiers à un, d'une manière unique et déterministe pour une pléthore d'options ..

Answer 8

Selon votre cas d'utilisation, il pourrait être possible d'utiliser un quadtree et remplacer les points avec la chaîne de noms de branche. Il est en fait une représentation parcimonieuse pour les points et aura besoin d'une structure quadtree personnalisée qui étend la toile en ajoutant des branches lorsque vous ajoutez des points hors de la toile, mais il évite les collisions et vous aurez des avantages comme des recherches les plus proches voisins rapides.

Answer 9

Vous pouvez diviser récursive votre plan XY dans les cellules, puis diviser ces cellules en sous-cellules, etc.

Gustavo Niemeyer a inventé en 2008 son système de géocodage geohash.

open source d'Amazon Bibliothèque Geo calcule le hachage pour toute coordonnée longitude latitude. La valeur résultante geohash est un nombre 63 bits. La probabilité de collision dépend de la résolution du hachage. Si deux objets sont plus proches que la résolution intrinsèque, le hachage calculée sera identique

En savoir plus:

https://en.wikipedia.org/wiki/Geohash https: / /aws.amazon.com/fr/blogs/mobile/geo-library-for-amazon-dynamodb-part-1-table-structure/ https://github.com/awslabs/dynamodb-geo

Answer 10

Si vous utilisez déjà des langues ou des plates-formes que tous les objets (même les primitifs comme des entiers) a intégré dans les fonctions de hachage mises en œuvre (plate-forme Java langages comme Java, langages de la plate-forme .NET, comme C #. Et d'autres comme Python, Ruby, etc ). Vous pouvez utiliser des valeurs de hachage intégrées en un bloc de construction et d'ajouter votre « saveur hashing » dans le mélange. Comme:

// C# code snippet 
public class SomeVerySimplePoint { 

public int X;
public int Y;

public override int GetHashCode() {
   return ( Y.GetHashCode() << 16 ) ^ X.GetHashCode();
}

}

Et ayant également des cas de test comme « ensemble prédéfini millions de points » en cours d'exécution contre chaque hachage possible de générer comparaison de l'algorithme pour différents aspects tels que, le temps de calcul, mémoire nécessaire, le nombre clé de collision, et les cas de bord (trop grandes ou trop petites valeurs) peut être à portée de main.

Answer 11

le hachage Fibonacci fonctionne très bien pour les paires d'entiers

multiplicateur 0x9E3779B9

autre mot tailles de 1 / phi = (sqrt (5) -1) / 2 * 2 ^ w tour à impair

a1 + a2 * multiplicateur

cela donnera des valeurs très différentes pour les paires ensemble proches

Je ne sais pas le résultat avec toutes les paires