2012-03-21 259 views
1

你們中的任何人都可以告訴我字典結構 的查找方法的幕後操作是什麼。我的意思是它是如何實現的?給定一個關鍵字,我們可以在字典中找到這個值。字典查找與數組查找;數組重定位與字典分配

1)我們知道,數組查找是O(1)操作。那麼字典呢?

2)如果我存儲的鍵值對中的兩個都是整數,如果有大量的這樣的數據和空間是我最擔心的問題?一個數組或字典? 例如,我可以分配一個固定大小的數組。但是關鍵值對可能不會佔據整個陣列。它的大小可能是陣列的一半。但是數組的分配應該是最大的,因爲我不知道某個鍵是否會出現。讓我澄清,讓我們有關鍵的價值對(10,1),(20,2),(30,3)。所以如果我使用數組,那麼我必須聲明其大小爲[30] [2],儘管它只佔用3個條目。所以,在這種情況下字典會更好。不是30可以是百萬。所以其他條目將佔用陣列中的內存嗎?

+0

絕對使用字典(或列表)。 – jahroy 2012-03-21 05:08:31

+0

是的,我決定使用字典。 – 2012-03-21 06:17:15

回答

2

字典通常以兩種方式實現,即哈希映射或二叉樹。

1:如果字典是二叉樹,那麼搜索時間是二分搜索,因此O(log n)。

如果字典是哈希映射,則搜索時間爲O(1)。 (對於具有相同散列的密鑰可能增加到O(m))

2:你說得對,在這種情況下,一個字典將更好地用於稀疏數據集。字典搜索的額外時間成本將會相對較低。

使用字典進行搜索可以通過類似bloom過濾器(如果平均情況是哈希映射中不存在的對象)進一步改進。

+0

請注意.Net Dictionary是作爲散列映射實現的 - 所以O(1)查找。 – 2012-03-21 05:24:39

+0

哦,那太好了。我在C#中使用它。 – 2012-03-21 06:16:04

2

術語dictionary是非常通用的,可以指任何類型的數據結構。你也沒有說它是一個有序的字典還是無序的。有各種各樣的二叉搜索樹,以各種方式平衡,n-ary樹,散列表,跳過列表等。

就陣列而言,直的扁平陣列在稀疏填充時會浪費空間。但是,您可以實現多級數組。前幾個級別是目錄,只有葉級有小陣列。

虛擬內存頁表通常以這種方式實現。

所以會發生的是,像(十六進制)[0x123456]這樣的數組索引可能會通過位掩碼操作分解爲[0x12] [0x34] [0x56]。選擇頂層目錄,該目錄是指向中間目錄的指針數組,其中有指向小表的指針數組。 (當然,實際上,代碼必須走水平,注意丟失的目錄和表格,而不是直接編制索引!這就是整個問題:不要將整棵樹實例化。)

不久前我實現了Unicode字符集以這種方式在正則表達式引擎中設置,對於不同的情況使用這些種類不同的深度結構。

當然,這與您的常規new int[foo] C++數組無關!但是當然可以隱藏在看起來像數組的類後面。

+0

我的字典沒有訂購。 – 2012-03-21 06:18:58

+0

「你的」字典?它是什麼?如果這是你的字典,你爲什麼不知道它是如何工作的? *困惑* – Kaz 2012-03-21 06:21:19