c - 如何使此集合哈希代码起作用？

集合散列是一种算法，它解决了与一致散列相同的问题：
…允许客户端实现分布式协议的算法
将给定对象放置在哪个站点（或代理）上。
集合哈希具有以下属性。
低开销：使用的哈希函数是高效的，因此客户端的开销非常低。
负载平衡：由于散列函数是随机的，所以n个站点中的每一个都有可能接收到对象O
穿过各个地点。
高命中率：由于所有客户端都同意将对象O放置到同一站点中，因此，每次获取或放置O时，都会产生
最大命中率的效用。对象o将始终是
找到它，除非它在so被某个替换算法逐出。
最小中断：当站点失败时，只需要重新映射映射映射到该站点的对象。破坏是在尽可能小的范围内
水平，如
[1]。
-Wikipedia: Rendezvous hashing
好极了。现在，我已经实现了一个修改版本，它将一组密钥映射到before的存储箱中，并且看起来工作得非常出色：
斯宾斯C：

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <limits.h>

#include <assert.h>

#include <math.h>

//#include <blake2.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

#define NODES   20
#define KEYS    16777216
#define CSKIP   1048576

__uint128_t hashes[NODES]   = {0};
int count[NODES]    = {0};

static inline int rendezvous (__uint128_t *pool, uint64_t id) {
    register int x, bin = 0;
    register __uint128_t max = 0, cache;

    for (x = 0; x < NODES; x++) {
//      blake2 ((void *) &cache, &pool[x], &id, sizeof (cache), sizeof (pool[x]), sizeof (id));
        cache = pool[x] * ~id;
        max = MAX (max, cache);
        bin = max == cache ? x : bin;
    }

    return bin;
}

int main (int argc, char **argv) {
    assert (fread (hashes, sizeof (hashes[0]), NODES, stdin) == NODES);

    register int x, bin;
    for (x = 0; x < KEYS; x++) {
        bin = rendezvous (hashes, x);
        count[bin]++;
        if (!(x % CSKIP)) {fprintf (stdout, "%i\n", x);}
    }

    fputs ("\n\n\n\n\n\n\n\n", stdout);

    float avg = (float) KEYS / (float) NODES;

    float mad = 0;
    for (x = 0; x < NODES; x++) {
        fprintf (stdout, "Bin %i\t: %i\n", x, count[x]);
        mad += abs ((float) count[x] - avg);
    }

    fputs ("\n\n\n\n\n\n\n\n", stdout);

    fprintf (stdout, "avg: keys/bin\t= %f\n", avg);

    mad /= (float) NODES;
    fprintf (stdout, "mad: keys/bin\t= %f\n", mad);

    float moa = mad / avg;
    moa *= 100;
    fprintf (stdout, "mad / avg\t= %05.2f %%\n", moa);

    return 0;
}

当使用gcc sbins.c -lm编译并使用cat /dev/urandom | ./a.out运行时，它似乎分布得相当好：

1048576
2097152
3145728
4194304
5242880
6291456
7340032
8388608
9437184
10485760
11534336
12582912
13631488
14680064
15728640








Bin 0   : 838966
Bin 1   : 838596
Bin 2   : 839535
Bin 3   : 838835
Bin 4   : 839220
Bin 5   : 838759
Bin 6   : 838907
Bin 7   : 838903
Bin 8   : 838302
Bin 9   : 838726
Bin 10  : 838522
Bin 11  : 838034
Bin 12  : 839020
Bin 13  : 839334
Bin 14  : 838898
Bin 15  : 838905
Bin 16  : 838984
Bin 17  : 838753
Bin 18  : 838956
Bin 19  : 839061








avg: keys/bin   = 838860.812500
mad: keys/bin   = 235.500000
mad / avg   = 00.03 %

到目前为止，一切都好。所以过了一段时间（也就是现在），我实际上需要编写使用它的代码我知道我需要副本，所以我想我只需存储、排序和返回一个列表，而不是总是选择最高的值最后，为了完成这项任务，我在两个文件中创建了一组类似的例程，基于上面所写的内容：
rendezvous.h（包含实际集合代码的头文件）：

#pragma once
// adapted from
// http://git.io/pgkqvw
// (haneefmubarak/experiments/rendezvous)

//===   Includes

#include <stdint.h>
#include <stdlib.h>

//===   Structures

typedef struct {
    __uint128_t val;
    int bin;
} rdv;

//===   Special

#define SORT_NAME rendezvous
#define SORT_TYPE rdv
#define SORT_CMP(x, y) ((((rdv)x).val) - (((rdv)y).val))
#include "./deps/sort/sort.h"

