如何在语言x中实现一个散列表?

The point of this question is to collect a list of examples of hashtable implementations using arrays in different languages. It would also be nice if someone could throw in a pretty detailed overview of how they work, and what is happening with each example.

这个问题的重点是收集使用不同语言中的数组的hashtable实现示例的列表。如果有人能详细介绍一下他们的工作方式，以及每个示例的情况，那就更好了。

Edit:

编辑:

Why not just use the built in hash functions in your specific language?

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

Because we should know how hash tables work and be able to implement them. This may not seem like a super important topic, but knowing how one of the most used data structures works seems pretty important to me. If this is to become the wikipedia of programming, then these are some of the types of questions that I will come here for. I'm not looking for a CS book to be written here. I could go pull Intro to Algorithms off the shelf and read up on the chapter on hash tables and get that type of info. More specifically what I am looking for are code examples. Not only for me in particular, but also for others who would maybe one day be searching for similar info and stumble across this page.

因为我们应该知道哈希表是如何工作的，并且能够实现它们。这似乎不是一个非常重要的话题，但是知道一个最常用的数据结构是如何工作的对我来说是非常重要的。如果这将成为编程的*，那么这些就是我来这里的问题。我不是在找一本CS的书。我可以把算法的介绍从架子上拿下来读哈希表的那一章，然后得到那种类型的信息。更具体地说，我正在寻找的是代码示例。不仅对我来说是特别的，对那些可能有一天会搜索类似信息并偶然发现这个页面的人来说也是如此。

To be more specific: If you had to implement them, and could not use built-in functions, how would you do it?

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

You don't need to put the code here. Put it in pastebin and just link it.

你不需要把代码放在这里。把它放到pastebin中并链接它。

9 个解决方案

#1

A hash table a data structure that allows lookup of items in constant time. It works by hashing a value and converting that value to an offset in an array. The concept of a hash table is fairly easy to understand, but implementing is obviously harder. I'm not pasting the whole hash table here, but here are some snippets of a hash table I made in C a few weeks ago...

哈希表一种数据结构，允许在固定时间内查找项。它通过散列一个值并将该值转换为数组中的偏移量来工作。哈希表的概念很容易理解，但是实现哈希表显然更难。我不是在这里粘贴整个哈希表，但是这里有一些我几个星期前用C做的哈希表的片段……

One of the basics of creating a hash table is having a good hash function. I used the djb2 hash function in my hash table:

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

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

Then comes the actual code itself for creating and managing the buckets in the table

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

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 finds the last node in the linked list and appends a new node to it.

AppendLinkedNode找到链表中的最后一个节点，并向它追加一个新节点。

The code would be used like this:

守则的用途如下:

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

Finding a node is a simple as:

找到一个节点很简单，如:

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

And is used as follows:

并使用如下:

char* value = FindNode("10");

#2

A Java implementation in < 60 LoC

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

#3

A HashTable is a really simple concept: it is an array in which key and value pairs are placed into, (like an associative array) by the following scheme:

HashTable是一个非常简单的概念:它是一个数组，其中的键和值对被放置到(像一个关联数组)中，通过以下方案:

A hash function hashes the key to a (hopefully) unused index into the array. the value is then placed into the array at that particular index.

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

Data retrieval is easy, as the index into the array can be calculated via the hash function, thus look up is ~ O(1).

数据检索很简单，因为数组中的索引可以通过哈希函数来计算，所以查找是~ O(1)。

A problem arises when a hash function maps 2 different keys to the same index...there are many ways of handling this which I will not detail here...

当一个哈希函数将两个不同的键映射到同一个索引时，问题就出现了。有很多方法来处理这个问题，这里我不详细说明……

Hash tables are a fundamental way of storing and retrieving data quickly, and are "built in" in nearly all programming language libraries.

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

#4

I was looking for a completely portable C hash table implementation and became interested in how to implement one myself. After searching around a bit I found: Julienne Walker's The Art of Hashing which has some great tutorials on hashing and hash tables. Implementing them is a bit more complex than I thought but it was a great read.

我正在寻找一个完全可移植的C哈希表实现，并对如何自己实现它产生了兴趣。搜索了一下之后，我找到了:Julienne Walker的《哈希的艺术》，里面有一些关于哈希和哈希表的教程。实现它们比我想象的要复杂一些，但是这是一个很好的阅读。

#5

Here is my code for a Hash Table, implemented in Java. Suffers from a minor glitch- the key and value fields are not the same. Might edit that in the future.

这是我的哈希表代码，用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;
            }
        }
    }
}

#6

I think you need to be a little more specific. There are several variations on hashtables with regards to the following options

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

Is the hashtable fixed-size or dynamic?
哈希表是固定大小的还是动态的?
What type of hash function is used?
使用什么类型的哈希函数?
Are there any performance constraints when the hashtable is resized?
哈希表调整大小时是否存在性能约束?

The list can go on and on. Each of these constraints could lead to multiple implementations in any language.

这个列表可以一直列下去。每个约束都可能导致任何语言的多个实现。

Personally, I would just use the built-in hashtable that is available in my language of choice. The only reason I would even consider implementing my own would be due to performance issues, and even then it is difficult to beat most existing implementations.

就我个人而言，我只使用我选择的语言中可用的内置hashtable。我甚至会考虑实现我自己的实现的唯一原因是性能问题，即使这样，也很难打败大多数现有的实现。

#7

For those who may use the code above, note the memory leak:

对于可能使用上述代码的用户，请注意内存泄漏:

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

And to complete the code:

并完成代码:

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

#8

Minimal implementation in F# as a function that builds a hash table from a given sequence of key-value pairs and returns a function that searches the hash table for the value associated with the given key:

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

#9

-1

I went and read some of the Wikipedia-page on hashing: http://en.wikipedia.org/wiki/Hash_table. It seems like a lot of work, to put up code for a hashtable here, especially since most languages I use allready have them built in. Why would you want implementations here? This stuff really belongs in a languages library.

我去读了一些关于哈希的*页面:http://en.wikipedia.org/wiki/Hash_table。在这里编写一个hashtable代码似乎需要大量的工作，特别是因为我使用的大多数语言都是内置的。为什么需要实现呢?这些东西确实属于一个语言库。

Please elaborate on what your expected solutions should include:

请详细说明您期望的解决方案应该包括以下内容:

hash function
哈希函数
variable bucket count
变量桶数
collision behavior
碰撞行为

Also state what the purpose of collecting them here is. Any serious implementation will easily be quite a mouthfull = this will lead to very long answers (possibly a few pages long each). You might also be enticing people to copy code from a library...

还要说明在这里收集它们的目的是什么。任何认真的实现都很容易让人大开眼界(这将导致非常长的答案(每个可能有几页长)。您可能还在诱使人们从库中复制代码……

#1