Exemple d'analyse de table de hachage en Java

1, concept

Dans la structure séquentielle et l'arbre équilibré, il n'y a pas de relation correspondante entre le code clé de l'élément et son emplacement de stockage, donc lors de la recherche d'un élément, vous devez procéder à plusieurs comparaisons du code clé. La complexité temporelle de la recherche séquentielle est O(N). Dans un arbre équilibré, c'est la hauteur de l'arbre, c'est-à-dire O( ). L'efficacité de la recherche dépend du nombre de comparaisons d'éléments au cours du processus de recherche.

Méthode de recherche idéale : vous pouvez obtenir l'élément à rechercher directement à partir du tableau en une seule fois sans aucune comparaison. Si vous construisez une structure de stockage et utilisez une certaine fonction (hashFunc) pour établir une relation de mappage un à un entre l'emplacement de stockage de l'élément et son code clé, vous pouvez alors trouver rapidement l'élément via cette fonction pendant la recherche.

Lors de la saisie de la structure :

Insérer un élément

Selon le code clé de l'élément à insérer, cette fonction calcule l'emplacement de stockage de l'élément Et stockez-le en fonction de cet emplacement

Rechercher des éléments

Effectuer le même calcul sur le code clé de l'élément, utiliser la valeur de fonction obtenue comme emplacement de stockage de l'élément, et appuyez dans la structure Comparez les éléments à cette position. Si les codes clés sont égaux, la recherche est réussie

Par exemple : ensemble de données {1, 7, 6, 4, 5, 9. };

Hash La fonction est définie comme : hash(key) = key %capacité est la taille totale de l'espace sous-jacent pour stocker les éléments.

2, conflit-évitement

Tout d'abord, nous devons préciser que parce que la capacité du sous-jacent Le tableau de notre table de hachage est souvent inférieur au nombre réel de mots-clés à stocker, ce qui entraîne un problème. L'apparition de conflits est inévitable, mais ce que nous pouvons faire est de réduire autant que possible le taux de conflits.

3, conception de la fonction de hachage pour éviter les conflits

Fonction de hachage commune

Méthode de personnalisation directe--(couramment utilisée)

# 🎜🎜# Prendre une fonction linéaire du mot-clé comme adresse de hachage : Hash (Clé) = A*Key + B Avantages : Simple et uniforme Inconvénients : Besoin de connaître la distribution des mots-clés à l'avance Scénario d'utilisation : Adapté à une recherche petite et continue case

Méthode de reste en laissant la division--(couramment utilisée)

