arrays - resolucion - tablas hash en java
¿Cómo implementaría una tabla hash en el lenguaje x? (9)
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 usar las funciones hash integradas 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 ejemplos de código . 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ífico: si tuviera que implementarlos, y no pudiera usar las funciones incorporadas, ¿cómo lo haría?
No necesitas poner el código aquí. Ponlo en pastebin y solo conéctalo.
Aquí está mi código para una Tabla Hash, implementada 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;
}
}
}
}
Creo que debes ser un poco más específico. Hay varias variaciones en hashtables con respecto a las siguientes opciones
- ¿Es la tabla hash 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, 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.
Estaba buscando una implementación de tabla C hash completamente portátil y me interesé en cómo implementar una yo mismo. Después de buscar un poco, encontré: The Art of Hashing, de Julienne Walker, que contiene excelentes tutoriales sobre hashing y hash tables. Implementarlos es un poco más complejo de lo que pensaba, pero fue una gran lectura.
Fui y leí parte de la página de Wikipedia sobre hashing: 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.
Por favor explique qué deben incluir sus soluciones esperadas:
- función hash
- conteo variable de cubos
- comportamiento de colisión
Indique también cuál es el propósito de recopilarlos aquí. 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 ...
Implementación mínima en F # como una función que construye una tabla hash a partir de una secuencia dada de pares clave-valor y devuelve una función que busca en la tabla hash 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
Para aquellos que pueden usar el código anterior, fíjese en 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;
}
Una HashTable es un concepto realmente simple: es una matriz en la que se colocan los pares clave y de valor, (como una matriz asociativa) mediante el siguiente esquema:
Una función hash ajusta la clave de un índice (con suerte) 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 asigna 2 claves diferentes al mismo índice ... hay muchas formas de manejar esto que no detallaré aquí ...
Las tablas Hash son una forma fundamental de almacenar y recuperar datos rápidamente, y están "integradas" en casi todas las bibliotecas de lenguaje de programación.
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));
}
}
}
Una tabla hash 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 pegaré 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. Usé 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 real para crear y administrar 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 en la lista vinculada y le agrega un nuevo nodo.
El código se usaría así:
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 usa de la siguiente manera:
char* value = FindNode("10");