Как бы вы реализовали хэш-таблицу в языке x?

Question

Задача этого вопроса состоит в том, чтобы собрать список примеров реализаций хэш-таблицы с использованием массивов на разных языках. Было бы также неплохо, если бы кто-то мог составить довольно подробный обзор того, как они работают, и что происходит с каждым примером.

Edit:

Почему бы просто не использовать встроенный в хэш-функции в вашем конкретном языке?

Потому что мы должны знать, как работают хеш-таблицы и смогут их реализовать. Это может показаться не очень важной темой, но знание того, как работает одна из наиболее используемых структур данных, кажется мне очень важным. Если это станет википедией программирования, то это некоторые из типов вопросов, к которым я приду сюда. Я не ищу книгу CS, которая будет написана здесь. Я мог бы перейти Intro к алгоритмам с полки и прочитать в главе о хэш-таблицах и получить этот тип информации. Более конкретно то, что я ищу, это примеры кода. Не только для меня, в частности, но и для других, которые, возможно, когда-нибудь будут искать подобную информацию и спотыкаться по этой странице.

Конкретно: Если у вас было, чтобы реализовать их и не могли использовать встроенные функции, как бы вы это сделали?

Вам не нужно указывать здесь код. Поместите его в пастебин и просто соедините его.

Answer 1

Я думаю, вам нужно быть более конкретным. Существует несколько вариантов использования хеш-таблиц в отношении следующих вариантов:

• Является ли хэш-таблица фиксированной или динамической?
• Какой тип хеш-функции используется?
• Существуют ли ограничения производительности при изменении размера хэш-таблицы?

Список можно продолжать и продолжать. Каждое из этих ограничений может привести к множеству реализаций на любом языке.

Лично я бы просто использовал встроенную хеш-таблицу, которая доступна на моем языке выбора. Единственная причина, по которой я бы даже подумал о том, чтобы реализовать свою собственную, - это из-за проблем с производительностью, и даже тогда ее трудно превзойти большинство существующих реализаций.

Answer 2

Я пошел и прочитал часть страницы Википедии о хешировании: http://en.wikipedia.org/wiki/Hash_table. Кажется, что много работы, чтобы поставить код для хэш-таблицы здесь, тем более, что большинство языков, которые я использую allready, их встроили. Зачем вам нужны реализации здесь? Этот материал действительно принадлежит библиотеке языков.

Просьба уточнить, что ваши ожидаемые решения должны включать в себя:

• хэш-функция
• переменная ведро счетчик
• поведение столкновения

государства также, что цель сбора их здесь. Любая серьезная реализация легко будет довольно насыщенной - это приведет к очень длинным ответам (возможно, на несколько страниц каждый).Вы также можете заставлять людей копировать код из библиотеки ...

Answer 3

HashTable - очень простая концепция: это массив, в который помещаются пары ключей и значений (как ассоциативный массив) следующим образом схема:

Хеш-функция хэширует ключ к (надеюсь) неиспользованному индексу в массив. значение затем помещается в массив по этому конкретному индексу.

Извлечение данных легко, так как индекс в массив может быть рассчитан через хеш-функцию, поэтому поиск равен ~ O (1).

Проблемы возникает тогда, когда хэш-функция отображает 2 разных ключи к тому же индексу ... Есть много способов обработки этого, которые я не буду здесь подробно ...

таблицы хеширования является основным способом хранения и быстро извлекают данные и «встроены» почти во все библиотеки языка программирования.

Answer 4

Хэш-таблица структуры данных, которая позволяет искать элементы в постоянное время. Он работает путем хэширования значения и преобразования этого значения в смещение в массиве. Понятие хэш-таблицы довольно легко понять, но реализация явно сложнее. Я не вставляю всю хэш-таблицу здесь, но вот некоторые фрагменты хэш-таблицы, которые я сделал в C несколько недель назад ...

Одна из основ создания хеш-таблицы имеет хорошую хэш-функцию , Я использовал djb2 хэш-функции в моей хэш-таблицы:

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

Затем приходит фактический код сам для создания и управления ведра в таблице

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 находит последний узел в связанном списке и добавляет к нему новый узел.

код будет использоваться следующим образом:

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

найти узел является простым, как:

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

И используется следующим образом:

char* value = FindNode("10"); 

Answer 5

Я искал для полностью переносимой реализации хэш-таблицы C и заинтересовался тем, как реализовать ее самостоятельно. После нескольких поисков я обнаружил: Julienne Walker's The Art of Hashing, в котором есть отличные уроки по хэшированию и хеш-таблицам. Реализация их немного сложнее, чем я думал, но это было отличное чтение.

Answer 6

Для тех, кто может использовать код, приведенный выше, обратите внимание на утечку памяти:

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

И завершить код:

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

Вот мой код для хэш-таблицы, реализованный в Java , Страдает от незначительного сбой - поля ключа и значения не совпадают. Можете изменить это в будущем.

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

Минимальная реализация в F # как функцию, которая создает хэш-таблицу из заданной последовательности пар ключ-значение и возвращает функцию, которая ищет в хэш-таблицу для значения, связанного с данным ключом:

> 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

реализация Java, в < 60 ЛСС

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