指针的最快哈希函数是什么？

Question

哈希表基于容器是非常快速的关联数组（例如 unordered_map, unordered_set）。

它们的性能高度依赖于用于为每个条目创建索引的哈希函数。随着哈希表的增长，元素会一遍又一遍地进行重新哈希。

指针是简单类型，基本上是一个4/8字节的值，可以唯一标识对象。问题在于，使用地址作为哈希函数的结果不高效，因为有多个最低有效位为零。

示例：

struct MyVoidPointerHash {
    size_t operator()(const void* val) const {
        return (size_t)val;
    }
};

更快的实现方法是丢失一些比特：

struct MyVoidPointerHash2 {
    size_t operator()(const void* val) const {
        return ((size_t)val) >> 3; // 3 on 64 bit, 1 on 32 bit
    }
};

后者在使用具有数万个元素的哈希集和映射，并且经常构建和清除时，可以提高10-20％的性能。

有人可以提供更好的指针哈希方案吗？

这个函数需要：

1. 快速！并且必须很好地内联。
2. 提供合理的分布，允许偶尔碰撞。

更新 - 基准测试结果

我运行了两组测试，一组是针对 int* 和一个大小为4KB的类指针。结果非常有趣。

我对所有测试使用了 std::unordered_set，数据大小为16MB，这些数据是在单个 new 调用中分配的。第一个算法运行了两次，以确保缓存尽可能热，CPU以最大速度运行。

设置：VS2013（x64），i7-2600，Windows 8.1 x64。

• VS2013 默认哈希函数
• Hash1: return (size_t)(val);
• Hash2: return '(size_t)(val) >> 3;
• Hash3(@BasileStarynkevitch): uintptr_t ad = (uintptr_t)val; return (size_t)((13 * ad) ^ (ad >> 15));
• Hash4(@Roddy): uintptr_t ad = (uintptr_t)val; return (size_t)(ad ^ (ad >> 16));
• Hash5(@egur):

代码：

template<typename Tval>
struct MyTemplatePointerHash1 {
    size_t operator()(const Tval* val) const {
        static const size_t shift = (size_t)log2(1 + sizeof(Tval));
        return (size_t)(val) >> shift;
    }
};

测试1-int*：

• VS2013默认情况下需要1292毫秒
• Hash1需要742毫秒
• Hash2需要343毫秒
• Hash3需要1008毫秒
• Hash4需要629毫秒
• Hash5需要350毫秒

测试1-4K_class*：

• VS2013默认情况下需要0.423毫秒
• Hash1需要23.889毫秒
• Hash2需要6.331毫秒
• Hash3需要0.366毫秒
• Hash4需要0.390毫秒
• Hash5需要0.290毫秒

更新2：

目前最优秀的是模板化哈希（Hash5）函数。适用于不同块大小的速度性能最佳。

更新3：

添加了基准的默认哈希函数。结果发现它远非最优。

- egur

---

这种移位取决于你的 T 在 unordered_set<T> 中的对齐方式。例如，当 T 是一个 32 位的 int 时，在 32 位和 64 位机器上只有最低的 2 位是 0。 - Maxim Egorushkin

@MaximYegorushkin，int不是指针。由malloc/new返回的32位指针有1个零LSB，64位指针有3个零LSB。当然，您可以拥有不是malloc/new结果的指针，因此如果对象足够小，则会发生一些冲突。 - egur

抱歉，我实际上是指unordered_set<int*>。那些'int'可以被存储在其他位置的数组中，因此自然情况下，在32位和64位平台上，'int*'将只有2个零LSB。 - Maxim Egorushkin

测试代码在Test1和Test2中基本上有所不同吗？最快时间相差1000倍...？虽然很有趣！ - Roddy

由于块大小增加了1000倍，我使用了较少的块。如果我使用更多的块，数字是一致的（+-2%）。 - egur

Answer 1

从理论上讲，正确的答案是：使用可能专门为此而设计的std::hash，如果不适用，则使用良好的哈希函数而不是快速的哈希函数。哈希函数的速度并不那么重要，它的质量才更为重要。

