fonction de hachage parfait

Je suis d'essayer de hachage les valeurs

10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0

J'ai besoin d'une fonction qui va de la carte à un tableau qui a une taille de 13 sans provoquer des collisions.

J'ai passé plusieurs heures à réfléchir à ce plus et googler et ne peut pas comprendre cela. Je n'ai pas une solution viable.

Comment pourrais-je aller sur la recherche d'une fonction de hachage de ce genre? J'ai joué avec gperf, mais je ne comprends pas vraiment et je ne pouvais pas obtenir les résultats que je cherchais.

Cela sonne comme des devoirs ... de toute façon, écrire un programme pour le faire pour vous! 🙂 Venir avec une formule générique, probablement à l'aide de pow ou une opération au niveau des bits, et le module (hey, il y a déjà un exemple dans une réponse!), et puis l'ordinateur de l'plunk, à travers des valeurs jusqu'à ce qu'il y a une "fonction de hachage parfait de match trouvé". Je l'ai fait pour mon CS devoirs il y a des années et il a très bien fonctionné 😉
On dirait que vous essayez de trouver une minimum parfaite de la fonction de hachage.
Sur la deuxième pensées... tu as 11 points de données. Pourquoi voulez-vous à la carte pour un tableau de taille 13? Quelle est la signification de ce numéro 13?
J'ai couru à vos numéros en "gperf" et il se produit un parfait fonction de hachage. Regardez le résultat que vous avez obtenu et vous verrez une fonction appelée 'hash' là.

InformationsquelleAutor gregghz | 2010-11-09

11

Trouvé Un

J'ai essayé un peu les choses et trouvé un semi-manuellement:
```
(n ^ 28) % 13
```
La semi-manuel a été la suivante ruby script que j'ai utilisé pour tester des fonctions candidates avec une gamme de paramètres:
```
t = [10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0]
(1..200).each do |i|
  t2 = t.map { |e| (e ^ i) % 13 }
  puts i if t2.uniq.length == t.length
end
```
InformationsquelleAutor DigitalRoss
24

si vous le connaissez touches, puis il est trivial pour produire un parfait fonction de hachage -
```
int hash (int n) {
  switch (n) {
    case 10:   return 0;
    case 100:  return 1;
    case 32:   return 2;
    //...
    default:   return -1;
  }
}
```
- +1 pour super simplicité
- Désolé, j'ai édité pour être en C++, le C++ tag a été retiré de la question. Vous pouvez revenir si vous le souhaitez.
- meh, c'était censé être C-comme des pseudo-code, c'est mieux maintenant, ty
- C'est effectivement une table de recherche. L'un des avantages d'une fonction de hachage est censé être: il permet une rapide évaluation de hit/miss qu'une table de recherche.
- cela est manifestement plus rapide que d'une table de recherche, même avec gcc -O0 c'est 5 fois plus rapide qu'une simple table linéaire de recherche sur ma machine, avec -O2 la recherche linéaire prend plus d'une seconde et time rapports un temps total de 0.00 pour 1 millions de recherches... Il est presque identique à la accepté de répondre à la vitesse de plus de 100 millions d'itérations avec -O0 et à moins de 0,2 s avec -O2. Et cette fonction de hachage est plus rapide si tout ce que vous devez faire est de travailler si la clé est présente/valide - hash(n)==-1 nécessite pas d'accès à la mémoire... et vous pouvez ajouter des touches avec la fonction reste parfait.
- Votre de hachage peut être plus rapide qu'une table de données de recherche de l'agred, mais ce n'est pas ce que je voulais dire. À préciser: Votre hash pourrait bien fonctionner pour ce petit ensemble de données, d'accord. Mais pour un ensemble de données de taille n, votre hash est O(n), alors que l'on a accepté la réponse est O(1). Le point d'une fonction de hachage est de fournir un O(1) solution. Ainsi, dans le cas particulier de l'ensemble de données de la question d'origine, votre solution est satisfaisante, mais, dans le cas plus général de la "recherche d'une fonction de hachage parfait pour les jeux de données" (en particulier, supérieure à un certain seuil), votre réponse n'est pas approprié.
- Mais un parfait fonction de hachage n'est pas logique pour rien de plus grand nombre de valeurs, et ce n'est pas une question sur les fonctions de hachage en général. Pourtant, c'est une méthode efficace pour efficace la mise en œuvre de fonctions de hachage parfait dans la plage où elles sont appropriées. En outre, le compilateur peut optimiser pour un saut de la table ou de l'arbre de recherche. Ce n'est pas nécessairement O(n) mais souvent O(1) ou O(log(n))
- "Mais un parfait fonction de hachage n'est pas logique pour quelque chose de plus grand que ce nombre de valeurs"—j'ai juste réussi à faire une [non-minimale] parfait fonction de hachage qui hachages mon fixe de l'ensemble de données de 154 valeurs de 16 bits en 8 bits de sortie, sans collisions. Ensuite, si je veux faire un minimum fonction de hachage parfait de cela, je peux le faire avec un supplément de 256 entrées look-up table).
- Une bonne optimisation du compilateur va dans le pire des cas produire un O(log(n)) de recherche pour trouver le bon interrupteur cas, qui va à l'encontre de l'objectif de l'aide de la fonction de hachage pour une table de hachage. En outre, vous pouvez dériver la fonction de hachage parfait au moment de l'exécution, parfois.
InformationsquelleAutor tobyodavies

Sur certaines plates-formes (par exemple, embedded), modulo est cher, donc % 13 est préférable d'éviter. Mais AND opération de bits n'est pas cher, et l'équivalent modulo une puissance de 2.

