Les fondamentaux de tables de Hachage?

Question

Je suis assez confus sur les concepts de base d'une table de Hachage. Si je code un hachage comment pourrais-je commencer? Quelle est la différence entre une table de Hachage et juste un tableau normal?

En gros, si quelqu'un a répondu à cette question, je pense à toutes mes questions seront répondues: Si j'avais 100 numéros générés au hasard (comme des clés), comment pourrais-je mettre en œuvre une table de hachage et pourquoi serait-ce plus avantageux d'un tableau?

Pseudo-code ou de Java devrait être apprécié comme un outil d'apprentissage...

Answer 1

Les réponses ont permis de définir les tables de hachage et d'expliquer une partie de la théorie, mais je pense qu'un exemple peut vous aider à obtenir une meilleure sensation pour eux.

Quelle est la différence entre une table de hachage et juste un tableau normal?

Une table de hachage et un tableau sont deux structures qui vous permettent de stocker et récupérer des données. Les deux vous permettent de spécifier un index et de récupérer une valeur est associée. La différence, comme Daniel Spiewak de noter, c'est que les indices d'un tableau sont séquentielle, alors que ceux de la table de hachage sont basés sur la valeur des données qui leur sont associés.

Pourquoi voudrais-je utiliser une table de hachage?

Une table de hachage peut fournir un moyen très efficace pour rechercher des éléments dans de grandes quantités de données, notamment les données qui ne sont pas facilement accessibles. ("Grand" signifie ici ginormous, dans le sens qu'il faudrait beaucoup de temps pour effectuer une recherche séquentielle).

Si je code un hachage comment pourrais-je commencer?

Pas de problème. La façon la plus simple est d'inventer un arbitraire opération mathématique que vous pouvez effectuer sur les données, qui renvoie à un certain nombre N (généralement un entier). Utilisez ensuite ce nombre comme index dans un tableau de "compartiments" et de stocker vos données dans un seau #N. Le truc, c'est le choix d'une opération qui tend à placer les valeurs dans les différents compartiments dans une manière qui le rend facile pour vous de les trouver plus tard.

Exemple: Un grand centre commercial qui maintient une base de données de ses clients des voitures et des aires de stationnement, afin de permettre aux consommateurs de se rappeler où ils sont stationnés. La base de données stocke make, color, license plate, et parking location. En quittant le magasin, un client trouve sa voiture en entrant de la, sa composition et de la couleur. La base de données renvoie une (relativement courte) liste des plaques d'immatriculation et des places de parking. Une analyse rapide localise l'acheteur de la voiture.

Vous pourriez mettre en œuvre des ce avec une requête SQL:

SELECT license, location FROM cars WHERE make="$(make)" AND color="$(color)"

Si les données ont été stockées dans un tableau, qui est essentiellement juste une liste, vous pouvez imaginer la mise en œuvre de la requête par l'analyse d'un tableau pour toutes les entrées correspondantes.

D'autre part, imaginer une règle de hachage:

Ajouter le caractère ASCII codes de toutes les lettres de la marque et la couleur, le diviser par 100, et utiliser le reste comme la valeur de hachage.

Cette règle vous permet de convertir chaque élément à un nombre entre 0 et 99, essentiellement trier les données dans 100 seaux. Chaque fois qu'un client a besoin de localiser une voiture, vous pouvez hacher le faire et de couleur pour trouver l' un seau de 100 qui contient l'information. Vous avez immédiatement réduit la recherche d'un facteur 100!

Maintenant l'exemple d'énormes quantités de données, dire une base de données avec des millions d'entrées qui est recherché basé sur des dizaines de critères. Une "bonne" fonction de hachage va distribuer les données dans des seaux de façon à minimiser toute recherche supplémentaire, permettant de gagner un temps considérable.

Answer 2

Tout d'abord, vous devez comprendre ce qu'est une fonction de hachage est. Une fonction de hachage est une fonction qui prend une clé (par exemple, une chaîne de arbritrary longueur) et renvoie un nombre aussi unique que possible. La même clé doit toujours retourner le même hash. Vraiment une chaîne simple fonction de hachage en java pourrait ressembler

public int stringHash(String s) {
    int h = s.length();
    for(char c : s.toCharArray()) {
        h ^= c;
    }
    return h;
}

Vous pouvez étudier une bonne fonction de hachage à http://www.azillionmonkeys.com/qed/hash.html

Maintenant, le hash map utilise cette valeur de hachage de la place de la valeur dans un tableau. Simpliste méthode en java:

public void put(String key, Object val) {
    int hash = stringHash(s) % array.length;
    if(array[hash] == null) {
        array[hash] = new LinkedList<Entry<String, Object> >();
    }
    for(Entry e : array[hash]) {
        if(e.key.equals(key)){
            e.value = val;
            return;
        }
    }
    array[hash].add(new Entry<String, Object>(key, val));
}

(Cette carte met en application des clés uniques. Pas toutes les cartes en faire).

Il est possible pour les deux clés différentes pour hacher de la même valeur, ou les deux hachages à la carte pour le même index de tableau. Il existe plusieurs techniques pour traiter cette question. Le plus simple est d'utiliser une liste chaînée (ou arbre binaire) pour chaque index de tableau. Si la fonction de hachage est assez bon, vous n'aurez plus jamais besoin d'une recherche linéaire.

Maintenant à chercher une clé:

public Object get(String key) {
    int hash = stringHash(key) % array.length;
    if(array[hash] != null) {
        for(Entry e : array[hash]) {
            if(e.key.equals(key))
                return e.value;
        }
    }

    return null;
}

Answer 3

Tables de hachage sont associatifs. C'est une énorme différence de tableaux, qui sont les structures de données linéaires. Avec un tableau, vous pourriez faire quelque chose comme ceci:

int[] arr = ...
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i] + 1);
}

