Comment voulez-vous mettre en œuvre une table de hachage dans le langage x?

Le point de cette question est de recueillir une liste d'exemples de la table de hachage des implémentations à l'aide de tableaux dans les différentes langues. Il serait bien aussi si quelqu'un pouvait jeter dans un joli aperçu détaillé de la façon dont ils fonctionnent, et ce qui se passe avec chaque exemple.

Edit:

Pourquoi ne pas simplement utiliser le construit dans les fonctions de hachage dans votre langue spécifique?

Parce que nous devons savoir comment les tables de hachage de travail et être capable de les mettre en œuvre. Cela peut ne pas sembler un super sujet important, mais de savoir comment l'un des plus utilisés structures de données des œuvres semble assez important pour moi. Si c'est pour devenir le wikipedia de programmation, puis ceux-ci sont quelques-uns des types de questions que je vais venir ici pour. Je ne suis pas à la recherche d'un CS livre écrit ici. Je pourrais aller traction introduction aux Algorithmes de l'étagère et de lire le chapitre sur les tables de hachage et d'obtenir ce type d'information. Plus précisément ce que je suis à la recherche pour sont exemples de code. Pas seulement pour moi en particulier, mais aussi pour d'autres qui auraient peut-être un jour être à la recherche d'informations similaires et de tomber sur cette page.

Pour être plus précis: Si vous avait pour les mettre en œuvre, et ne pouvait pas utiliser les fonctions intégrées, comment le feriez-vous?

Vous n'avez pas besoin de mettre le code ici. Mettre dans pastebin et juste un lien.

L'idée est DONC de organiquement devenir le Wikipedia de programmation. Ne le forcez pas à des questions; ça sent le karma de l'agriculture.

InformationsquelleAutor mk. | 2008-08-24

Une table de hachage une structure de données qui permet la recherche d'éléments dans les temps constant. Il fonctionne par une valeur de hachage et la conversion de cette valeur à un décalage dans un tableau. Le concept d'une table de hachage est assez facile à comprendre, mais la mise en œuvre est évidemment plus difficile. Je ne suis pas le collage de l'ensemble de la table de hachage ici, mais en voici quelques extraits d'une table de hachage, j'ai fait en C il y a quelques semaines...

L'une des bases de la création d'une table de hachage est d'avoir une bonne fonction de hachage. J'ai utilisé le djb2 fonction de hachage dans ma table de hachage:

int ComputeHash(char* key)
{
    int hash = 5381;
    while (*key)
    hash = ((hash << 5) + hash) + *(key++);
    return hash % hashTable.totalBuckets;
}

Puis vient le code lui-même pour créer et gérer les seaux dans le tableau

typedef struct HashTable{
    HashTable* nextEntry;
    char*      key;
    char*      value;
}HashBucket;

typedef struct HashTableEntry{
    int totalBuckets;       //Total number of buckets allocated for the hash table
    HashTable** hashBucketArray; //Pointer to array of buckets
}HashTableEntry;
HashTableEntry hashTable;

bool InitHashTable(int totalBuckets)
{
    if(totalBuckets > 0)
    {
        hashTable.totalBuckets = totalBuckets;
        hashTable.hashBucketArray = (HashTable**)malloc(totalBuckets * sizeof(HashTable));
        if(hashTable.hashBucketArray != NULL)
        {
            memset(hashTable.hashBucketArray, 0, sizeof(HashTable) * totalBuckets);
            return true;
        }
    }
    return false;
}

bool AddNode(char* key, char* value)
{
    int offset = ComputeHash(key);
    if(hashTable.hashBucketArray[offset] == NULL)
    {
        hashTable.hashBucketArray[offset] = NewNode(key, value);
        if(hashTable.hashBucketArray[offset] != NULL)
            return true;
    }

    else
    {
        if(AppendLinkedNode(hashTable.hashBucketArray[offset], key, value) != NULL)
            return true;
    }
    return false;
}

HashTable* NewNode(char* key, char* value)
{
    HashTable* tmpNode = (HashTable*)malloc(sizeof(HashTable));
    if(tmpNode != NULL)
    {
        tmpNode->nextEntry = NULL;
        tmpNode->key   = (char*)malloc(strlen(key));
        tmpNode->value = (char*)malloc(strlen(value));

        strcpy(tmpNode->key, key);
        strcpy(tmpNode->value, value);
    }
    return tmpNode;
}

