您能否快速生成一個 ID 號，沒有衝突，並且沒有 ID 洩露資訊？
是否有一種標準方法可以一個接一個地生成 ID 號，這樣：
- 您可以保證或幾乎保證避免碰撞。（通過“幾乎保證”，我的意思是，例如，如果您生成完全隨機的 24 位數字，而您“僅”生成了 100 萬個，那麼即使存在生日悖論，發生碰撞的機率也會很小。）
- 您希望 ID 號較短，而不是笨拙 - 具體而言，您不想依賴 ID 號的長度（並選擇隨機值）來避免衝突，如前一個要點中所述。你必須以其他方式做到這一點。
- 您不想在每次生成新值時通過查看所有預先存在的值以查看它是否已被使用來避免衝突。這只會是每次在排序列表上的 log(n) 查找，但假設我無論如何都想避免這種情況。
- 您不希望 ID 號顯示有關它何時生成的任何資訊，或者在 ID 號 X 和 ID 號 Y 之間生成了多少個 ID 號。沒有這個條件，問題就變得微不足道；您可以只使用時鐘時間（加上一些足夠大的隨機值以避免在同一時鐘時間值中生成的數字之間發生衝突），或者您可以只使用順序整數（除非現在攻擊者知道如果有人在3 月 1 日和 4 月 1 日的 ID 值 6000，在此期間生成了 1000 個其他值）。
我試圖找到一個微不足道的答案，但我嘗試過的答案似乎都不起作用。你可以只取數字 1、2、3 等的 SHA-256 雜湊（加上一些密鑰），但這與從可用空間中選擇隨機數有同樣的問題——如果你依賴散列的長度（例如 SHA-256）以避免衝突，由此產生的 ID 號又長又笨重，如果使散列更短，則會增加衝突的機會。
或者，您可以通過每次增加 1 和 n 之間的隨機值來生成新的 ID，而不是總是增加 1。問題在於，根據攻擊者可以做什麼，他們可以弄清楚 n 是什麼——如果他們有能夠按順序生成兩個 ID，並重複執行，他們可以計算出 n，或者如果他們有能力檢查哪些 ID 是有效的，他們可以檢查某個小範圍內的每個數字，看看有效的包裝有多密集ID 是，並從中找出 n。
我能找到的唯一解決方案如下：首先，提前做一些準備工作。無論您希望生成多少個 ID 值（例如 100 萬），取從 1 到 100 萬的所有整數，然後按順序開始計算每個整數的雜湊值加上一個密鑰。將散列截斷為您認為足夠短的任何值。但是，如果截斷時間足夠短，您可能會看到碰撞。因此，每次為給定整數生成一個新的截斷散列時，請對照先前生成的值檢查它，如果存在衝突，則將該整數添加到整數列表 L 中，其中該整數的散列與較小整數的散列發生衝突。（所以事實上，如果你的計劃是生成 100 萬個 ID，那麼在他的準備工作中，你將不得不去最後 100 萬個整數，以彌補你跳過的那些。）
然後，在執行時生成 ID 時，您只需從整數計數器開始。每次生成新 ID 時，遞增整數並檢查它是否在列表 L 中，如果是，則跳過並轉到下一個整數。（這確實涉及“log n 查找”，顯然違反了我聲明的規則之一，但我真正想做的是避免將每個新 ID 值與迄今為止生成的每個值進行檢查；檢查 L 應該快得多。）並且您可以對其進行微調以進行權衡（截斷散列的時間越長，L 越短，因此每次生成新 ID 時檢查的時間就越短；但可能不希望使用更長的 ID 值）。
但這感覺就像一個黑客。有標準方法嗎？如果沒有，你能想出更好的方法嗎？
最有效的方法是使用格式保留加密算法；這是一種算法，它是對任意大小的集合（例如，10 個十進制數字的序列）的排列。
使用它很簡單：你會選擇一個隨機密鑰並儲存它；您還將保留一個序列號（與輸出格式相同，例如，您可能以 0000000000 開頭）。然後，當需要生成下一個 ID 時，您將增加序列號，並通過 FPE 算法發送；那是你的下一個身份證
$$ 1 $$. 因為 FPE 算法是一個排列，所以在序列號換行之前，您永遠不會兩次生成相同的 ID；因此，沒有碰撞。您可以根據需要使 ID 盡可能短（目前的 FPE 算法存在空間非常小的問題；如果您將 ID 保持為至少 6 位數字，那麼您將是安全的）。而且，由於 FPE 算法是安全的，任何 ID 都不會提供任何其他 ID 的任何資訊（包括相對生成順序）。
缺點：沒有（據我所知）通用的 FPE 庫可用。對於使用，我建議從本文件中選擇 FF1；從頭開始實施將需要一些工作（但會滿足您的需求）。
一種效率較低但更易於實施的方法是對您的建議進行更改：保留您尚未分配的 ID 列表。
在這裡，在設置期間，您將按順序初始化所有可能 ID 的列表，例如 000000 到 999999。此外，您將值 N 設置為最高的未分配 ID（在此範例中，N = 999999）。
然後，當需要發布一個新 ID 時，您會選擇一個介於 0 和 N（含）之間的隨機數 x。然後，您將交換索引 N 和 x 處的 ID（如果 x=N，則此交換操作不執行任何操作）；然後，您將輸出不在索引 N 中的值（然後遞減 N）。
而已; 這實際上是Fisher-Yates shuffle，您可以按需執行此操作（正如我所寫的那樣），或者您可以在設置時進行所有洗牌（並在生成 ID 時從列表中讀取內容）。
這比 FPE 的想法效率低 - 既是因為設置涉及更多，而且您需要保留一個較大的 ID 列表。另一方面，它比嘗試從頭開始實現FF1要容易得多……
$$ 1 $$：格式保留加密算法也需要“調整”；您希望將其保持為固定值（例如，空字元串）；調整提供了您的特定用途不需要的服務。