Supposons que le nombre d'adresses autorisées dans la table de hachage soit m, choisissez-en une qui n'est pas supérieure à m, mais est le plus proche ou égal à Le nombre premier p de m est utilisé comme diviseur, et selon la fonction de hachage : Hash(key) = key% p(pMéthode de mise au carré--(Comprendre)

Supposons que le mot-clé soit 1234, le carré est 1522756, extrayez les 3 chiffres du milieu 227 comme adresse de hachage ; un autre exemple est le mot-clé ; 4321, carré c'est 18671041, extraire les 3 bits du milieu 671 (ou 710) est plus adapté comme méthode de hachage d'adresse au carré : la distribution des mots-clés n'est pas connue, et le nombre de bits n'est pas très grand

#🎜 🎜#4, ajustement du facteur de charge pour éviter les conflits

Démonstration approximative de la relation entre le facteur de charge et le taux de conflit

Donc, lorsque le taux de conflits atteint un niveau intolérable, nous devons réduire le taux de conflits déguisés en réduisant le facteur de charge. , On sait que le nombre de mots-clés dans la table de hachage est immuable, alors tout ce que nous pouvons ajuster est la taille du tableau dans la table de hachage.

5, hachage fermé-résolution de conflit

Hashage fermé : aussi appelé méthode d'adressage ouverte, lorsqu'un conflit de hachage survient, si la table de hachage n'est pas pleine, indiquant qu'il y a doit être une position vide dans la table de hachage, alors la clé peut être stockée dans la position vide "suivante" dans la position de conflit.

①Détection linéaire

Par exemple, dans le scénario ci-dessus, vous devez insérer l'élément 44. Tout d'abord, calculez l'adresse de hachage via la fonction de hachage, donc l'indice est 4. 44 devrait théoriquement être Insert à cette position, mais un élément avec une valeur de 4 est déjà placé à cette position, c'est-à-dire qu'un conflit de hachage se produit. Détection linéaire : en partant de la position où le conflit se produit, détectez vers l'arrière jusqu'à ce que la prochaine position vide soit trouvée.

Insert

Obtenez la position de l'élément à insérer dans la table de hachage via la fonction de hachage S'il n'y a aucun élément dans la position, insérez directement le nouvel élément. S'il y a un élément dans la position, lorsqu'un conflit de hachage se produit, utilisez la détection linéaire pour trouver la prochaine position vide et insérez le nouvel élément

When en utilisant le hachage fermé pour gérer les conflits de hachage, vous ne pouvez pas le faire avec désinvolture. Supprimer les éléments existants dans la table de hachage La suppression directe des éléments affectera la recherche d'autres éléments. Par exemple, si vous supprimez directement l'élément 4, la recherche de 44 peut être affectée. Par conséquent, le sondage linéaire utilise une pseudo-suppression marquée pour supprimer un élément.

②Deuxième détection

Le défaut de la détection linéaire est que des données contradictoires sont empilées, ce qui est lié à la recherche de la prochaine position vide, car la façon de trouver la position vide est de revenir en arrière. Trouvez-les un par un, donc afin d'éviter ce problème de détection secondaire, la méthode pour trouver la prochaine position vide est : = ( + )% m, ou : = ( - )% m. Parmi eux : i = 1,2,3..., est la position calculée par la fonction de hachage Hash(x) sur le code clé de l'élément, et m est la taille du tableau. Pour la version 2.1, si vous souhaitez insérer 44, un conflit se produit. La situation résolue est la suivante :

La recherche montre que lorsque la longueur de la table est un. nombre premier et la table est chargée. Lorsque le facteur a ne dépasse pas 0,5, de nouvelles entrées peuvent définitivement être insérées, et aucune position ne sera sondée deux fois. Par conséquent, tant qu’il y aura des positions à moitié vides dans la table, il n’y aura pas de problème de table pleine. Lors de la recherche, vous n'avez pas besoin de considérer que la table est pleine, mais lors de l'insertion, vous devez vous assurer que le facteur de charge a de la table ne dépasse pas 0,5. S'il dépasse, vous devez envisager d'augmenter la capacité.

6, conflit-résolution-open hash/hash bucket

La méthode de hachage ouvert est également appelée méthode d'adresse de chaîne (méthode de chaîne ouverte). Tout d'abord, utilisez le code clé. set La fonction de hachage calcule l'adresse de hachage. Les codes clés avec la même adresse appartiennent au même sous-ensemble. Chaque sous-ensemble est appelé un compartiment. Les éléments de chaque compartiment sont liés via une seule liste chaînée. la liste chaînée est stockée dans la table de hachage.

 
     static class Node {
         public int key;
         public int val;
         public Node next;
 
         public Node(int key, int val) {
             this.key = key;
             this.val = val;
         }
     }
 
     private Node[] array;
     public int usedSize;
 
     public HashBucket() {
         this.array = new Node[10];
         this.usedSize = 0;
     }

#🎜🎜 # # 🎜🎜#

 public void put(int key,int val){
        int index = key % this.array.length;
        Node cur = array[index];
        while (cur != null){
            if(cur.val == key){
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //头插法
         Node node = new Node(key,val);
        node.next = array[index];
        array[index] = node;
        this.usedSize++;
        if(loadFactor() >= 0.75){
            resize();
        }
    }

public int get(int key) {
         //以什么方式存储的  那就以什么方式取
         int index = key % this.array.length;
         Node cur = array[index];
         while (cur != null) {
             if(cur.key == key) {
                 return cur.val;
             }
             cur = cur.next;
         }
         return -1;//
     }

public void resize(){
 
        Node[] newArray = new Node[2*this.array.length];
        for (int i = 0; i < this.array.length; i++){
            Node cur = array[i];
            Node curNext = null;
            while (cur != null){
 
                curNext = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[i];
                newArray[i] = cur;
                cur = curNext.next;
                cur = curNext;
 
            }
        }
        this.array = newArray;
    }

7 , code complet # 🎜🎜 #

 class HashBucket {
 
     static class Node {
         public int key;
         public int val;
         public Node next;
 
         public Node(int key, int val) {
             this.key = key;
             this.val = val;
         }
     }
 
     private Node[] array;
     public int usedSize;
 
     public HashBucket() {
         this.array = new Node[10];
         this.usedSize = 0;
     }
 
     public void put(int key,int val) {
         //1、确定下标
         int index = key % this.array.length;
         //2、遍历这个下标的链表
         Node cur = array[index];
         while (cur != null) {
             //更新val
             if(cur.key == key) {
                 cur.val = val;
                 return;
             }
             cur = cur.next;
         }
         //3、cur == null   当前数组下标的 链表  没要key
         Node node = new Node(key,val);
         node.next = array[index];
         array[index] = node;
         this.usedSize++;
         //4、判断  当前 有没有超过负载因子
         if(loadFactor() >= 0.75) {
             //扩容
             resize();
         }
     }
 
     public int get(int key) {
         //以什么方式存储的  那就以什么方式取
         int index = key % this.array.length;
         Node cur = array[index];
         while (cur != null) {
             if(cur.key == key) {
                 return cur.val;
             }
             cur = cur.next;
         }
         return -1;//
     }
 
 
     public double loadFactor() {
         return this.usedSize*1.0 / this.array.length;
     }
 
 
 
    public void resize(){
 
        Node[] newArray = new Node[2*this.array.length];
        for (int i = 0; i < this.array.length; i++){
            Node cur = array[i];
            Node curNext = null;
            while (cur != null){
 
                curNext = cur.next;
                int index = cur.key % newArray.length;
                cur.next = newArray[i];
                newArray[i] = cur;
                cur = curNext.next;
                cur = curNext;
 
            }
        }
        this.array = newArray;
    }
 
 
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!