J'ai essayé d'écrire un programme simple (en Python) recherche pour un de hachage parfait de votre 11 points de données, à l'aide de formes simples comme ((x << a) ^ (x << b)) & 0xF (où & 0xF est équivalent à % 16, donnant un résultat dans l'intervalle 0..15, par exemple). J'ai été en mesure de trouver la suite de collision de hachage qui donne un indice dans l'intervalle 0..15 (exprimé en C macro):

#define HASH(x)    ((((x) << 2) ^ ((x) >> 2)) & 0xF)

Voici le programme en Python, j'ai utilisé:

data = [ 10, 100, 32, 45, 58, 126, 3, 29, 200, 400, 0 ]

def shift_right(value, shift_value):
    """Shift right that allows for negative values, which shift left
    (Python shift operator doesn't allow negative shift values)"""
    if shift_value == None:
        return 0
    if shift_value < 0:
        return value << (-shift_value)
    else:
        return value >> shift_value

def find_hash():
    def hashf(val, i, j = None, k = None):
        return (shift_right(val, i) ^ shift_right(val, j) ^ shift_right(val, k)) & 0xF

    for i in xrange(-7, 8):
        for j in xrange(i, 8):
            #for k in xrange(j, 8):
                #j = None
                k = None
                outputs = set()
                for val in data:
                    hash_val = hashf(val, i, j, k)
                    if hash_val >= 13:
                        pass
                        #break
                    if hash_val in outputs:
                        break
                    else:
                        outputs.add(hash_val)
                else:
                    print i, j, k, outputs

if __name__ == '__main__':
    find_hash()

InformationsquelleAutor Craig McQueen

3

Juste quelques quasi-analytiques divagations:

Dans votre ensemble de nombres, onze en tout, trois sont impairs et huit sont même.
En regardant les formes les plus simples de hachage - %13 - va donner la suite des valeurs de hachage:
10 - 3,
100 - 9,
32 - 6,
45 - 6,
58 - 6,
126 - 9,
3 - 3,
29 - 3,
200 - 5,
400 - 10,
0 - 0

Qui, bien sûr, est inutilisable en raison du nombre de collisions. Quelque chose de plus élaboré est nécessaire.

Pourquoi le mentionner?
Étant donné que les numéros sont si peu complexes - ou plutôt, "moins simple" - algorithme sera probablement plus lent que soit l'instruction switch ou (ce que je préfère), il suffit de parcourir un unsigned short/long vecteur de taille onze postes et à l'aide de l'index de la correspondance.

Pourquoi utiliser un vecteur de recherche?
1. Vous pouvez l'affiner en plaçant le plus souvent présentes les valeurs vers le début du vecteur.
2. Je suppose que le but est de le brancher dans l'index de hachage dans un interrupteur de nice, la numérotation séquentielle. Dans cette perspective, il semble un gaspillage de la première utilisation d'un interrupteur pour trouver l'index, puis de le brancher dans un autre interrupteur. Peut-être vous devriez envisager de ne pas utiliser le hachage à tous et allez directement à la finale de l'interrupteur?
3. Le commutateur version de hachage ne peut pas être affiné et, en raison de la grande disparité des valeurs, le compilateur pour générer un arbre de recherche binaire qui entraînera un grand nombre de comparaisons et à la condition que/autres sauts (particulièrement coûteux), qui prend du temps (j'ai supposé que vous êtes tourné vers le hachage pour sa rapidité) et nécessitent de l'espace.
4. Si vous voulez accélérer le vecteur de recherche de plus et utilisez un x86-système, vous pouvez mettre en œuvre un vecteur de recherche basé sur les instructions en assembleur repne scasw (courte)/repne scasd (long) qui sera beaucoup plus rapide. Après un temps de réglage de quelques instructions, vous trouverez la première entrée dans une instruction, et le dernier en onze suivie par quelques instructions de nettoyage. Cela signifie 5-10 instructions dans le meilleur des cas et 15-20 pire. Cela devrait battre l'interrupteur de la fonction de hachage à tous, mais peut-être un ou deux cas.
InformationsquelleAutor Olof Forshell
2

Bob Jenkins est un programme pour cela aussi: http://burtleburtle.net/bob/hash/perfect.html

Sauf si vous êtes très chanceux, il n'y a pas "gentil" fonction de hachage parfait pour un jeu de données. Parfait algorithmes de hachage généralement utiliser une simple fonction de hachage sur les touches (à l'aide d'assez de bits c'est donc sans collision) puis utiliser un tableau pour y mettre fin.

InformationsquelleAutor Fabian Giesen
0

J'ai fait une rapide vérification et à l'aide de la fonction de hachage SHA256 et ensuite de faire modulaire de la division par 13 travaillé quand je l'ai essayé dans Mathematica. En c++, cette fonction devrait être dans la bibliothèque openssl. Voir ce post.

Si vous faites beaucoup de hachage et de la recherche si, modulaire division est une jolie opération coûteuse pour le faire à plusieurs reprises. Il est une autre façon de cartographie de n bits en fonction de hachage dans un je-peu d'indices. Voir ce post par Michael Mitzenmacher sur la façon de le faire avec un peu de décalage de l'opération en C. Espère que ça aide.

InformationsquelleAutor Samsdram
0

Essayez les solutions suivantes qui correspond à votre n valeurs uniques indices entre 0 et 12
(1369%(n+1))%13

InformationsquelleAutor steviekm3

Vous devez vous connecter pour publier un commentaire.

Trouvé Un