是否有更好的實現來保持唯一整數對的計數？

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位，則將失敗。