//===   Functions

static inline int *rendezvous (__uint128_t *pool, uint64_t id, int nodes) {

    register int x;

    // store temporary results
    rdv *cache  = malloc (nodes * sizeof (rdv));
    if (!cache)
        return NULL;
    int *bin    = malloc (nodes * sizeof (int));
    if (!bin) {
        free (cache);
        return NULL;
    }

    // calculate for each server
    for (x = 0; x < nodes; x++) {
        cache[x].val    = pool[x] * ~id;
        cache[x].bin    = x;
    }

    // sort the results
    rendezvous_tim_sort (cache, nodes);

    // extract the results
    for (x = 0; x < nodes; x++) {
        bin[x] = cache[x].bin;
    }

    // cleanup
    free (cache);

    return bin;
}

还有一个测试程序：
试验/会合.c（试验）：

#include <stdio.h>
#include <assert.h>
#include "../rendezvous.h"

#define NODES   20
#define REPFAC  4
#define KEYS    16777216
#define CSKIP   1048576

__uint128_t hashes[NODES]   = {0};
int count[REPFAC][NODES]    = {{0}};

int main (int argc, char **argv) {
    assert (fread (hashes, sizeof (hashes[0]), NODES, stdin) == NODES);

    register uint64_t x, y;
    register int *bin;
    for (x = 0; x < KEYS; x++) {
        bin = rendezvous (hashes, x, NODES);
        for (y = 0; y < REPFAC; y++)
            count[y][bin[y]] += 1;
        free (bin);
        if (!(x % CSKIP)) {fprintf (stdout, "%llu\n", x);}
    }

    for (x = 0; x < REPFAC; x++) {
        fputs ("\n\n\n\n\n\n\n\n", stdout);
        fprintf (stdout, "RepSet %llu\n", x);
        for (y = 0; y < NODES; y++)
            fprintf (stdout, "Bin %llu\t: %i\n", y, count[x][y]);
    }

    return 0;
}

注意：文件“sort.h”来自github:swenson/sort。
但是，当使用gcc rendezvous.c编译此文件并使用cat /dev/urandom | ./a.out运行它时，代码似乎失败了：

0
1048576
2097152
3145728
4194304
5242880
6291456
7340032
8388608
9437184
10485760
11534336
12582912
13631488
14680064
15728640








RepSet 0
Bin 0   : 0
Bin 1   : 16777216
Bin 2   : 0
Bin 3   : 0
Bin 4   : 0
Bin 5   : 0
Bin 6   : 0
Bin 7   : 0
Bin 8   : 0
Bin 9   : 0
Bin 10  : 0
Bin 11  : 0
Bin 12  : 0
Bin 13  : 0
Bin 14  : 0
Bin 15  : 0
Bin 16  : 0
Bin 17  : 0
Bin 18  : 0
Bin 19  : 0








RepSet 1
Bin 0   : 0
Bin 1   : 0
Bin 2   : 16777216
Bin 3   : 0
Bin 4   : 0
Bin 5   : 0
Bin 6   : 0
Bin 7   : 0
Bin 8   : 0
Bin 9   : 0
Bin 10  : 0
Bin 11  : 0
Bin 12  : 0
Bin 13  : 0
Bin 14  : 0
Bin 15  : 0
Bin 16  : 0
Bin 17  : 0
Bin 18  : 0
Bin 19  : 0








RepSet 2
Bin 0   : 0
Bin 1   : 0
Bin 2   : 0
Bin 3   : 16777216
Bin 4   : 0
Bin 5   : 0
Bin 6   : 0
Bin 7   : 0
Bin 8   : 0
Bin 9   : 0
Bin 10  : 0
Bin 11  : 0
Bin 12  : 0
Bin 13  : 0
Bin 14  : 0
Bin 15  : 0
Bin 16  : 0
Bin 17  : 0
Bin 18  : 0
Bin 19  : 0








RepSet 3
Bin 0   : 0
Bin 1   : 0
Bin 2   : 0
Bin 3   : 0
Bin 4   : 16777216
Bin 5   : 0
Bin 6   : 0
Bin 7   : 0
Bin 8   : 0
Bin 9   : 0
Bin 10  : 0
Bin 11  : 0
Bin 12  : 0
Bin 13  : 0
Bin 14  : 0
Bin 15  : 0
Bin 16  : 0
Bin 17  : 0
Bin 18  : 0
Bin 19  : 0

