基于磁盘的散列表

一个简单的基于磁盘的散列表（即持久化散列表）。

它是一个在内存映射磁盘上实现的散列表，因此可以通过单个mmap()系统调用加载并直接在内存中使用（一旦从磁盘加载，其速度与内存散列表一样快）。

代码是用C编写的，提供了Python、Haskell和C++的包装器。包装器遵循类似的API，并针对语言特性进行了调整。它们都使用相同的底层代码，因此您可以从C中打开在Haskell中创建的散列表，在Haskell代码中修改它，然后稍后在Python中打开结果。

跨语言功能仅适用于您可以控制其二进制表示的简单类型（例如64位整数）。

读取根本不会触及磁盘表示，因此可以在只读文件上执行或在多个线程（不同进程将共享内存：操作系统会为您做这件事）中使用。但是，写入或修改值不是线程安全的。

示例

以下示例都创建一个散列表来存储长整型（int64_t），然后将与键"key"相关联的值设置为9。在当前的API中，需要预先指定键的最大大小，如下面的值15。

原始C

#include <stdio.h>
#include <inttypes.h>
#include "diskhash.h"

int main(void) {
    HashTableOpts opts;
    opts.key_maxlen = 15;
    opts.object_datalen = sizeof(int64_t);
    char* err = NULL;
    HashTable* ht = dht_open("testing.dht", opts, O_RDWR|O_CREAT, &err);
    if (!ht) {
        if (!err) err = "Unknown error";
        fprintf(stderr, "Failed opening hash table: %s.\n", err);
        return 1;
    }
    long i = 9;
    dht_insert(ht, "key", &i);
    
    long* val = (long*) dht_lookup(ht, "key");
    printf("Looked up value: %l\n", *val);

    dht_free(ht);
    return 0;
}

C API依赖于错误代码和错误字符串（上面的&err参数）。头文件有 不错的文档。

Haskell

在Haskell中，读写哈希表和只读哈希表有不同的类型/函数。读写操作是IO操作，只读哈希表是纯的。

读写示例

import Data.DiskHash
import Data.Int
main = do
    ht <- htOpenRW "testing.dht" 15
    htInsertRW ht "key" (9 :: Int64)
    val <- htLookupRW "key" ht
    print val

只读示例（在这种情况下，htLookupRO是纯的）

import Data.DiskHash
import Data.Int
main = do
    ht <- htOpenRO "testing.dht" 15
    let val :: Int64
        val = htLookupRO "key" ht
    print val

Python

Python的接口基于struct模块。例如，'ll'指的是一对64位整型（长整型）

import diskhash
tb = diskhash.StructHash("testing.dht", 15, 'll', 'rw')
tb.insert("key", 1, 2)
print(tb.lookup("key"))

Python接口目前只支持Python 3。欢迎提供将之扩展到2.7的补丁，但这不是优先事项。

C++

在C++中定义了一个简单的包装器，它提供了一定程度的类型安全性。您使用DiskHash<T>模板。此外，错误通过异常报告（可以抛出std::bad_alloc和std::runtime_error异常）而不是返回代码。

#include <iostream>
#include <string>

#include <diskhash.hpp>

int main() {
    const int key_maxlen = 15;
    dht::DiskHash<uint64_t> ht("testing.dht", key_maxlen, dht::DHOpenRW);
    std::string line;
    uint64_t ix = 0;
    while (std::getline(std::cine, line)) {
        if (line.length() > key_maxlen) {
            std::cerr << "Key too long: '" << line << "'. Aborting.\n";
            return 2;
        }
        const bool inserted = ht.insert(line.c_str(), ix);
        if (!inserted) {
            std::cerr  << "Found repeated key '" << line << "' (ignored).\n";
        }
        ++ix;
    }
    return 0;
}

稳定性

这是一个beta软件。它足够好，以至于我在使用它，但API将来可能会在没有太多警告的情况下更改。二进制格式是版本化的（魔数字符串包含其版本，因此可以检测更改，并且在将来您将收到错误消息而不是某些无声的错误行为）。

自动单元测试确保基本错误不会被遗漏。

限制

• 您必须指定最大键大小。这可以通过预先对键进行哈希处理（使用强哈希）或使用多个不同键大小的哈希表来解决。这两种方法目前都没有在diskhash中实现。

• 您不能删除对象。这对我来说不是必需的，因此没有实现。可以通过在对象上标记为“已删除”并在哈希表大小更改时或显式调用dht_gc()来重新压缩来简单实现。还可能需要添加功能以缩小哈希表，以便不浪费磁盘空间。

• 算法是线性地址的相对简单的实现。切换到robin hood哈希并不难，这可能在不久的将来发生。

许可证：MIT