2012-04-24 30 views
1

在線性探測中,有一個特殊值叫做AVAILABLE,當物品被移除時,它被替換。散列表和探測 - AVAILABLE和null?

而當你插入你找一個空單元格鍵(這只是意味着細胞是null?)或一個包含AVAILABLE,我不明白的是,如果空單元格指null,而不是具有的特殊值AVAILABLE爲什麼不只是使單元格null

與使用AVAILABLE相比有什麼優勢?

+0

您可以參考您獲得「AVAILABLE」術語的位置嗎?也許這是學術界的一個怪癖。 – usr 2012-04-24 20:41:18

+0

@usr是的,[這裏](http://www.cs.sfu.ca/CC/225/jmanuch/lec/12-3.ppt)它在幻燈片10上,關於代碼 – orange 2012-04-24 21:10:43

+0

的評論我有不知道。至少根據顯示的代碼null和AVAILABLE是等同的。 – usr 2012-04-24 21:34:47

回答

2

在封閉的散列(打開尋址)的值被查找爲:

  1. 計算密鑰哈希和由它確定了「完美」的桶;
  2. 如果存儲桶已被佔用並且其鍵值等於查找的鍵值,則返回值;
  3. 如果存儲桶未被佔用,請中止查找失敗;
  4. 轉到下一個桶(線性探測只是增量鬥指數)和步驟2

現在,假設你開始在鬥5查找,只在桶8.找到你的密鑰如果現在刪除程序標記的桶6沒有被佔用,因爲步驟3,你永遠不會進入桶8.因此,我們需要一個特殊的值來標記桶被「佔用」,但仍然可以插入。這可能是您的來源條款AVAILABLEnull根本沒有佔用。

編輯:順便說一句,利用線性探測,可以(非常)有效地離開而沒有這個特殊的值,但是這使得擦除變得相當複雜。