在将给定的高效的基于指针的哈希图实现转换为通用哈希图实现的过程中,我偶然发现了以下问题:
我有一个代表哈希节点的类(哈希映射实现使用二叉树)
THashNode <KEY_TYPE, VALUE_TYPE> = class
public
Key : KEY_TYPE;
Value : VALUE_TYPE;
Left : THashNode <KEY_TYPE, VALUE_TYPE>;
Right : THashNode <KEY_TYPE, VALUE_TYPE>;
end;
除此之外,还有一个函数应该返回指向哈希节点的指针。我想写
PHashNode = ^THashNode <KEY_TYPE, VALUE_TYPE>
但这不会编译(预期为“;”,但找到了“
如何获得指向泛型类型的指针?
致巴里·凯利(Barry Kelly):如果您读到此内容:是的,这是基于您的哈希映射实现的。您自己还没有编写过这样的通用版本的实现,是吗?这会节省我一些时间:)
对不起,粉碎者。不支持打开泛型类型的指针,因为不支持泛型指针类型,尽管在某些情况下可以(编译器错误)创建它们(特别是指向泛型类型内的嵌套类型的指针);如果我们破坏某人的代码,则无法在更新中删除此“功能”。对通用指针类型的限制将来应该被删除,但我不能保证何时删除。
如果有问题的类型是JclStrHashMap
我写的(或者古代的HashList
单位),好吧,重现它的最简单方法是将节点类型更改为类并传递任何双指针Pointer
通过适当的铸造。但是,如果我今天再次编写该单元,我不会将存储桶实现为二叉树。我有机会在 Generics.Collections 单元中编写字典,尽管在交付可靠的 QA 之前,所有其他 Delphi 编译器的工作时间都太紧张,并且通用功能支持本身一直在变化,直到相当晚。
我更愿意将哈希映射存储桶实现为双哈希、每存储桶动态数组或来自连续数组的单元格链接列表之一,以使用代表性数据进行测试时的最佳结果为准。其逻辑是,在树/列表中跟踪链接的缓存未命中成本应该在具有良好哈希函数的树和列表之间的存储桶搜索中占主导地位。当前的字典被实现为直线探测,主要是因为它相对容易实现并且可以与可用的原始通用操作集一起使用。
也就是说,二叉树桶应该是针对糟糕的哈希函数的有效对冲;如果它们是平衡二叉树(=>
甚至更多的修改成本),平均为 O(1),最坏情况下的性能为 O(log n)。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)