代码之家 › 专栏 › 技术社区 › Swiss Frank

用于64位操作系统/编译的哈希函数,用于实际只有4字节int的对象

hashcode c++11

Swiss Frank · 技术社区 · 4 年前

我有一个名为Foo的类,私下里只不过是4字节的int。如果我以8字节大小返回它的值,我会搞砸吗 unordered_map<> 或者别的什么?我可以用类似 return foo + foo << 32; return ~foo + foo << 32; 哪一个会使用所有的64位,也没有一个共同的因素?

namespace std {
  template<> struct hash<MyNamespace::Foo> {
    typedef size_t result_type;
    typedef MyNamespace::Foo argument_tupe;
    size_t operator() (const MyNamespace::Foo& f ) const { return (size_t) f.u32InternalValue; }
  };
}

0 回复 | 直到 4 年前

Adrian Maire 4 年前

增量 uint32_t 密钥转换为 uint64_t 效果很好

unordered_map

密钥的较低有效位用于确定铲斗位置,在4个条目/铲斗的示例中,使用较低有效位2。

// 4 Buckets example

******** ******** ******** ******** ******** ******** ******** ******XX

bucket 00 would contains keys like {0, 256, 200000 ...}
bucket 01 would contains keys like {1, 513, 4008001 ...}
bucket 10 would contains keys like {2, 130, 10002 ...}
bucket 11 would contains keys like {3, 259, 1027, 20003, ...}

如果您试图在一个bucket中保存一个额外的值,并且它的负载系数超过了限制,那么该表的大小将被调整(例如,您试图在负载系数为1.0的4 bucket表中保存第5个元素)。

因此:

有一个 第32页 或者 uint64\ 在达到2^32个元素的哈希表之前,键的影响很小。

这是更好,还是更糟,因为所有散列现在都是0x100000000001的倍数?

在达到32位溢出(2^32)哈希表之前,这不会有任何影响。

key64 = static_cast<uint64>(key32);

增量uint32\t和uint64\t之间的密钥转换错误:

key64 = static_cast<uint64>(key32)<<32;

最好的办法是尽可能保持密钥的均匀性,避免一次又一次使用相同的因子进行哈希运算。E、 g.在下面的代码中,所有因子为7的键在调整到16个桶之前都会发生冲突。

https://onlinegdb.com/r1N7TNySv

#include <iostream>
#include <unordered_map>

using namespace std;

// Print to std output the internal structure of an unordered_map.
template <typename K, typename T>
void printMapStruct(unordered_map<K, T>& map)
{
    cout << "The map has " << map.bucket_count()<< 
        " buckets and max load factor: " << map.max_load_factor() << endl;
    
    for (size_t i=0; i< map.bucket_count(); ++i)
    {
        cout << "    Bucket " << i << ": ";
        for (auto it=map.begin(i); it!=map.end(i); ++it)
        {
            cout << it->first << " ";
        }
        cout << endl;
    }
    cout << endl;
}

// Print the list of bucket sizes by this implementation
void printMapResizes()
{
    cout << "Map bucket counts:"<< endl;
    unordered_map<size_t, size_t> map;
    
    size_t lastBucketSize=0;
    for (size_t i=0; i<1024*1024; ++i)
    {
        if (lastBucketSize!=map.bucket_count())
        {
            cout << map.bucket_count() << " ";
            lastBucketSize = map.bucket_count();
        }
        map.emplace(i,i);
    }
    cout << endl;
}

int main()
{
    unordered_map<size_t,size_t> map;
    
    printMapStruct(map);
    
    map.emplace(0,0);
    map.emplace(1,1);
    printMapStruct(map);
    
    map.emplace(72,72);
    map.emplace(17,17);
    printMapStruct(map);
    
    map.emplace(7,7);
    map.emplace(14,14);
    printMapStruct(map);
    
    printMapResizes();

    return 0;
}

注意桶计数:

1 3 7 17 37 79 167 337 709 1493 3209 6427 12983 26267 53201 107897 218971 444487 902483 1832561

std::unordered_map<> bucket_count() after default rehash