算法：實現基於自定義散列表的字典

我正在學習編程抽象數據類型。試圖構建基於自定義哈希表的字典。算法：實現基於自定義散列表的字典

到目前爲止，我創建了一個班級佔位符。

public class HashMapDict implements IDict 
{ 
    private var _map:Array; 
    public function HashMapDict() 
    { 
     _map = new Array(); 

     //TODO: implement function 
    } 

    public function set(keys:Array):Boolean 
    { 
     // 1. For each key in array of keys 
     // 2. Pass Key.key to hash function 
     // 3. Write Key to _map[hash(Key.key)] 
     return true; 
    } 


}

我看到主要的方法集執行以下操作

// 1. For each key in array of keys 
// 2. Pass Key.key to hash function 
// 3. Write Key to _map[hash(Key.key)]

我所想的是使用加密庫進行哈希生成。但我對它應該如何工作有點困惑。例如試圖看看像as3crypto（http://crypto.hurlant.com/demo/）這樣的幾個庫，它似乎產生散列的方式，我真的不認爲可以用於數組中的索引。

E.g.

http://screencast.com/t/bE1lYQEqp4D

你可以建議我可以用它的lib來產生可用哈希？他們應該如何看起來像

來源

2011-08-19 Oleg Tarasenko

對於散列表的實現，加密散列函數是矯枉過正的。

僅當您關心試圖爲您提供不良數據的人的攻擊時（例如，有大量散列衝突的密鑰）使散列表變慢。

對於一個哈希表的使用，像下面的一個散列函數足夠（僞代碼，因爲我不知道正確的語法）：

hash = 0 
for c in string: 
    hash = hash * 13 + c; 
return hash

但正如其他的答案說，已經有一個哈希表內置，你並不需要重新實現它。

來源

2011-08-19 21:38:53

我只是爲了教育目的而做的。在實際應用中，我將使用已經實現的字典。你的代碼的想法是什麼？ –

我的哈希碼（這是一個非常標準的哈希碼，我認爲除了可能的選擇13）是一個多項式，字符代碼爲係數，評估爲13.（使用任何其他數字 - 但質數最好。）[Java的String.hashCode（）做了類似的事情，使用31而不是13。]（http://download.oracle.com/javase/6/docs/api/java/lang/String.html#hashCode（）） –

試過這種方法。一般來說，對於key =「bob」，它生成一個哈希碼= 337.所以，通過在數組中插入一個帶有這樣的鍵的項目，例如_map [337] = MYKEY我將得到一個由337個空元素組成的數組（其中一個不爲空）。你認爲沒關係嗎？我只是有點擔心，如果在內存中創建如此大的陣列可以。 –

我可能會錯過一些東西，但我認爲你應該看看flash.utils::Dictionary。
它使哈希過時。如果您必須有某種原始的關鍵，我建議使用下列內容：

class UIDUtil { 
    static private var map:Dictionary = new Dictionary(true); 
    static private var counter:int = 0; 
    static public function getUID(value:*):int { 
     return map[value] ||= counter++; 
    } 
}

但你的類我會爲實現：

public class HashMapDict implements IDict { 
    private var _map:Dictionary = new Dictionary(); 
    public function set(keys:Array):Boolean { 
     for each (var key:* in keys) _map[key] = key; 
     return true; 
    } 
}

我不知道它的目的雖然;）

來源

2011-08-19 21:28:39 back2dos

什麼是返回圖[value] || = counter ++; –

這是一個懶惰實例化的花哨語法。它的作用是：如果map [value] == null，那麼它被填充counter（每次增加） –

就像一個人擡頭 - 我幾乎可以保證你將無法做出比Dictionary甚至Object更好的東西。你提出的計劃可能會奏效，但它對這些計劃沒有任何好處。我也覺得不得不建議使用矢量數組，因爲矢量更快更強大。

哈希庫的問題是它們通常會導致非常非常大的數字。例如，MD5將生成一個十六進制字符串，它表示的內容遠遠超過甚至可以適用於uint（適用於2^32，MD5爲2^128）的內容。這也恰好是maximum size of an Array/Vector in AS.

這並不是說他們不能融入Number（可容納約1.79 * 10^308），但它確實意味着你將失去的數字受益索引，並且在這一點上你肯定不會從Vector中獲得太多好處。你基本上會回落到Object。

說實話，它確實看起來像你有兩種選擇之一。您可以使用第二個Array/Vector實現直接查找。這具有O（n）查找時間的問題，而哈希表的查找時間將爲O（1）。

看來，至少對我而言，無論做什麼，你都需要使用Dictionary或Object。

來源

2011-08-19 21:32:04 cwallenpoole

算法：實現基於自定義散列表的字典

回答

相關問題