实际上，答案是：使用std::hash，它很差劲，但表现出人意料之外的好。

在产生兴趣后，我在周末进行了约30小时的基准测试。除其他事项外，我试图获得平均情况与最坏情况，并尝试通过在插入的集合大小方面故意提供错误的桶计数提示，来迫使std::unordered_map呈现最坏情况的行为。

我比较了糟糕哈希值（std::hash<T*>）和著名的通用哈希值（djb2、sdbm），以及针对非常短的输入长度的这些变体，以及专门用于哈希表的哈希值（murmur2 和 murmur3），还有非常糟糕的哈希值，它们实际上比不进行哈希还要糟糕，因为它们丢失了熵。
由于指针的最低2-3位由于对齐而始终为零，因此我认为测试简单右移作为“哈希”是值得的，因此只使用非零信息，以防哈希表例如仅使用最低 N 位。结果证明，对于合理的移位（我也尝试过不合理的移位！）这实际上表现得相当好。

发现

我的一些发现是众所周知且毫不意外的，而其他的则非常惊人：

• 很难预测什么是“好”的哈希函数。编写好的哈希函数很困难。这不足为奇，是一个众所周知的事实，并再次得到证明。
• 没有单个哈希函数在每种情况下都显著优于其他所有哈希函数。没有单个哈希函数甚至在80％的时间内显着优于其他所有哈希函数。第一个结果是可以预料的，第二个结果尽管令人惊讶。
• 很难使std::unordered_map表现不佳。即使给出故意错误的桶计数提示，强制进行多次重新哈希，总体性能也不会差太多。只有那些以几乎荒谬的方式丢弃大部分熵的最坏的哈希函数才能显着影响性能超过10-20％（例如right_shift_12，它实际上为50,000个输入产生了仅12个不同的哈希值！在这种情况下，哈希映射运行约慢100倍-我们基本上在链表上进行随机访问查找。）。
• 一些“有趣”的结果肯定是由于实现细节造成的。我的实现（GCC）使用略大于2 ^ N的素数桶计数，并将具有相同哈希值的值以头部优先插入到链接列表中。
• std::hash<T * >的特化对于GCC来说非常糟糕（一个简单的reinterpret_cast）。有趣的是，一个做完全相同事情的函数对象在插入时表现更快，在随机访问时表现更慢。差异很小（在8-10秒的测试运行中有几十毫秒），但它不是噪音，它始终存在-可能与指令重排或流水线相关。这个代码完全相同的情况下，两种不同场景下的表现一致不同，这真是太惊人了。
• 可怜的哈希函数并不比“好”的哈希函数或专门设计用于哈希表的哈希函数表现得更差。实际上，它们有一半的时间是最好的表现者，或者是前三名之一。
• “最佳”哈希函数很少能够产生最佳的整体性能。
• 在此SO问题中发布的哈希函数通常是可以接受的。它们是良好的平均值，但不优于std::hash。通常它们会排在前3-4位。
• 较差的哈希函数对插入顺序有一定的敏感性（在随机插入和随机查找之后进行随机查找时表现更差），而“好”的哈希函数对插入顺序的影响更具弹性（几乎没有差异），但总体性能仍然稍慢。

测试设置

测试不仅针对任意的4字节或8字节（或其他）对齐的值，而是针对从堆上分配完整元素集合获得的实际地址进行的，并将地址存储在std::vector中由分配器提供（然后删除对象，它们不再需要）。
地址按照存储在向量中的顺序插入到新分配的std::unordered_map中，一次按原始顺序（"sequential"），一次在向量上应用std::random_shuffle后。

对大小为4、16、64、256和1024的50,000和1,000,000个对象进行了测试（此处省略了64的结果，因为篇幅过长，它们位于16和256之间-- StackOverflow只允许发布30k个字符）。
测试套件运行3次，结果有时相差3或4毫秒，但整体上是相同的。这里发布的结果是最后一次运行的结果。

