你将如何实现X语言哈希表？ [英] How would you implement a hashtable in language x?

问题描述

这个问题的关键是要收集使用数组不同语言的哈希表实现的示例清单。这也将是很好，如果有人可以，他们是如何工作的一个pretty详细概述扔，什么是与每个例子发生。

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.

编辑：

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

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

由于我们应该知道哈希表是如何工作的，并能够实现它们。这似乎并不像一个超级重要的话题，但知道如何最常用的数据结构工程之一，似乎pretty对我很重要。如果这是成为编程的维基百科，那么这些都是一些类型的问题，我会来这里的。我不是在寻找在这里写了一本书CS。我可以去拉简介算法现成的和关于哈希表的章念起来得到类型信息的。更具体是什么我期待的是的 code例子。不仅是对我特别，也为别人谁也说不定哪一天会寻找类似信息并在此页面绊倒。

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.

要更具体：如果你有实施他们，不能使用内置函数，你会怎么办呢？

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

您不必在这里把code。把它放在引擎收录，只是链接。

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

推荐答案

一个哈希表的数据结构，允许在固定时间内的项目查找。它的工作原理是散列值，并且该值转换为以阵列偏移。哈希表的概念是相当容易理解，但实施显然更难。我不是在这里粘贴整个哈希表，但这里有一个哈希表我在C几个星期前的一些片段...

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...

创建一个哈希表的基础知识是有一个好的哈希函数。我在哈希表中使用的djb2散列函数：

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:

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

然后是实际code本身创造和表管理桶

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发现链表的最后一个节点，并追加新的节点了。

AppendLinkedNode finds the last node in the linked list and appends a new node to it.

在code将用于如下：

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

和使用如下：

char* value = FindNode("10");

这篇关于你将如何实现X语言哈希表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！