我们将如何使用语言x实现哈希表？
这个问题的重点是收集使用不同语言的数组的哈希表实现的示例列表。如果有人可以对他们的工作方式以及每个示例所发生的事情进行详细的概述，那也很好。
编辑：
为什么不只使用特定语言的内置哈希函数呢？
因为我们应该知道哈希表如何工作并能够实现它们。这似乎不是一个超级重要的话题，但是对我来说，了解最常用的数据结构之一的工作原理似乎很重要。如果这要成为编程的维基百科，那么这些就是我将在这里提出的一些类型的问题。我不是要在此处编写CS书籍。我可以直接阅读"算法简介"，然后阅读有关散列表的章节，并获取该类型的信息。更具体地说，我正在寻找的是代码示例。不仅对我来说特别如此，对于其他可能有一天会搜索相似信息并偶然浏览此页面的人也是如此。
更具体地说：如果我们必须实现它们，并且不能使用内置函数，我们将如何做？
我们无需将代码放在这里。将其放在pastebin中，然后将其链接。
解决方案
回答
我认为我们需要更具体一些。关于以下选项，哈希表有多种变体
- 哈希表是固定大小的还是动态的？
- 使用哪种类型的哈希函数？
- 调整哈希表的大小时是否存在性能限制？
该列表可以继续下去。这些约束中的每一个都可能导致以任何语言进行多种实现。
就个人而言，我只会使用我选择的语言中可用的内置哈希表。我什至会考虑实施自己的唯一原因是由于性能问题，即使如此，也很难击败大多数现有的实施。
回答
我去阅读了一些有关哈希的Wikipedia页：http://en.wikipedia.org/wiki/Hash_table。在这里为哈希表放置代码似乎需要很多工作，特别是因为我已经使用的大多数语言都已经内置了它们。为什么要在这里实现？这些东西确实属于语言库。
请详细说明预期解决方案应包括：
- 散列函数
- 可变的存储桶数
- 碰撞行为
还要说明在这里收集它们的目的是什么。任何认真的实现都将很容易使人大开嘴–这将导致很长的答案(每个答案可能只有几页长)。我们可能还诱使人们从库中复制代码...
回答
HashTable是一个非常简单的概念：它是一个通过以下方案将键和值对放入其中的数组(如关联数组)：
散列函数将键散列到(希望)未使用的数组索引。然后将该值放在该特定索引处的数组中。
数据检索很容易，因为可以通过哈希函数计算数组的索引，因此查找值为〜O(1)。
当散列函数将2个不同的键映射到相同的索引时，就会出现问题。有很多处理方式，在此不再赘述...
哈希表是快速存储和检索数据的基本方法，并且"内置"在几乎所有编程语言库中。
回答
哈希表是一种数据结构，它允许在恒定时间内查找项目。它通过散列值并将该值转换为数组中的偏移量来工作。哈希表的概念相当容易理解，但是实现起来显然更困难。我没有在此处粘贴整个哈希表，但是这里是几周前我在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");
回答
我一直在寻找一种完全可移植的C哈希表实现，并对自己如何实现感兴趣。经过一番搜索，我发现：
朱利安·沃克(Julienne Walker)的《散列的艺术》(The Art of Hashing)中有一些很棒的关于散列和散列表的教程。实施它们比我想象的要复杂，但这是一本好书。
回答
对于那些可能使用上面代码的人，请注意内存泄漏：
tmpNode->key = (char*)malloc(strlen(key)+1); //must have +1 for '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;
}
'
tmpNode->value = (char*)malloc(strlen(value)+1); //must have +1
strcpy(tmpNode->key, key);
strcpy(tmpNode->value, value);
并完成代码：
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;
}
}
}
}
回答
这是我用Java实现的哈希表代码。遭受小故障的困扰键和值字段不相同。以后可能会对其进行编辑。
> 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
回答
Fas中的最少实现是一个函数，该函数根据给定的键值对序列构建哈希表，并返回一个在哈希表中搜索与给定键相关联的值的函数：
##代码##