類/對象生成唯一的ID

Question

我使用C＃，但即使您不知道它，它應該很容易跟隨這個問題。

這是我的問題：我有一些對象，我想保留在一個哈希集數據結構，以便我可以查找他們基於int ID。這些對象具有可變屬性，所以對它們進行散列不是一種選擇（我需要一些關於它們的常量來散列，是的？）。

我所做的是制定如下界面：

public interface IUniqueIDCollection 
{ 
    // Can return any int that hasn't been requested yet. 
    public int RequestUniqueID(); 

    // Undos the requesting of an int 
    public int ReleaseUniqueID(int uniqueID); 
} 

我最初的想法是隻儲存在一個遞增的ID的請求的IUniqueIDCollection內部計數器。但是，一旦ID被髮布，我將不得不跟蹤已被刪除的範圍或個人ID。我認爲後者會更好。但是，如果我使用計數器（或任何循環函數）來生成ID，那麼我會遇到必須通過檢查已經連續請求的ID的序列的問題，因爲一旦計數器迴繞，就不會被釋放。

啓發式是這樣的：假設一次最多需要5000個ID。但是，ID經常會要求併發布。釋放將傾向於發生在範圍內 - 即可能一次請求100個，然後全部100個將在短時間間隔內釋放。

我知道我可以使用一個GUID或東西，而不是一個int，但我想節省ID的空間/帶寬/處理時間。

所以我的問題是：在給出啓發式的情況下，在上面給出的接口中，請求和釋放方法應該按照僞代碼的方式表示？

Answer 1

如果您確定發佈的ID是安全的，可以立即重用（例如，如果新對象分配了最近發佈的ID，那麼舊ID的掛起不會過時引用會被混淆），您可以先使用發佈的ID。所以當一個ID被釋放時，你把它放在一個隊列的末尾。當請求新的ID時，您使用隊列中的第一個ID。如果隊列爲空，則增加內部計數器併發出新的號碼。

利用此實現：

• 所有的操作都是O（1）。你永遠不會迭代一個集合或範圍。您只能在隊列的末尾插入，從隊列的前面移除或增加計數器。
• 由於您嘗試儘快使用隊列，內存佔用量應該相當低。
• 實現很簡單。

缺點：

• 你會被重用ID的很快，所以你不會使用你的整個索引範圍，以保持新對象使用相同ID最近發佈的對象。
• 通過查看對象的ID，您甚至無法猜測對象的年齡。

Answer 2

可能比Tom Panning's一個糟糕的想法上面幾乎在所有情況下，但你可以使用一個BitArray跟蹤正在使用的ID。內存使用量與您總共擁有活動ID的位數相同;最壞的情況將是512MB，用於映射所有32位整數。發佈很簡單：只需將相應位設置爲0.獲取（或請求）ID需要搜索0位，如果找不到，則擴展BitArray。

如果您仍然可以選擇擴展您的BitArray（即您尚未達到512MB），那麼您在決定擴展之前可能不想搜索所有BitArray - 這樣做總是會很慢。您當然不會始終想從同一個索引開始：跟蹤您找到的最後一個0並從此處開始搜索可能是個好主意。

我可以看到的一個優點是，一旦所有或幾乎所有的對象都被釋放，內存使用就會消失。那麼Tom Panning的解決方案至少需要32倍的內存。但是，我期望在解決方案使用較少的典型用法中。