AppendLinkedNode trouve le dernier nœud de la liste, et ajoute un nouveau nœud à elle.

Le code pourra être utilisé comme ceci:

if(InitHashTable(100) == false) return -1;
AddNode("10", "TEN");

Trouver un nœud est aussi simple que:

HashTable* FindNode(char* key)
{
    int offset = ComputeHash(key);
    HashTable* tmpNode = hashTable.hashBucketArray[offset];
    while(tmpNode != NULL)
    {
        if(strcmp(tmpNode->key, key) == 0)
            return tmpNode;
        tmpNode = tmpNode->nextEntry;
    }
    return NULL;
}

Et est utilisée comme suit:

char* value = FindNode("10");

Je ne suis pas sûr que vous coould utilisation char* value = FindNode("10"); depuis FindNode retourne HashTable*. Si vous être à la recherche à quelque chose le long des lignes de: char* value = FindNode("10")->value;

InformationsquelleAutor SemiColon

Une implémentation de Java dans < 60 LoC

import java.util.ArrayList;
import java.util.List;
import java.util.Random;


public class HashTable {

    class KeyValuePair {

        Object key;

        Object value;

        public KeyValuePair(Object key, Object value) {
            this.key = key;
            this.value = value;
        }
    }

    private Object[] values;

    private int capacity;

    public HashTable(int capacity) {
        values = new Object[capacity];
        this.capacity = capacity;
    }

    private int hash(Object key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void add(Object key, Object value) throws IllegalArgumentException {

        if (key == null || value == null)
            throw new IllegalArgumentException("key or value is null");

        int index = hash(key);

        List<KeyValuePair> list;
        if (values[index] == null) {
            list = new ArrayList<KeyValuePair>();
            values[index] = list;

        } else {
            //collision
            list = (List<KeyValuePair>) values[index];
        }

        list.add(new KeyValuePair(key, value));
    }

    public Object get(Object key) {
        List<KeyValuePair> list = (List<KeyValuePair>) values[hash(key)];
        if (list == null) {
            return null;
        }
        for (KeyValuePair kvp : list) {
            if (kvp.key.equals(key)) {
                return kvp.value;
            }
        }
        return null;
    }

    /**
     * Test
     */
    public static void main(String[] args) {

        HashTable ht = new HashTable(100);

        for (int i = 1; i <= 1000; i++) {
            ht.add("key" + i, "value" + i);
        }

        Random random = new Random();
        for (int i = 1; i <= 10; i++) {
            String key = "key" + random.nextInt(1000);
            System.out.println("ht.get(\"" + key + "\") = " + ht.get(key));
        }   
    }
}

Vous ne savez pas ce que list.add(new KeyValuePair(key, value)); est en train de faire à la fin de la add fonction?
Je ne comprends pas trop la question. Il ajoute la clé -> valeur de la cartographie à l'intérieur de la matrice de sorte qu'il peut être récupéré plus tard dans le get() de l'appel.
Désolé, je ne pensais pas à droite. Je pensais qu'il était défini dans la méthode, donc il va juste être nettoyée, mais vous l'utilisez comme une poignée sur un élément du values variable membre.

InformationsquelleAutor Korbi

7

Une table de hachage est vraiment un concept simple: c'est un tableau dans lequel les paires clé-valeur sont placés dans des, (comme un tableau associatif) par le schéma suivant:

Une fonction de hachage hachages la clé d'une (on l'espère) inutilisé de l'indice dans le tableau. la valeur est ensuite placé dans le tableau à l'index.

La récupération de données est facile, comme l'index dans le tableau peut être calculée à l'aide de la fonction de hachage, donc l'air est ~ O(1).

Un problème survient lorsqu'une fonction de hachage cartes de 2 clés différentes pour le même indice...il y a beaucoup de façons de traiter ce qui je ne détaillerai pas ici...

