生成多對一映射的算法/散列函數

我正在尋找可用於生成整數流的批處理的散列函數。具體來說，我想要從一個集合或流（例如X）映射整數xi到另一組整數或字符串（如Y），使許多xi映射到一個yj。雖然這樣做，我想確保有最多nxi映射到單個yj。與哈希算法一樣，我需要能夠可靠地找到給定x的y。生成多對一映射的算法/散列函數

我想，以確保大部分yj有接近n一些xi映射到它們（避免非常稀疏映射從X到Y）。我能想到的

一個功能是商：

int BATCH_SIZE = 3; 
public int map(int x) { 
    return x/BATCH_SIZE; 
}

爲連續整數流，它可以工作得相當好。例如流1..9將映射到

1 -> 0 
2 -> 0 
3 -> 1 
4 -> 1 
5 -> 1 
6 -> 2 
7 -> 2 
8 -> 2 
9 -> 3

等等。但是，對於非順序大整數和小批量（我的用例），這可以生成超稀疏映射（每批大部分時間只有1個元素）。

是否有任何標準的方法來產生這樣的映射（配料）

來源

2017-07-19 aoak

如何使用'modulo'操作作爲散列函數？ – Josnidhin

modulo生成映射，該映射創建無限批處理大小，但有限數量的分區。我想要相反。有限的批量大小，對批次數量沒有限制 – aoak

對於流不能很好地工作，但是如果您將所有內容都讀入數組中，您可以對其進行排序並分批次製作n個索引。 – maraca

有沒有辦法讓它在這些假設下工作。

您需要知道流中有多少物品以及它們的分佈情況，或者您需要放鬆將物品映射到批量的能力。

比方說，您有流中的項目a和b。你打算把它們放在一起嗎？除非你知道你是否要獲得更多的物品來填補2個或更多的批次（如果你決定把它們放在不同的批次中），否則你不能回答這個問題。

如果您知道會有多少人（甚至大約），您可以根據他們的分佈和建立批次。假設你有字符串哈希（均勻分佈在32位以上）。如果您知道獲得了1M項目，並且想要批量爲100，則可以生成2^32 /（1.000.000/100）的間隔並將其用作批次標識（yj）。這並不能保證你批量批量batch_size，但他們應該近似batch_size。如果分配不統一，事情就比較困難，但仍然可以完成。

如果您放寬了將項目映射到批次的功能，那麼只需將它們分組到每個batch_size中，以便它們從流中出來。如果您有空間，您可以保留蒸汽物品的地圖。

來源

2017-07-21 09:37:12 Sorin

生成多對一映射的算法/散列函數

回答

相關問題