算法：实现基于自定义散列表的字典

我正在学习编程抽象数据类型。试图构建基于自定义哈希表的字典。算法：实现基于自定义散列表的字典

到目前为止，我创建了一个班级占位符。

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

算法：实现基于自定义散列表的字典

回答

相关问题