Remarquez comment vous obtenez un élément de la matrice par la spécification exacte décalage mémoire (i). Cette situation contraste avec les tables de hachage, qui vous permettent de stocker des paires clé/valeur, plus tard, de la récupération de la valeur basée sur la clé:

Hashtable<String, Integer> table = new Hashtable<String, Integer>();
table.put("Daniel", 20);
table.put("Chris", 18);
table.put("Joseph", 16);

Avec le tableau ci-dessus, nous pouvons faire l'appel suivant:

int n = table.get("Chris");

...et être assuré que l' n seront évalués à 18.

Je pense que ce sera probablement répondre à la plupart de vos questions. La mise en place d'une table de hachage est assez intéressant ce sujet, l'un qui Wikipedia adresses passablement bien.

Answer 4

"Je suis plus intéressé par la façon dont les Tables de Hachage de chercher la clé et la façon dont la clé est générée."

1. Le hachage transforme un objet clé à un numéro. Ceci est appelé le "hachage" -- il fait un hachage de l'objet. Voir La Fonction De Hachage. En additionnant les octets d'une chaîne, par exemple, est une norme de hachage technique. Vous calculez la somme modulo 2^{de 32} à conserver la valeur de hachage à une taille gérable. Hachage donne toujours la même réponse. Ce est O(1).

2. Le nombre vous donne un "slot" dans la table de hachage. Compte tenu de l'arbitraire d'un objet clé, la valeur de hachage calcule une valeur de hachage. La valeur de hachage vous donne ensuite la fente de la table. Habituellement mod( hash, table size ). Ce est O(1), aussi.

C'est la solution générale. Deux calculs numériques et que vous avez passé de l'arbitraire de l'objet en tant que clé pour objet arbitraire de la valeur. Peu de choses peuvent être aussi rapide.

La transformation de l'objet à la valeur de hachage qui se passe dans l'un de ces moyens.

1. Si c'est un "primitif" de l'objet de 4 octets, puis l'objet natif de valeur est un nombre.

2. L'objet de l'adresse est de 4 octets, l'objet de l'adresse peut être utilisée comme une valeur de hachage.

3. Une simple fonction de hachage (MD5, SHA1, peu importe) accumule les octets de l'objet pour créer un 4-nombre d'octet. L'avancée des hachages ne sont pas de simples sommes d'octets, une simple somme ne correspond pas à l'original de tous les bits d'entrée assez suffisant.

La fente dans la table de hachage est mod( nombre, la taille du tableau ).

Si ce logement a la valeur désirée, vous avez terminé. Si ce n'est pas la valeur souhaitée, vous avez besoin de chercher ailleurs. Il existe plusieurs types de sondage algorithmes de chercher une place libre dans la table. Linéaire est une recherche simple pour la prochaine place libre. Quadratique est non-linéaire en sautillant autour de la recherche d'un slot libre. Un générateur de nombre aléatoire (avec un fixe de semences) peut être utilisé pour générer une série de sondes qui vont se répandre données uniformément, mais de façon arbitraire.

Le sondage algorithmes ne sont pas O(1). Si la table est assez grande, les chances de collision sont faibles, et des sondes n'a pas d'importance. Si la table est trop petite, alors les collisions peuvent se produire et le sondage qui se passe. À ce point, ça devient une question de "réglages et les ajustements" à la solde de sondage et taille de la table afin d'optimiser les performances. Habituellement, nous venons de rendre le tableau plus grand.

Voir La Table De Hachage.

Answer 5

Quelque chose que je n'ai pas vu spécialement de noter encore:

Le point de l'utilisation d'une table de hachage sur un tableau est la performance.

Une itération à travers un tableau était généralement n'importe où à partir de O(1) O(x), où x est le nombre d'éléments dans le tableau. Cependant, le temps de trouver votre article sera extrêmement variable, particulièrement si nous parlons de centaines de milliers d'éléments dans le tableau.

Un correctement pondérée de la table de hachage a généralement une quasi constante de temps d'accès d'un peu plus de O(1), peu importe combien d'articles sont dans la table de hachage.