"随机"测试中插入的顺序以及访问模式（在每个测试中）是伪随机的，但在测试运行中，每个哈希函数的顺序完全相同。

哈希基准测试中的时间是为了将4,000,000,000个哈希值相加到一个整数变量中。

列insert是以毫秒为单位的时间，用于创建50个元素的std::unordered_map，分别插入50,000和1,000,000个元素，并销毁该映射表的50次迭代。

列access是以毫秒为单位的时间，用于在“vector”中查找100,000,000个伪随机元素，然后在unordered_map中查找该地址。
对于大数据集（小数据集完全适合于L2），这个时间包括平均一个缓存未命中来访问vector中的随机元素。

所有时间都在2.66GHz Intel Core2，Windows 7，gcc 4.8.1/MinGW-w64_32上进行。计时器粒度@ 1ms。

源代码

源代码在Ideone上可用，这是因为Stackoverflow有30k字符限制。

注意：在台式电脑上运行完整的测试套件需要超过2小时，因此如果您想重现结果，请准备好散步。

测试结果

Benchmarking hash funcs...
std::hash                 2576      
reinterpret_cast          2561      
djb2                      13970     
djb2_mod                  13969     
sdbm                      10246     
yet_another_lc            13966     
murmur2                   11373     
murmur3                   15129     
simple_xorshift           7829      
double_xorshift           13567     
right_shift_2             5806      
right_shift_3             5866      
right_shift_4             5705      
right_shift_5             5691      
right_shift_8             5795      
right_shift_12            5728      
MyTemplatePointerHash1    5652      
BasileStarynkevitch       4315      

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 421        6988       
reinterpret_cast          408        7083       
djb2                      451        8875       
djb2_mod                  450        8815       
sdbm                      455        8673       
yet_another_lc            443        8292       
murmur2                   478        9006       
murmur3                   490        9213       
simple_xorshift           460        8591       
double_xorshift           477        8839       
right_shift_2             416        7144       
right_shift_3             422        7145       
right_shift_4             414        6811       
right_shift_5             425        8006       
right_shift_8             540        11787      
right_shift_12            1501       49604      
MyTemplatePointerHash1    410        7138       
BasileStarynkevitch       445        8014       

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 443        7570       
reinterpret_cast          436        7658       
djb2                      473        8791       
djb2_mod                  472        8766       
sdbm                      472        8817       
yet_another_lc            458        8419       
murmur2                   479        9005       
murmur3                   491        9205       
simple_xorshift           464        8591       
double_xorshift           476        8821       
right_shift_2             441        7724       
right_shift_3             440        7716       
right_shift_4             450        8061       
right_shift_5             463        8653       
right_shift_8             649        16320      
right_shift_12            3052       114185     
MyTemplatePointerHash1    438        7718       
BasileStarynkevitch       453        8140       

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 8945       32801      
reinterpret_cast          8796       33251      
djb2                      11139      54855      
djb2_mod                  11041      54831      
sdbm                      11459      36849      
yet_another_lc            14258      57350      
murmur2                   16300      39024      
murmur3                   16572      39221      
simple_xorshift           14930      38509      
double_xorshift           16192      38762      
right_shift_2             8843       33325      
right_shift_3             8791       32979      
right_shift_4             8818       32510      
right_shift_5             8775       30436      
right_shift_8             10505      35960      
right_shift_12            30481      91350      
MyTemplatePointerHash1    8800       33287      
BasileStarynkevitch       12885      37829      