Les tables de hachage sont un moyen fondamental de stockage et de récupération des données rapidement, et est "intégrée" dans presque l'ensemble de la programmation des bibliothèques de langue.
- Comment est-ce lié à la question?
- Convenu ce ne peut pas répondre à la question, et que la question peut ne pas être constructif, mais au moins je comprends enfin pourquoi les tables de hachage sont si prompts à récupérer des valeurs! Très embarrassant que, jusqu'à maintenant, je pensais que c'était le vaudou.
InformationsquelleAutor mmattax
3

J'étais à la recherche d'un portable C table de hachage de la mise en œuvre et s'est intéressé à la façon de mettre en œuvre un moi-même. Après avoir cherché un peu j'ai trouvé:
Julienne Walker est L'Art de Hachage qui a quelques bons tutoriels sur le hachage et les tables de hachage. Leur mise en œuvre est un peu plus complexe que ce que je pensais, mais ça a été une excellente lecture.

InformationsquelleAutor Nick Van Brunt

Voici mon code pour une Table de Hachage, mise en œuvre en Java. Souffre d'un problème mineur - la clé des champs de valeur et ne sont pas les mêmes. Peut le modifier dans l'avenir.

public class HashTable
{
    private LinkedList[] hashArr=new LinkedList[128];
    public static int HFunc(int key)
    {
        return key%128;
    }


    public boolean Put(Val V)
    {

        int hashval = HFunc(V.getKey());
        LinkedNode ln = new LinkedNode(V,null);
        hashArr[hashval].Insert(ln);
        System.out.println("Inserted!");
        return true;            
    }

    public boolean Find(Val V)
    {
        int hashval = HFunc(V.getKey());
        if (hashArr[hashval].getInitial()!=null && hashArr[hashval].search(V)==true)
        {
            System.out.println("Found!!");
            return true;
        }
        else
        {
            System.out.println("Not Found!!");
            return false;
        }

    }
    public boolean delete(Val v)
    {
        int hashval = HFunc(v.getKey());
        if (hashArr[hashval].getInitial()!=null && hashArr[hashval].delete(v)==true)
        {
            System.out.println("Deleted!!");
            return true;
        }
        else 
        {
            System.out.println("Could not be found. How can it be deleted?");
            return false;
        }
    }

    public HashTable()
    {
        for(int i=0; i<hashArr.length;i++)
            hashArr[i]=new LinkedList();
    }

}

class Val
{
    private int key;
    private int val;
    public int getKey()
    {
        return key;
    }
    public void setKey(int k)
    {
        this.key=k;
    }
    public int getVal()
    {
        return val;
    }
    public void setVal(int v)
    {
        this.val=v;
    }
    public Val(int key,int value)
    {
        this.key=key;
        this.val=value;
    }
    public boolean equals(Val v1)
    {
        if (v1.getVal()==this.val)
        {
            //System.out.println("hello im here");
            return true;
        }
        else 
            return false;
    }
}

class LinkedNode
{
    private LinkedNode next;
    private Val obj;
    public LinkedNode(Val v,LinkedNode next)
    {
        this.obj=v;
        this.next=next;
    }
    public LinkedNode()
    {
        this.obj=null;
        this.next=null;
    }
    public Val getObj()
    {
        return this.obj;    
    }
    public void setNext(LinkedNode ln)
    {
        this.next = ln;
    }

    public LinkedNode getNext()
    {
        return this.next;
    }
    public boolean equals(LinkedNode ln1, LinkedNode ln2)
    {
        if (ln1.getObj().equals(ln2.getObj()))
        {
            return true;
        }
        else 
            return false;

    }

}

class LinkedList
{
    private LinkedNode initial;
    public LinkedList()
    {
        this.initial=null;
    }
    public LinkedList(LinkedNode initial)
    {
        this.initial = initial;
    }
    public LinkedNode getInitial()
    {
        return this.initial;
    }
    public void Insert(LinkedNode ln)
    {
        LinkedNode temp = this.initial;
        this.initial = ln;
        ln.setNext(temp);
    }
    public boolean search(Val v)
    {
        if (this.initial==null)
            return false;
        else 
        {
            LinkedNode temp = this.initial;
            while (temp!=null)
            {
                //System.out.println("encountered one!");
                if (temp.getObj().equals(v))
                    return true;
                else 
                    temp=temp.getNext();
            }
            return false;
        }

    }
    public boolean delete(Val v)
    {
        if (this.initial==null)
            return false;
        else 
        {
            LinkedNode prev = this.initial;
            if (prev.getObj().equals(v))
            {
                this.initial = null;
                return true;
            }
            else
            {
                LinkedNode temp = this.initial.getNext();
            while (temp!=null)
            {
                if (temp.getObj().equals(v))
                {
                    prev.setNext(temp.getNext());
                    return true;
                }
                else
                {
                    prev=temp;
                    temp=temp.getNext();
                }
            }
            return false;
            }
        }
    }
}

