你将如何在x语言中实现哈希表？

Question

这个问题的关键是使用不同语言的数组收集哈希表实现的示例列表.如果有人能够详细了解它们的工作原理以及每个例子的情况,那也很好.

编辑:

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

因为我们应该知道哈希表是如何工作的并且能够实现它们.这可能看起来不是一个非常重要的主题,但了解最常用的数据结构之一对我来说非常重要.如果这是成为编程的维基百科,那么这些是我将来到这里的一些类型的问题.我不是要在这里写一本CS书.我可以下载现成的算法Intro并阅读有关哈希表的章节并获取该类型的信息.更具体地说,我正在寻找的是代码示例.不仅对我来说,而且对于那些可能有一天会搜索类似信息并偶然发现此页面的人也是如此.

更具体一点:如果你必须实现它们,并且不能使用内置函数,你会怎么做？

您不需要在此处输入代码.把它放在pastebin中,然后链接它.

Answer 1

哈希表一种数据结构,允许在恒定时间内查找项目.它通过散列值并将该值转换为数组中的偏移量来工作.哈希表的概念相当容易理解,但实现起来显然更难.我不是在这里粘贴整个哈希表,但这里是我几周前在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 2

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

Answer 3

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

哈希函数将一个(希望)未使用的索引的密钥哈希到数组中.然后将该值放入该特定索引处的数组中.

数据检索很容易,因为可以通过哈希函数计算数组的索引,因此查找是~O(1).

当哈希函数将2个不同的键映射到同一个索引时会出现问题...有很多方法可以解决这个问题,我在这里不详述......

散列表是快速存储和检索数据的基本方法,并且几乎在所有编程语言库中都"内置".

Answer 4

我认为你需要更具体一点。哈希表在以下选项方面有多种变体

• 哈希表是固定大小的还是动态的？
• 使用什么类型的哈希函数？
• 调整哈希表大小时是否存在性能限制？

这个清单还可以一直列下去。这些限制中的每一个都可能导致任何语言的多种实现。

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