--------------------------------
sizeof(T)       = 4
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 12183      33424      
reinterpret_cast          12125      34000      
djb2                      22693      51255      
djb2_mod                  22722      51266      
sdbm                      15160      37221      
yet_another_lc            24125      51850      
murmur2                   16273      39020      
murmur3                   16587      39270      
simple_xorshift           16031      38628      
double_xorshift           16233      38757      
right_shift_2             11181      33896      
right_shift_3             10785      33660      
right_shift_4             10615      33204      
right_shift_5             10357      38216      
right_shift_8             15445      100348     
right_shift_12            73773      1044919    
MyTemplatePointerHash1    11091      33883      
BasileStarynkevitch       15701      38092      

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 415        8243       
reinterpret_cast          422        8321       
djb2                      445        8730       
djb2_mod                  449        8696       
sdbm                      460        9439       
yet_another_lc            455        9003       
murmur2                   475        9109       
murmur3                   482        9313       
simple_xorshift           463        8694       
double_xorshift           465        8900       
right_shift_2             416        8402       
right_shift_3             418        8405       
right_shift_4             423        8366       
right_shift_5             421        8347       
right_shift_8             453        9195       
right_shift_12            666        18008      
MyTemplatePointerHash1    433        8191       
BasileStarynkevitch       466        8443       

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 450        8135       
reinterpret_cast          457        8208       
djb2                      470        8736       
djb2_mod                  476        8698       
sdbm                      483        9420       
yet_another_lc            476        8953       
murmur2                   481        9089       
murmur3                   486        9283       
simple_xorshift           466        8663       
double_xorshift           468        8865       
right_shift_2             456        8301       
right_shift_3             456        8302       
right_shift_4             453        8337       
right_shift_5             457        8340       
right_shift_8             505        10379      
right_shift_12            1099       34923      
MyTemplatePointerHash1    464        8226       
BasileStarynkevitch       466        8372       

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 9548       35362      
reinterpret_cast          9635       35869      
djb2                      10668      37339      
djb2_mod                  10763      37311      
sdbm                      11126      37145      
yet_another_lc            11597      39944      
murmur2                   16296      39029      
murmur3                   16432      39280      
simple_xorshift           16066      38645      
double_xorshift           16108      38778      
right_shift_2             8966       35953      
right_shift_3             8916       35949      
right_shift_4             8973       35504      
right_shift_5             8941       34997      
right_shift_8             9356       31233      
right_shift_12            13831      45799      
MyTemplatePointerHash1    8839       31798      
BasileStarynkevitch       15349      38223      

--------------------------------
sizeof(T)       = 64
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 14756      36237      
reinterpret_cast          14763      36918      
djb2                      15406      38771      
djb2_mod                  15551      38765      
sdbm                      14886      37078      
yet_another_lc            15700      40290      
murmur2                   16309      39024      
murmur3                   16432      39381      
simple_xorshift           16177      38625      
double_xorshift           16073      38750      
right_shift_2             14732      36961      
right_shift_3             14170      36965      
right_shift_4             13687      37295      
right_shift_5             11978      35135      
right_shift_8             11498      46930      
right_shift_12            25845      268052     
MyTemplatePointerHash1    10150      32046      
BasileStarynkevitch       15981      38143      

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 432        7957       
reinterpret_cast          429        8036       
djb2                      462        8970       
djb2_mod                  453        8884       
sdbm                      460        9110       
yet_another_lc            466        9015       
murmur2                   495        9147       
murmur3                   494        9300       
simple_xorshift           479        8792       
double_xorshift           477        8948       
right_shift_2             430        8120       
right_shift_3             429        8132       
right_shift_4             432        8196       
right_shift_5             437        8324       
right_shift_8             425        8050       
right_shift_12            519        11291      
MyTemplatePointerHash1    425        8069       
BasileStarynkevitch       468        8496       

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 462        7956       
reinterpret_cast          456        8046       
djb2                      490        9002       
djb2_mod                  483        8905       
sdbm                      482        9116       
yet_another_lc            492        8982       
murmur2                   492        9120       
murmur3                   492        9276       
simple_xorshift           477        8761       
double_xorshift           477        8903       
right_shift_2             458        8116       
right_shift_3             459        8124       
right_shift_4             462        8281       
right_shift_5             463        8370       
right_shift_8             458        8069       
right_shift_12            662        16244      
MyTemplatePointerHash1    459        8091       
BasileStarynkevitch       472        8476       

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 9756       34368      
reinterpret_cast          9718       34897      
djb2                      10935      36894      
djb2_mod                  10820      36788      
sdbm                      11084      37857      
yet_another_lc            11125      37996      
murmur2                   16522      39078      
murmur3                   16461      39314      
simple_xorshift           15982      38722      
double_xorshift           16151      38868      
right_shift_2             9611       34997      
right_shift_3             9571       35006      
right_shift_4             9135       34750      
right_shift_5             8978       32878      
right_shift_8             8688       30276      
right_shift_12            10591      35827      
MyTemplatePointerHash1    8721       30265      
BasileStarynkevitch       15524      38315      

