¿Cómo implementaría una tabla hash en el lenguaje x?

Question

El objetivo de esta pregunta es recopilar una lista de ejemplos de implementaciones de hashtable utilizando matrices en diferentes idiomas. También sería bueno si alguien pudiera ofrecer una descripción bastante detallada de cómo funcionan y qué está sucediendo con cada ejemplo.

Editar:

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

Porque deberíamos saber cómo funcionan las tablas hash y poder implementarlas. Puede que esto no parezca un tema súper importante, pero saber cómo funciona una de las estructuras de datos más utilizadas me parece muy importante. Si esto se va a convertir en la wikipedia de programación, estos son algunos de los tipos de preguntas por las que vendré aquí. No estoy buscando un libro de CS que deba escribirse aquí. Podría ir introduciendo Algoritmos en el estante y leer el capítulo sobre tablas hash y obtener ese tipo de información. Más específicamente, lo que estoy buscando son código ejemplos. No solo para mí en particular, sino también para otros que algún día podrían estar buscando información similar y tropezando con esta página.

Para ser más específicos: Si tenía para implementarlos, y no podía usar las funciones incorporadas, ¿cómo lo haría?

No es necesario que coloque el código aquí. Ponlo en pastebin y solo conéctalo.

Answer 1

Creo que tiene que ser un poco más específico. Hay varias variaciones en hashtables con respecto a las siguientes opciones

• ¿La tabla hash es de tamaño fijo o dinámica?
• ¿Qué tipo de función hash se usa?
• ¿Hay alguna restricción de rendimiento cuando se cambia el tamaño de la tabla hash?

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

Personalmente, simplemente usaría la tabla hash incorporada que está disponible en mi idioma de elección. La única razón por la que incluso consideraría implementar la mía sería debido a problemas de rendimiento, e incluso entonces es difícil superar la mayoría de las implementaciones existentes.

Answer 2

Fui y leí parte de la página de Wikipedia sobre hash: http://en.wikipedia.org/wiki/Hash_table. Parece mucho trabajo poner código para una tabla hash aquí, especialmente porque la mayoría de los lenguajes que uso ya los tienen incorporados. ¿Por qué querrían implementaciones aquí? Esto realmente pertenece a una biblioteca de idiomas.

Sírvanse explicar en detalle cuáles son sus soluciones esperadas deben incluir:

• función hash
• cubo variable de recuento
• comportamiento de colisión

Asimismo, indique cuál es el propósito de proceder a su recogida aquí está. Cualquier implementación seria será bastante difícil = esto dará lugar a respuestas muy largas (posiblemente unas pocas páginas cada una).También podría estar tentando a las personas a copiar el código de una biblioteca ...

Answer 3

Una tabla Hash es un conjunto en el que se colocan pares clave y de valor (como una matriz asociativa) mediante el siguiente esquema:

Una función de almohadilla hash la clave de un (con suerte) índice no utilizado en la matriz. el valor luego se coloca en la matriz en ese índice en particular.

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

surge un problema cuando una función hash mapea 2 llaves diferentes para el mismo índice ... hay muchas maneras de manejar esto lo que no voy a detallar aquí ...

Las tablas hash son una forma fundamental de almacenamiento y recuperar datos rápidamente, y están "incorporados" en casi todas las bibliotecas de lenguaje de programación.

Answer 4

Una tabla hash es una estructura de datos que permite la búsqueda de elementos en tiempo constante. Funciona mezclando un valor y convirtiendo 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. No estoy pegando toda la tabla hash aquí, pero aquí hay algunos fragmentos de una tabla hash que hice en C hace unas semanas ...

Uno de los conceptos básicos para crear una tabla hash es tener una buena función hash . He utilizado la función hash djb2 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 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 le agrega un nuevo nodo.

El código se utiliza como esto:

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

Answer 5

que estaba buscando para una implementación de la tabla C hash completamente portátil y se interesó en cómo implementar uno yo mismo. Después de buscar un poco encontré: Julienne Walker's The Art of Hashing que tiene algunos excelentes tutoriales sobre hash y tablas hash. Implementarlos es un poco más complejo de lo que pensaba, pero fue una gran lectura.

Answer 6

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

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

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

Answer 7

Aquí está mi código de una tabla hash, implementado en Java . Sufre de un problema menor: los campos de clave y valor no son lo mismo. Podría editar eso 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; 
      } 
     } 
    } 
} 

Answer 8

aplicación mínima en F # como una función que genera una tabla hash a partir de una determinada secuencia de pares de valores clave y devuelve una función que busca en la tabla hash para el valor asociado a 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 

Answer 9

aplicación Java en < 60 Línea de Control

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