InformationsquelleAutor Pranav

0

Je pense que vous devez être un peu plus précis. Il existe plusieurs variantes sur les tables de hashage en ce qui concerne les options suivantes
- Est la table de hachage de taille fixe ou dynamique?
- Quel type de fonction de hachage est utilisée?
- Y a des contraintes de performance lorsque la table de hachage est redimensionnée?
La liste peut continuer encore et encore. Chacune de ces contraintes pourrait conduire à de multiples implémentations dans n'importe quelle langue.

Personnellement, je voudrais juste utiliser le microphone de table de hachage qui est disponible dans ma langue de son choix. La seule raison pour laquelle je pourrait même envisager de mettre mon propre serait dû à des problèmes de performance, et même alors, il est difficile de battre la plupart des implémentations existantes.

InformationsquelleAutor Jason Z

Pour ceux qui peuvent utiliser le code ci-dessus, note la fuite de mémoire:

tmpNode->key   = (char*)malloc(strlen(key)+1);   //must have +1 for 'tmpNode->key   = (char*)malloc(strlen(key)+1);   //must have +1 for '\0'
tmpNode->value = (char*)malloc(strlen(value)+1); //must have +1
strcpy(tmpNode->key, key);
strcpy(tmpNode->value, value);
'
tmpNode->value = (char*)malloc(strlen(value)+1); //must have +1
strcpy(tmpNode->key, key);
strcpy(tmpNode->value, value);

Et à compléter le code:

HashNode* AppendLinkedNode(HashNode* ptr, char* key, char* value)
{
    //follow pointer till end
    while (ptr->nextEntry!=NULL)
    {
        if (strcmp(ptr->value,value)==0) return NULL;
        ptr=ptr->nextEntry;
    }
    ptr->nextEntry=newNode(key,value);
    return ptr->nextEntry;
}

InformationsquelleAutor

0

Minimale de mise en œuvre en F# comme une fonction qui crée une table de hachage à partir d'une séquence de paires clé-valeur et retourne une fonction qui recherche dans la table de hachage pour la valeur associée à la clé donnée:
```
> let hashtbl xs =
    let spine = [|for _ in xs -> ResizeArray()|]
    let f k = spine.[abs(k.GetHashCode()) % spine.Length]
    Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs
    fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);;
val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality
```
- Une correction mineure est nécessaire dans la ligne 3 de l'extrait ci-dessus: k.GetHashCode() peut retourner un nombre négatif (par exemple, "Key with negative hashcode".GetHashCode() retourne -648767821), qui, à son tour, permettra de rendre le Système.IndexOutOfRangeException lors du calcul d'un seau, pour clés tels par la fonction f.
- Bonne prise. Fixe.
InformationsquelleAutor Jon Harrop
-1

Je suis allé lire quelques de Wikipedia-page sur le hachage: http://en.wikipedia.org/wiki/Hash_table. Il ressemble à beaucoup de travail, de mettre en place un code pour une table de hachage ici, surtout depuis que la plupart des langues que j'utilise déjà les avoir intégrés. Pourquoi voudriez-vous implémentations ici? Cette substance appartient vraiment dans une des langues de la bibliothèque.

Veuillez élaborer sur ce que vos solutions attendus devrait inclure:
- fonction de hachage
- variable comte de seau
- comportement de collision
Également état de ce que le but de la collecte est ici. Une sérieuse mise en œuvre sera facilement être tout à fait un mouthfull = cela conduira à de très longues réponses (peut-être quelques pages chaque). Vous pourriez également être attirez les gens de copier le code à partir d'une bibliothèque...

InformationsquelleAutor Daren Thomas

Vous devez vous connecter pour publier un commentaire.