--------------------------------
sizeof(T)       = 256
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 14169      36078      
reinterpret_cast          14096      36637      
djb2                      15373      37492      
djb2_mod                  15279      37438      
sdbm                      15531      38247      
yet_another_lc            15924      38779      
murmur2                   16524      39109      
murmur3                   16422      39280      
simple_xorshift           16119      38735      
double_xorshift           16136      38875      
right_shift_2             14319      36692      
right_shift_3             14311      36776      
right_shift_4             13932      35682      
right_shift_5             12736      34530      
right_shift_8             9221       30663      
right_shift_12            15506      98465      
MyTemplatePointerHash1    9268       30697      
BasileStarynkevitch       15952      38349      

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = sequential

dataset size    =    50000 elements
name                      insert     access    
std::hash                 421        7863       
reinterpret_cast          419        7953       
djb2                      457        8983       
djb2_mod                  455        8927       
sdbm                      445        8609       
yet_another_lc            446        8892       
murmur2                   492        9090       
murmur3                   507        9294       
simple_xorshift           467        8687       
double_xorshift           472        8872       
right_shift_2             432        8009       
right_shift_3             432        8014       
right_shift_4             435        7998       
right_shift_5             442        8099       
right_shift_8             432        7914       
right_shift_12            462        8911       
MyTemplatePointerHash1    426        7744       
BasileStarynkevitch       467        8417       

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = random

dataset size    =    50000 elements
name                      insert     access    
std::hash                 452        7948       
reinterpret_cast          456        8018       
djb2                      489        9037       
djb2_mod                  490        8992       
sdbm                      477        8795       
yet_another_lc            491        9179       
murmur2                   502        9078       
murmur3                   507        9273       
simple_xorshift           473        8671       
double_xorshift           480        8873       
right_shift_2             470        8105       
right_shift_3             470        8100       
right_shift_4             476        8333       
right_shift_5             468        8065       
right_shift_8             469        8094       
right_shift_12            524        10216      
MyTemplatePointerHash1    451        7826       
BasileStarynkevitch       472        8419       

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = sequential

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 10910      38432      
reinterpret_cast          10892      38994      
djb2                      10499      38985      
djb2_mod                  10507      38983      
sdbm                      11318      37450      
yet_another_lc            11740      38260      
murmur2                   16960      39544      
murmur3                   16816      39647      
simple_xorshift           16096      39021      
double_xorshift           16419      39183      
right_shift_2             10219      38909      
right_shift_3             10012      39036      
right_shift_4             10642      40284      
right_shift_5             10116      38678      
right_shift_8             9083       32914      
right_shift_12            9376       31586      
MyTemplatePointerHash1    8777       30129      
BasileStarynkevitch       16036      38913      

--------------------------------
sizeof(T)       = 1024
sizeof(T*)      = 4
insertion order = random

dataset size    =  1000000 elements
name                      insert     access    
std::hash                 16304      38695      
reinterpret_cast          16241      39641      
djb2                      16377      39533      
djb2_mod                  16428      39526      
sdbm                      15402      37811      
yet_another_lc            16180      38730      
murmur2                   16679      39355      
murmur3                   16792      39586      
simple_xorshift           16196      38965      
double_xorshift           16371      39127      
right_shift_2             16445      39263      
right_shift_3             16598      39421      
right_shift_4             16378      39839      
right_shift_5             15517      38442      
right_shift_8             11589      33547      
right_shift_12            11992      49041      
MyTemplatePointerHash1    9052       30222      
BasileStarynkevitch       16163      38829      

