Hash: Comment ça marche?

1. Hasher signifie générer un nombre unique qui représente une valeur.
2. les Différents types de valeurs (Integer,String, etc) Utilisez des algorithmes différents pour calculer un hashcode.
3. HashMap et HashTable sont cartes; il s'agit d'une collection de clés unqiue, dont chacune est associée à une valeur.
   
   Java n'a pas de classe HashList. Une Table De Hachage Set est un ensemble de valeurs uniques.
4. obtenir un article d'un hashtable est constant-temps par rapport à la taille de la table.
   
   Le calcul d'un hachage n'est pas nécessairement constant en temps par rapport à la valeur qui est hachée.
   
   Par exemple, calculer le hachage d'une chaîne implique itérer la chaîne, et n'est pas du temps constant par rapport à la taille de la chaîne.
5. ce sont des choses que les gens doivent savoir.

1. le hachage est la transformation d'une entité donnée (en termes java - un objet) en un certain nombre (ou une séquence). La fonction de hachage n'est pas réversible, c'est - à-dire que vous ne pouvez pas obtenir l'objet original à partir du hachage. En interne, il est mis en œuvre (pour java.lang.Object en obtenant une adresse mémoire par la JVM.

2. l'adresse JVM est un détail sans importance. Chaque classe peut outrepasser le hashCode() méthode avec son propre algorithme. Modren Java IDEs permet de générer du bon les méthodes hashCode.

3. Hashtable et hashmap sont la même chose. Ils ont des paires de valeurs clés, où les clés sont hachées. Les listes de Hash et les hashsets ne stockent pas uniquement des clés de valeur.

4. temps Constant signifie que peu importe le nombre d'entrées dans le hashtable (ou toute autre collection), le nombre d'opérations nécessaires pour trouver un objet donné par sa clé est constant. C'est - à 1 ou proche de 1

5. C'est de base le matériel informatique, et il est supposé que tout le monde est familier avec lui. Je pense que google a précisé que le hashtable est la structure de données la plus importante en informatique.

je vais essayer de donner des explications simples du hachage et de son but.

tout d'abord, considérez une liste simple. Chaque opération (insérer, rechercher, supprimer) sur une telle liste aurait O(n) la complexité, ce qui signifie que vous devez analyser l'ensemble de la liste (ou la moitié, en moyenne) pour effectuer une telle opération.

le hachage est un moyen très simple et efficace de l'accélérer: considérons que nous divisons la liste entière en un ensemble de petites listes. Les éléments d'une liste aussi restreinte auraient quelque chose en commun, et ce quelque chose peut être déduit de la clé. Par exemple, en ayant une liste de noms, nous pourrions utiliser la première lettre comme la qualité qui choisira dans quelle petite liste regarder. De cette façon, en divisant les données par la première lettre de la clé, nous avons obtenu un simple hachage, qui serait capable de diviser la liste entière en ~30 listes plus petites, de sorte que chaque opération prendrait O(n)/30 Temps.

Cependant, nous pouvons noter que les résultats ne sont pas si parfaits. Premier, il n'y en a que 30 et on ne peut rien y changer. Deuxièmement, certaines lettres sont utilisées plus souvent que les autres, de sorte que l'ensemble Y ou Z sera beaucoup plus petit que l'ensemble A. Pour de meilleurs résultats, il est préférable de trouver un moyen de cloisonner les éléments dans des ensembles de grosso modo même taille. Comment pourrions-nous résoudre ce problème? C'est là que vous utilisez les fonctions de hachage. C'est une fonction qui est capable de créer un nombre arbitraire de partitions avec à peu près le même nombre d'éléments dans chaque. Dans notre exemple avec des noms, nous pourrions utiliser quelque chose comme

int hash(const char* str){
    int rez = 0;
    for (int i = 0; i < strlen(str); i++)
        rez = rez * 37 + str[i];
    return rez % NUMBER_OF_PARTITIONS;
};

ceci assurerait une distribution tout à fait uniforme et un nombre configurable d'ensembles (aussi appelé seaux).

de Considérer le problème de la recherche d'un tableau pour une valeur donnée. Si le tableau n'est pas trié, la recherche peut nécessiter l'examen de tous les éléments du tableau. Si le tableau est trié, nous pouvons utiliser la recherche binaire, et donc réduire la complexité de l'exécution du pire cas à O(log n). Nous pourrions recherche encore plus rapide si nous savons à l'avance l'indice de cette valeur se trouve dans le tableau. Supposons que nous ayons cette fonction magique qui nous indiquerait l'indice pour une valeur donnée. Avec cette fonction magique notre recherche est réduite à une seule sonde, ce qui nous donne une durée d'exécution constante O(1). Une telle fonction est appelée fonction de hachage . Une fonction de hachage est une fonction qui donne la clé, génère une adresse dans la table.

Qu'entendons-nous par Hachage, comment ça marche en interne ?

le hachage est la transformation d'une chaîne de caractères plus courte valeur de longueur fixe ou clé qui représente la chaîne originale. Il n'est pas d'indexation. Le cœur du hash est la table de hash. Il contient tableau d'éléments. Les tables de hachage contiennent un index de la clé de l'élément de données et utilisent cet index pour placer les données dans le tableau.

Quel algorithme de suivre ?

En mots simples la plupart des algorithmes de Hachage les travaux sur la logique "index = f(clé, arrayLength)"

enfin, pourquoi dans la plupart des interviews les questions Hash et LinkedList sont demandé, est-il logique spécifique pour à partir de tests de la personne interrogée la connaissance ?

C'est à propos de comment vous êtes bon au raisonnement logique. C'est la structure de données la plus importante que tous les programmeurs connaissent.