关于数组：如何用语言x实现哈希表？

How would you implement a hashtable in language x?

这个问题的重点是收集使用不同语言的数组的哈希表实现的示例列表。如果有人可以对他们的工作方式以及每个示例所发生的事情进行详细的概述，那也很好。

编辑：

为什么不只使用特定语言的内置哈希函数呢？

因为我们应该知道哈希表如何工作并能够实现它们。这似乎不是一个超级重要的话题，但是对我来说，了解最常用的数据结构之一的工作原理似乎很重要。如果要成为编程的维基百科，那么这些就是我将在这里提出的一些类型的问题。我不是要在这里写CS书。我可以直接阅读"算法简介"，然后阅读有关哈希表的章节，并获取该类型的信息。更具体地说，我正在寻找的是代码示例。不仅对我来说特别如此，对于其他可能有一天会搜索相似信息并偶然浏览此页面的人也是如此。

更具体地说：如果您必须实现它们，并且不能使用内置函数，您将如何做？

您无需将代码放在这里。将其放在pastebin中，然后将其链接。

哈希表是一种数据结构，允许在恒定时间内查找项目。它通过散列值并将该值转换为数组中的偏移量来工作。哈希表的概念相当容易理解，但是实现起来显然比较困难。我没有在这里粘贴整个哈希表，但是这里是几周前我在C语言中制作的哈希表的一些片段...

创建哈希表的基础知识之一就是拥有良好的哈希函数。我在哈希表中使用了djb2哈希函数：

1
2
3
4
5
6
7

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

然后是用于创建和管理表中存储桶的实际代码本身

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

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在链表中找到最后一个节点，并向其附加一个新节点。

该代码将像这样使用：

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

查找节点很简单：

1
2
3
4
5
6
7
8
9
10
11
12

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

并使用如下：

1	char* value = FindNode("10");

<60 LoC中的Java实现

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

HashTable是一个非常简单的概念：它是一个通过以下方案将键和值对放入其中的数组(如关联数组)：

哈希函数将键散列到(希望)未使用的数组索引。然后将该值放在该特定索引处的数组中。

数据检索很容易，因为可以通过哈希函数计算数组的索引，因此查找值为?O(1)。

当哈希函数将2个不同的键映射到相同的索引时，就会出现问题。有很多处理方式，在此不再赘述...

哈希表是快速存储和检索数据的基本方式，并且"内置"在几乎所有编程语言库中。

我一直在寻找一种完全可移植的C哈希表实现，并对自己如何实现感兴趣。经过一番搜索，我发现：
朱利安·沃克(Julienne Walker)的《散列的艺术》(The Art of Hashing)中有一些很棒的关于散列和散列表的教程。实施它们比我想象的要复杂，但这是一本好书。

这是我用Java实现的哈希表代码。遭受小故障-键和值字段不同。以后可能会对其进行编辑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207

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

F＃中的最低实现，此功能是根据给定的键值对序列构建哈希表并返回一个在哈希表中搜索与给定键关联的值的函数：

1
2
3
4
5
6

> 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

对于可能使用上面代码的人，请注意内存泄漏：

1
2
3
4

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

并完成代码：

1
2
3
4
5
6
7
8
9
10
11

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

我认为您需要更具体一些。关于以下选项，哈希表有多种变体