- Damon

---

SHA或MD5不是优秀的哈希函数，它们是加密哈希函数。虽然它们可以用于哈希表，但与非加密哈希函数相比，它们没有任何优势（甚至不能使哈希更不易受攻击），但速度慢了几个数量级。我现在记不起名字了，但有一个视频由Ruby实现者进行了非常广泛的讲座，特别提到了SHA。 - Damon

密码哈希函数具有出色的分布性和非常低的碰撞几率。它们非常缓慢。这是为了限制您的声明：“哈希表的性能首先取决于哈希函数的质量。” - egur

不过这并不是重点。当我说一个混合比较好的慢哈希函数比一个快速哈希函数有更好的净结果时，当然要带着一些保留态度。如果你从10MB的RAM区域中获得8字节对齐的指针，那么其中最多只有19位熵。花费一些额外的周期来很好地混合它们是有意义的，这样你就可以确保最终哈希表使用的16或17位实际上包含16-17位熵。但是将它们重新哈希数百万次是没有意义的。 - Damon

如果您想要节省几十个周期以加快散列速度，但混合的位数不够好，另一方面，散列表最终将使用的16位或更多位可能仅包含9-10位熵，因此会发生冲突。出于同样的原因，例如DJB建议您对从curve25519获得的结果进行哈希处理。实际上，这些是“随机”的位，因此您可以只使用低128位作为会话密钥，对吗？但是，在其中的比特总数中，熵的比特数较少，而且您不知道它们在哪里。因此，为了确保获取一些信息，您需要进行哈希处理。 - Damon

这就是为什么我对哈希函数进行基准测试的原因，以了解理论和实际如何结合 : )。我知道理论，但想要进行实证测试并找出哪个更好。哈希表性能在某些应用程序中是一个重大问题。 - egur

Answer 2

让这个问题搁置一段时间后，我将发布目前为止我认为最好的指针哈希函数：

template<typename Tval>
struct MyTemplatePointerHash1 {
    size_t operator()(const Tval* val) const {
        static const size_t shift = (size_t)log2(1 + sizeof(Tval));
        return (size_t)(val) >> shift;
    }
};

对于各种块大小，它的性能表现很高。
如果有更好的功能，我将更改接受的答案。

- egur

---

为什么在log2中要将sizeof加1？对于char类型来说，这看起来是错误的。另一个可能的改进是选择超对齐引用类型的sizeof和alignof之间的最大值，例如std::max(sizeof(T), alignof(T))。 - Tomilov Anatoliy

+1 是专门为 char 设计的，因为所有动态分配器（例如 malloc）都会分配一个可被 2（或更多）整除的地址。对于大多数（99%）使用 char 指针的其他情况也是如此（地址将相隔 >2 字节）。如果实际大小大于 sizeof()，结果仍然有效，因为它不会引入哈希冲突。 - egur

那么char * p = new char[2]; assert(MyTemplatePointerHash1< char >{}(p) != MyTemplatePointerHash1< char >{}(p + 1));呢？ - Tomilov Anatoliy

这只占到了1%的情况 :) 。但我认为你没有抓住重点，为什么会有人用指针哈希表呢？最坏的情况是你会失去一些性能。而其他选择也不是万能的解决方案。 - egur

无论如何，我们都应该寻求问题解决方案的规范形式。 - Tomilov Anatoliy

请原谅我的愚蠢，但使用void *作为参数类型是否足够？ - Chef Gladiator

Answer 3

哈希函数返回的结果类型为size_t，但由容器将其转换为“桶索引”，以确定正确的桶来查找对象。

我认为标准规定了这种转换，但我希望它通常是模数N运算，其中N是桶的数量 - 并且N通常是2的幂，因为增加桶计数是增加大小的好方法当有太多命中时。模数N运算意味着对于指针，朴素哈希函数仅使用桶的一部分。

真正的问题是用于容器的“好”哈希算法必须基于桶大小和要哈希的值的知识。例如，如果您在表中存储的对象大小都为1024字节，则每个指针的低位10位可能相同。

