Ce qui est une bonne fonction de hachage ?

Question

Ce qui est une bonne fonction de Hachage? J'ai vu beaucoup de fonction de hachage et des applications dans mon les structures de données de cours à l'université, mais j'ai surtout eu qu'il est assez difficile de faire une bonne fonction de hachage. En règle générale, pour éviter les collisions mon professeur a dit que:

function Hash(key)
  return key mod PrimeNumber
end

(mod est l'opérateur % en C et langues similaires)

avec le premier numéro de la taille de la table de hachage. J'obtiens c'est une assez bonne fonction pour éviter les collisions et un rapide, mais comment puis-je faire de mieux? Est-il mieux de fonctions de hachage pour les clés de chaîne contre les touches numériques?

Answer 1

Il n'y a pas une telle chose comme une "bonne fonction de hachage" universel hachages (ed. oui, je sais qu'il ya une telle chose comme "universel hachage" mais ce n'est pas ce que je voulais dire). En fonction du contexte, des critères différents de déterminer la qualité de hachage. Deux personnes déjà mentionné SHA. C'est un hachage cryptographique et il n'est pas du tout bon pour les tables de hachage qui tu veux sans doute dire.

Les tables de hachage ont des exigences très différentes. Mais encore, la recherche d'une bonne fonction de hachage est universellement dur, parce que les différents types de données exposer les différentes informations qui peuvent être haché. En règle générale, il est bon de considérer toutes les informations d'un type en va de même. Ce n'est pas toujours facile, ni même possible. Pour des raisons de statistiques (et donc de la collision), il est également important de générer une bonne répartition sur le problème de l'espace, c'est à dire tous les objets possibles. Cela signifie que lorsque le hachage des nombres entre 100 et 1050, c'est pas bon de laisser le plus significatif à jouer un grand rôle dans la table de hachage parce que pour ~ 90% des objets, ce chiffre sera de 0. Il est beaucoup plus important que les trois derniers chiffres de déterminer la valeur de hachage.

De même, lorsque les chaînes de hachage, il est important de considérer tous les personnages – sauf quand elle est connue à l'avance que les trois premiers caractères de toutes les chaînes doivent être les mêmes; considérant ces choses, alors est un déchet.

C'est en fait l'un des cas où, je conseille de lire ce que Knuth est-à-dire dans L'Art de la Programmation Informatique, vol. 3. Une autre bonne lecture est Julienne Walker est L'Art de Hachage.

Answer 2

Pour faire des recherches de table de hachage « normal » sur pratiquement n’importe quel type de données - celui-ci par Paul Hsieh est le meilleur que j’ai jamais utilisé.

http://www.azillionmonkeys.com/QED/Hash.html

Si vous vous souciez par chiffrement sécurisé ou toute autre chose plus avancées, puis YMMV. Si vous voulez juste une fonction de hachage kick ass généraliste pour une recherche de table de hachage, c’est ce que vous recherchez.

Answer 3

Il y a deux principaux objectifs de fonctions de hachage:

• pour disperser les points de données de manière uniforme sur n bits.
• afin d'identifier en toute sécurité les données d'entrée.

Il est impossible de recommander un hachage sans savoir ce que vous l'utilisez pour.

Si vous êtes juste de faire une table de hachage dans un programme, alors vous n'avez pas besoin de s'inquiéter sur la façon réversible ou de piratable l'algorithme est... SHA-1 ou AES est complètement inutile pour cela, vous feriez mieux d'utiliser une variation de la FNV. FNV permet une meilleure dispersion (et donc moins de collisions) qu'un simple premier mod comme vous l'avez dit, et c'est plus adaptable aux variables d'entrée tailles.

Si vous utilisez les codes de hachage à se cacher et à authentifier l'information du public (tels que le hachage d'un mot de passe, ou un document), vous devez utiliser l'un des principaux algorithmes de hachage approuvés par l'examen du public. La Fonction de Hachage Salon est un bon endroit pour commencer.

Answer 4

Je dirais que la règle principale est ne pas de rouler. Essayez d’utiliser quelque chose qui a été testée, par exemple, SHA-1 ou quelque chose dans ce sens.

Answer 5

Une bonne fonction de hachage a les propriétés suivantes:

1. Étant donné une valeur de hachage d'un message, il est mathématiquement impossible pour un attaquant de trouver un autre message d'erreur tel que leurs empreintes sont identiques.

2. Une paire de message, m' et m, il est mathématiquement impossible de trouver deux tel que h(m) = h(m')

Les deux cas ne sont pas les mêmes. Dans le premier cas, il existe un pré-existante de hachage que vous essayez de trouver une collision. Dans le second cas, vous essayez de trouver toutes les deux messages qui entrent en collision. La deuxième tâche est beaucoup plus facile en raison de l'anniversaire "paradoxe."

Où la performance n'est pas un problème, vous devriez toujours utiliser une fonction de hachage sûre. Il y a très intelligent attaques qui peuvent être effectuées en forçant les collisions dans une table de hachage. Si vous utilisez quelque chose de fort dès le début, vous vous protéger contre ces.

N'utilisez pas de MD5 ou SHA-1 dans les nouvelles conceptions. La plupart des cryptographes, moi y compris, serait de considérer cassé. Le principe de la source de la faiblesse de ces modèles est que la deuxième propriété, qui je l'ai souligné ci-dessus, ne détient pas pour ces constructions. Si un attaquant peut générer deux messages m et m', que les deux de hachage à la même valeur qu'ils peuvent utiliser ces messages contre vous. SHA-1 et MD5 souffrent également de message d'extension attaques, qui peuvent mortellement affaiblir votre demande si vous ne faites pas attention.

Plus moderne de hachage comme le Jacuzzi est un meilleur choix. Il ne souffre pas de ces message d'extension des attaques et utilise les mêmes mathématiques AES utilise pour prouver la sécurité contre les diverses attaques.

Espérons que ça aide!