是否有更好的实现来保持唯一整数对的计数？

Question

这是用C++编写的。我需要为每一对数字保留一个计数。这两个数字的类型是“int”。我排序这两个数字，所以（n1 n2）对与（n2 n1）对相同。我使用std :: unordered_map作为容器。我一直在用pairing function by Matthew Szudzik, Wolfram Research, Inc.。在我的实现中，函数给了我一个类型为“long”的唯一数字（在我的机器上是64位），用于每对“int”类型的两个数字。我用这个long作为unordered_map（std :: unordered_map）的关键字。有没有更好的方法来保持这些对的计数？我的意思是，更快，如果可能的话使用更少的内存。

此外，我不需要所有的长。即使您可以假设这两个数字的范围可以达到32位的最大值，但我预计配对函数的最大可能值最多需要36位。如果没有别的，至少有没有办法将36位作为unordered_map的关键字？ （某些其他数据类型）

我想过使用bitset，但我不确定std :: hash是否会为任何给定的36位位集生成一个唯一的键，这可以用作unordered_map的键。

我将不胜感激任何想法，建议等

Answer 1

首先我觉得你带着错误的假设。对于std::unordered_map和std::unordered_set，散列不必是唯一的（对于例如std::string等数据类型，原则上不可能是这样），那么2个不同的键将生成相同散列值的概率很低。但是如果发生碰撞，它不会是世界末日，只是访问速度会变慢。我会从2个数字生成32位散列，如果你有一个典型值的想法，只是测试散列冲突的概率，并相应地选择散列函数。

对于这个工作，你应该使用一对32位数字作为std::unordered_map中的一个键并提供一个合适的散列函数。计算唯一的64位密钥并将其与哈希映射一起使用是有争议的，因为hash_map会计算该密钥的另一个哈希值，所以有可能让它变慢。

大约36位密钥，这不是一个好主意，除非你有一个特殊的CPU来处理36位数据。您的数据将在64位边界上对齐，并且您不会有任何保存内存的好处，否则您将受到未对齐数据访问的惩罚。在第一种情况下，您只需要额外的代码就可以从64位数据中获得36位（如果处理器支持它的话）。在第二种情况下，即使存在一些冲突，代码也会比32位散列更慢。

如果是的hash_map的瓶颈，你可以考虑不同的实现哈希表像goog-sparsehash.sourceforge.net

Answer 2

只是我的两分钱，你已经在文章中得到了配对功能WAY更复杂比你实际需要的。将2个32位UNISIGNED值唯一地映射到64是很容易的。下面是这样做的，甚至可以处理非对数状态，而不会严重影响数学外设（如果有的话）。

uint64_t map(uint32_t a, uint32_t b) 
{ 
    uint64_t x = a+b; 
    uint64_t y = abs((int32_t)(a-b)); 

    uint64_t ans = (x<<32)|(y); 
    return ans; 
} 

void unwind(uint64_t map, uint32_t* a, uint32_t* b) 
{ 
    uint64_t x = map>>32; 
    uint64_t y = map&0xFFFFFFFFL; 

    *a = (x+y)>>1; 
    *b = (x-*a); 
} 

另一种选择：

uint64_t map(uint32_t a, uint32_t b) 
{ 
    bool bb = a>b; 
    uint64_t x = ((uint64_t)a)<<(32*(bb)); 
    uint64_t y = ((uint64_t)b)<<(32*!(bb)); 

    uint64_t ans = x|y; 
    return ans; 
} 

void unwind(uint64_t map, uint32_t* a, uint32_t* b) 
{ 

    *a = map>>32; 
    *b = map&0xFFFFFFFF; 
} 

，它作为一个独特的密钥。你可以很容易地将其修改为无序映射的散列函数提供者，不管它是否会比std :: map更快取决于你得到的值的数量。

注意：如果值a + b> 32位，则将失败。