你会如何在语言x中实现散列表？

Question

这个问题的关键是收集使用不同语言的数组的哈希表实现列表。如果有人能够详细了解他们的工作方式以及每个示例发生的情况，这也很好。

编辑：

为什么不直接使用内置的散列函数在特定的语言？

因为我们应该知道哈希表如何工作并能够实现它们。这似乎不是一个超级重要的话题，但知道如何使用最常用的数据结构对我来说似乎非常重要。如果这要成为编程的维基百科，那么这些就是我将来到这里的一些类型的问题。我不想在这里写一本CS书。我可以将现成的算法从现成的算法中解放出来，并阅读关于哈希表的章节并获取该类型的信息。更具体地说，我正在寻找的是代码示例。不仅对我来说尤其如此，对于那些也许有一天会在这个页面上寻找类似信息并且偶然发现的人来说也是如此。

更具体一点：如果你有来实现它们，并且不能使用内置函数，你会怎么做？

你不需要把代码放在这里。把它放在pastebin中，然后连接它。

Answer 1

我认为你需要更具体一点。关于以下选项，哈希表有几种变体：

• 散列表是固定大小还是动态的？
• 使用什么类型的散列函数？
• 哈希表大小调整时是否存在任何性能约束？

该列表可以继续。这些约束中的每一个都可能导致以任何语言执行多个实现。

就我个人而言，我只是使用内置的散列表，可用我的语言选择。我甚至会考虑实施我自己的唯一原因是由于性能问题，即使如此也很难击败大多数现有的实现。

Answer 2

我去读了一些关于散列的维基百科页面：http://en.wikipedia.org/wiki/Hash_table。看起来好像有很多工作要为这里的散列表编写代码，特别是因为我使用的大多数语言都已经内置了它们。为什么你要在这里实现？这些东西真的属于语言库。

请你的期望的解决方案应包括详细说明：

• 哈希函数
• 可变斗数
• 碰撞行为

还规定什么这里收集他们的目的是什么。任何严肃的实施都会很容易地出现 - 这将导致很长的答案（可能每页只有几页）。您可能也会诱使人们从库中复制代码...

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

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