我试图找出问题的原因。我甚至认为我可能有一个优先级问题，或者有什么count[y][bin[y]]++的问题，所以我改变了，但是没有用我认为错误在rendezvous.h中，但在这一点上，我几乎没有什么想法，也没有任何线索。
理想情况下，第二个程序的输出应该均匀分布，类似于第一个程序。但我找不到唯一一个被填满的箱子。
那么我怎样才能让程序正常工作呢如有任何帮助，我们将不胜感激。

最佳答案

重新调整比较器算法请记住，您使用的是无符号值。因此，这方面的比较器：

#define SORT_CMP(x, y) ((((rdv)x).val) - (((rdv)y).val))

如果x.val永远小于y.val将下溢。反过来，这又使得任何人假设一个标准的“负、零、正”结果来规定“少、等、大”都将失败。它们都将是“更大的”（假设底流返回正数；陷阱条件不受影响；技术上是它的ub），或者充其量是“相等的”…好。。。平等。
我修改了您的代码以使用qsort()和一个比较器，简单地说：

int cmp_rdv(const void *arg1, const void* arg2)
{
    const rdv* lhs = arg1;
    const rdv* rhs = arg2;
    return (lhs->val < rhs->val) ? -1 : (rhs->val < lhs->val);
}

然后按原样调用它，抛出旧算法：

// calculate for each server
for (x = 0; x < nodes; x++) {
    cache[x].val    = pool[x] * ~id;
    cache[x].bin    = x;
}

// sort the results
qsort(cache, nodes, sizeof(*cache), cmp_rdv);

// extract the results
for (x = 0; x < nodes; x++) {
    bin[x] = cache[x].bin;
}

结果如下，很可能是你要找的（我清理了墙壁上的新线，为自己的理智添加了一些禁忌）。

0
1048576
2097152
3145728
4194304
5242880
6291456
7340032
8388608
9437184
10485760
11534336
12582912
13631488
14680064
15728640


RepSet 0
    Bin 0   : 838214
    Bin 1   : 838719
    Bin 2   : 838792
    Bin 3   : 839251
    Bin 4   : 838699
    Bin 5   : 838436
    Bin 6   : 838827
    Bin 7   : 839038
    Bin 8   : 839062
    Bin 9   : 838787
    Bin 10  : 839000
    Bin 11  : 838683
    Bin 12  : 839024
    Bin 13  : 838922
    Bin 14  : 838847
    Bin 15  : 839312
    Bin 16  : 838980
    Bin 17  : 838607
    Bin 18  : 839191
    Bin 19  : 838825


RepSet 1
    Bin 0   : 840405
    Bin 1   : 838603
    Bin 2   : 838612
    Bin 3   : 837891
    Bin 4   : 839700
    Bin 5   : 839559
    Bin 6   : 838918
    Bin 7   : 838834
    Bin 8   : 839128
    Bin 9   : 838711
    Bin 10  : 838930
    Bin 11  : 839856
    Bin 12  : 838654
    Bin 13  : 837914
    Bin 14  : 838665
    Bin 15  : 837965
    Bin 16  : 838278
    Bin 17  : 839167
    Bin 18  : 837817
    Bin 19  : 839609


RepSet 2
    Bin 0   : 838054
    Bin 1   : 838727
    Bin 2   : 838852
    Bin 3   : 839306
    Bin 4   : 837806
    Bin 5   : 838103
    Bin 6   : 838929
    Bin 7   : 837990
    Bin 8   : 837851
    Bin 9   : 838877
    Bin 10  : 838228
    Bin 11  : 837360
    Bin 12  : 839282
    Bin 13  : 840473
    Bin 14  : 839353
    Bin 15  : 840022
    Bin 16  : 840401
    Bin 17  : 838826
    Bin 18  : 840139
    Bin 19  : 838637


RepSet 3
    Bin 0   : 838545
    Bin 1   : 840246
    Bin 2   : 839210
    Bin 3   : 839441
    Bin 4   : 838555
    Bin 5   : 838835
    Bin 6   : 838539
    Bin 7   : 839562
    Bin 8   : 838275
    Bin 9   : 839164
    Bin 10  : 839194
    Bin 11  : 840005
    Bin 12  : 838463
    Bin 13  : 837821
    Bin 14  : 839498
    Bin 15  : 838393
    Bin 16  : 837376
    Bin 17  : 838632
    Bin 18  : 839393
    Bin 19  : 838069

我没有下载你提到的分类源，只是因为我很懒（为什么撒谎？）。但我确实检查了当您不提供时默认值是什么，它是：

#define SORT_CMP(x, y)  ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))

证实我的怀疑，他们需要我们都习惯提供的小于零/大于零的标准三重奏你可能需要你的jus算法来匹配这个格式，它会给你你想要的。
祝你好运。

关于c - 如何使此集合哈希代码起作用？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25589098/