指向泛型类型的指针

Question

在将给定的基于指针的有效哈希映射实现转换为通用哈希映射实现的过程中,我偶然发现了以下问题:

我有一个表示哈希节点的类(哈希映射实现使用二叉树)

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致敬:如果您读到这个:是的,这是基于您的哈希映射实现.你自己没有写过这样一个通用版本的实现,对吗？那会节省我一些时间:)

Answer 1

对不起,Smasher.不支持打开泛型类型的指针,因为不支持泛型指针类型,尽管在某些情况下可能(编译器错误)创建它们(特别是指向泛型类型中的嵌套类型的指针); 如果我们破坏某人的代码,则无法在更新中删除此"功能".通用指针类型的限制应该在将来被删除,但我不能做出承诺.

如果有问题的类型是JclStrHashMap我写的(或古代HashList单元),那么,重现它的最简单方法是将节点类型更改为类,并传递任何双指针,如同Pointer适当的转换.但是,如果我今天再次编写该单元,我就不会将桶实现为二叉树.我有机会在Generics.Collections单元中编写字典,尽管所有其他Delphi编译器的工作时间都太紧,然后才能获得可靠的QA,并且通用功能支持本身一直在变化,直到相当晚.

我更愿意将哈希映射存储桶实现为双散列,每桶动态数组或来自连续数组的单元的链接列表之一,无论哪种情况最好来自使用代表性数据的测试.逻辑是树/列表中跟随链接的高速缓存未命中成本应该主导树和具有良好散列函数的列表之间的桶搜索的任何差异.当前字典实现为直线性线性探测,主要是因为它相对容易实现并使用可用的原始泛型操作集.

也就是说,二叉树桶应该是对抗不良哈希函数的有效对冲; 如果它们是平衡的二叉树(=>甚至更多的修改成本),它们将是平均O(1)和O(log n)最差情况下的性能.