El punto de esta pregunta es obtener una lista de ejemplos de hashtable implementaciones de uso de matrices en diferentes idiomas. También sería bueno si alguien puede tirar en una bonita descripción detallada de cómo funcionan, y lo que está sucediendo con cada ejemplo.

Edición:

¿Por qué no utilizar el construido en funciones de hash en su lenguaje específico?

Porque debemos saber cómo hash mesas de trabajo y ser capaces de aplicarlas. Esto puede no parecer un super tema importante, pero sabiendo cómo uno de los más utilizados en las estructuras de datos de las obras parece muy importante para mí. Si esto se convierte en la wikipedia de programación, a continuación, estos son algunos de los tipos de preguntas que voy a venir aquí. Yo no estoy buscando un CS libro escrito aquí. Yo podía ir a tirar Introducción a los Algoritmos de la estantería y leer el capítulo sobre las tablas hash y obtener ese tipo de información. Más específicamente lo que estoy buscando son ejemplos de código. No sólo para mí en particular, pero también para otras personas que tal vez un día buscando información similar y tropieza a través de esta página.

Para ser más específico: Si había para ponerlas en práctica, y no podía utilizar las funciones integradas, cómo lo harías?

No es necesario poner el código aquí. Poner en pastebin y solo enlace.

  • La idea es TAN orgánicamente a convertirse en la Wikipedia de la programación. No fuerce preguntas; esto huele de karma de la agricultura.
InformationsquelleAutor mk. | 2008-08-24

9 Comentarios

  1. 19

    Una tabla hash de una estructura de datos que permite la búsqueda de artículos en tiempo constante. Funciona por la mezcla de un valor y convertir ese valor a un desplazamiento en una matriz. El concepto de una tabla hash es bastante fácil de entender, pero la implementación es obviamente más difícil. Yo no soy de pegar toda la tabla hash aquí, pero aquí hay algunos fragmentos de una tabla hash que he hecho en C hace un par de semanas…

    Uno de los fundamentos de la creación de una tabla hash es tener una buena función hash. He utilizado el djb2 función de hash en mi tabla hash:

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

    Luego viene el código real en sí para la creación y gestión de los cubos en la tabla

    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 encuentra el último nodo de la lista enlazada y agrega un nuevo nodo a la misma.

    El código sería utilizado como esta:

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

    Encontrar un nodo es un simple como:

    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;
    }
    

    Y se utiliza de la siguiente manera:

    char* value = FindNode("10");
    
    • No estoy seguro de que usted coould uso char* value = FindNode("10"); desde FindNode devuelve HashTable*. Así que usted podría estar observando algo a lo largo de las líneas de: char* value = FindNode("10")->value;
  2. 8

    Una implementación de Java en < 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));
            }   
        }
    }
    
    • No estoy seguro de lo que list.add(new KeyValuePair(key, value)); está haciendo en la final de la add función?
    • Yo realmente no se de que se trate. Se agrega la clave -> asignación de valores a la matriz interna para que se pueda recuperar más tarde en el get() de la llamada.
    • Lo siento, yo no estaba pensando recta. Estaba pensando que era definido en el método, por lo que sólo va a ser el recolector de basura, pero usted lo está utilizando como un identificador en un elemento en el values miembro de la variable.
  3. 7

    Una tabla Hash es un concepto muy simple: es una matriz en la que los pares clave /valor se coloca en, (como una matriz asociativa) por el siguiente esquema:

    Una función hash hash de la clave para una (esperemos) no utilizados índice en la matriz. el valor se coloca entonces en la matriz en ese índice en particular.

    De recuperación de datos es fácil, ya que el índice en la matriz se puede calcular a través de la función de hash, lo que buscar es ~ O(1).

    Surge un problema cuando una función hash mapas 2 claves diferentes para el mismo índice…hay muchas maneras de manejar esto que no voy a detallar aquí…

    Las tablas Hash son una forma fundamental de almacenar y recuperar datos de forma rápida, y se «integra» en casi todos los lenguajes de programación lenguaje de las bibliotecas.

    • Cómo se relaciona con la pregunta?
    • Acordado esto no puede contestar la pregunta, y que la cuestión no puede ser constructivo, pero al menos puedo terminar de comprender por qué las tablas hash son tan rápidos para recuperar los valores! Muy vergonzoso que hasta ahora yo pensaba que era el vudú.
  4. 3

    Yo estaba buscando una completamente portátil C de la tabla hash de implementación y se convirtió interesado en cómo implementar uno mismo. Después de buscar un poco he encontrado:
    Juliana Walker El Arte de la mezcla que tiene algunos buenos tutoriales en hash y tablas hash. La aplicación de ellos es un poco más complejo de lo que pensaba, pero fue una gran lectura.

  5. 1

    Aquí está mi código para una Tabla Hash, implementado en Java. Sufre de un menor de edad glitch – la clave y el valor de los campos no son los mismos. Puede editar en el futuro.

    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;
                }
            }
        }
    }
    
  6. 0

    Creo que hay que ser un poco más específico. Hay varias variaciones de tablas de hash con respecto a las siguientes opciones

    • Es la tabla hash de tamaño fijo o dinámico?
    • ¿Qué tipo de función hash se utiliza?
    • Hay restricciones de rendimiento cuando se cambia el tamaño de la tabla hash?

    La lista puede seguir y seguir. Cada una de estas limitaciones podrían conducir a múltiples implementaciones en cualquier idioma.

    Personalmente, me acaba de utilizar el built-in hashtable que está disponible en mi idioma de su elección. La única razón por la que me atrevería a considerar la aplicación de mi propio sería debido a problemas de rendimiento, y aún así es difícil vencer a la mayoría de las implementaciones existentes.

  7. 0

    Para aquellos que pueden utilizar el código anterior, tenga en cuenta la pérdida de memoria:

    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);

    Y para completar el código:

    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;
    }
    
  8. 0

    Mínimo de aplicación en F# como una función que crea una tabla hash de una determinada secuencia de pares clave-valor y devuelve una función que busca en la tabla hash para el valor asociado con la clave dada:

    > 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
    
    • Una menor corrección es necesario en la línea 3 del fragmento anterior: k.GetHashCode() puede devolver un número negativo (por ejemplo, "Key with negative hashcode".GetHashCode() devuelve -648767821), que, a su vez, hará que el Sistema.IndexOutOfRangeException a la hora de calcular un número del cubo para una clave por la función f.
    • Buena captura. Fijo.
  9. -1

    Fui y leer un poco de la Wikipedia-página hash: http://en.wikipedia.org/wiki/Hash_table. Parece como un montón de trabajo, para poner el código de una tabla hash aquí, especialmente porque la mayoría de los idiomas puedo usar ya los han incorporado. ¿Por qué quieres implementaciones de aquí? Esto realmente le pertenece en idiomas de la biblioteca.

    Sírvanse explicar en detalle lo que espera soluciones deben incluir:

    • función hash
    • variable número de depósito
    • colisión comportamiento

    También indicar cuál es la finalidad de la recogida aquí está. Cualquier seria implementación fácilmente ser bastante mouthfull = esto conducirá a muy largo respuestas (posiblemente un par de páginas cada uno). Usted también podría persuadir a las personas para copiar el código de una biblioteca…

Dejar respuesta

Please enter your comment!
Please enter your name here