struct MyOneKStruct x[100];  //bottom 10 bits of &x[n] are always the same

因此，对于任何应用程序来说，“最佳”哈希可能需要大量的试验和测量，以及对你正在哈希的值的分布的了解。

然而，与其仅仅将指针向下移动N位，我会尝试将顶部“字”异或到底部。这很像@BasileStarynkevich的答案。

关于添加哈希表的提议非常有趣。我在下面的段落中强调：http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2003/n1456.html “不可能编写一个适用于所有类型的完全通用的哈希函数。（你不能仅仅将对象转换为原始内存并哈希字节；除其他原因外，该想法因填充而失败。）因此，也因为好的哈希函数只在特定使用模式的上下文中才是好的，允许用户提供自己的哈希函数是至关重要的。”

- Roddy

---

好的观点。虽然与我的应用程序无关，但仍值得探究。顺便说一下，一些哈希实现使用2的指数（好的实现），而其他一些使用质数。 - egur

重要答案！此外，对于使用2的指数的哈希实现，有些使用混合以确保它们仍然与天真的指针哈希很好地配合使用。其他人期望哈希函数已经完成了混合。如果您想尽可能快地工作，您需要知道自己正在处理什么。双重混合会浪费一些时间；完全没有混合可能会导致性能严重下降。 - Daniel

Answer 4

显然，答案取决于系统和处理器（特别是由于页面大小和字长）。我提议：

  struct MyVoidPointerHash {
      size_t operator()(const void* val) const {
         uintptr_t ad = (uintptr_t) val;
         return (size_t) ((13*ad) ^ (ad >> 15));
      }
  };

见解是，许多系统的页面大小通常为4K字节（即2¹²），因此右移位运算符>>15将把重要地址部分放在低位。 13*大多是为了有趣（但13是素数），并且更混杂一些位。异或^是将位混合起来，速度非常快。因此哈希的低位是指针的许多位（高位和低位）的混合物。 ^{我不主张在这种哈希函数中加入太多科学。 但它们经常表现得相当不错。 YMMV。 我猜您应该避免停用ASLR！}

- Basile Starynkevitch

---

有任何基准测试数据吗？此外，当所有对象恰好位于相同的32KiB区域（2 ** 15）中时，“（ad >> 15）”部分并不提供任何有用的信息。也许“13 * ad”就足够了。 - Maxim Egorushkin

Answer 5

虽然在性能方面（无论是对于char还是1024大小的struct）无法与您的解决方案相比，但在正确性方面有一些改进：

#include <iostream>
#include <new>
#include <algorithm>
#include <unordered_set>
#include <chrono>

#include <cstdlib>
#include <cstdint>
#include <cstddef>
#include <cmath>

namespace
{

template< std::size_t argument, std::size_t base = 2, bool = (argument < base) >
constexpr std::size_t log = 1 + log< argument / base, base >;

template< std::size_t argument, std::size_t base >
constexpr std::size_t log< argument, base, true > = 0;

}

struct pointer_hash
{

    template< typename type >
    constexpr
    std::size_t
    operator () (type * p) const noexcept
    {
        return static_cast< std::size_t >(reinterpret_cast< std::uintptr_t >(p) >> log< std::max(sizeof(type), alignof(type)) >);
    }

};

template< typename type = std::max_align_t, std::size_t i = 0 >
struct alignas(alignof(type) << i) S
{

};

int
main()
{
    constexpr std::size_t _16M = (1 << 24);
    S<> * p = new S<>[_16M]{};
    auto latch = std::chrono::high_resolution_clock::now();
    {
        std::unordered_set< S<> *, pointer_hash > s;
        for (auto * pp = p; pp < p + _16M; ++pp) {
            s.insert(pp);
        }
    }
    std::cout << std::chrono::duration_cast< std::chrono::milliseconds >(std::chrono::high_resolution_clock::now() - latch).count() << "ms" << std::endl;
    delete [] p;
    return EXIT_SUCCESS;
}

- Tomilov Anatoliy