异或链表

本文关键字：链表 | 更新日期: 2023-09-27 17:56:22

我最近看到了下面的链接，我觉得很有趣。

http://en.wikipedia.org/wiki/XOR_linked_list

  • 通用调试工具无法遵循异或链，使调试更困难;[1]
  • 内存减少的代价使用量是代码的增加复杂性，使维护更加复杂贵;
  • 大多数垃圾回收方案都可以不适用于以下数据结构不包含文字指针;
  • 指针的异或未在 中定义一些上下文（例如，C语言），虽然许多语言提供了一些类型转换的种类指针和整数;
  • 指针将不可读，如果一个不是遍历列表 — 对于例如，如果指向列表的指针项目包含在另一个数据中结构;
  • 遍历列表时，您需要记住地址以前访问的节点，以便计算下一个节点的地址。

现在我想知道这是否是低级语言独有的，或者这在 C# 中是否也可能？

是否有任何类似的选项可以使用 C# 生成相同的结果？

异或链表

TL;DR 我用 C# 快速编写了一个概念验证的 XorLinkedList 实现。

在 C# 中使用不安全的代码绝对可以做到这一点。不过，有一些限制：

  1. XorLinkedList 必须是"非托管结构"，即它们不能包含托管引用
  2. 由于 C# 泛型的限制，链表不能是泛型的（即使带有 where T : struct 也不行）

后者似乎是因为您不能将泛型参数限制为非托管结构。只需where T : struct，您还可以允许包含托管引用的结构。

这意味着您的 XorLinkedList 只能保存基元值，如整数、指针或其他非托管结构。

C# 中的低级编程

private static Node* _ptrXor(Node* a, Node* b)
{
    return (Node*)((ulong)a ^ (ulong)b);//very fragile
}

非常脆弱，我知道。C# 指针和 IntPtr 不支持 XOR 运算符（可能是个好主意）。

private static Node* _allocate(Node* link, int value = 0)
{
    var node = (Node*) Marshal.AllocHGlobal(sizeof (Node));
    node->xorLink = link;
    node->value = value;
    return node;
}

之后不要忘记Marshal.FreeHGlobal这些节点（实现完整的 IDisposable 模式，并确保将免费调用置于if(disposing)块之外。

private static Node* _insertMiddle(Node* first, Node* second, int value)
{
    var node = _allocate(_ptrXor(first, second), value);
    var prev = _prev(first, second);
    first->xorLink = _ptrXor(prev, node);
    var next = _next(first, second);
    second->xorLink = _ptrXor(node, next);
    return node;
}

结论

就个人而言，我永远不会在 C# 中使用 XorLinkedList（当我编写非常低级的系统内容（如内存分配器或内核数据结构）时，可能会在 C 中使用。在任何其他设置中，存储效率的小幅提高真的不值得痛苦。事实上，你不能在 C# 中将其与托管对象一起使用，这使得它对于日常编程几乎毫无用处。

此外，存储今天几乎是免费的，甚至是主内存，如果您使用的是 C#，您可能不太关心存储。我在某处读到CLR对象标头约为~40字节，因此这一个指针将是您最不关心的问题;)

C# 通常不允许您在该级别操作引用，所以很遗憾。

作为已提出的不安全解决方案的替代方案。

如果您使用数组或列表集合支持链表，其中"next"和"previous"指示数组中的索引，而不是内存指针，则可以在不诉诸不安全功能的情况下实现此异或。

在 C# 中有一些方法可以使用指针，但只能暂时使用指向对象的指针，因此在此方案中不能使用它们。造成这种情况的主要原因是垃圾回收——只要你可以做一些事情，比如 XOR 指针并在以后取消 XOR 它们，GC 就无法知道收集某些对象是否安全。

您可以通过在一个大数组中使用索引模拟指针来制作非常相似的东西，但您必须自己实现一种简单的内存管理形式（即在创建新节点时，我应该将其放在数组中的什么位置？

另一种选择是使用 C++/CLI，它一方面允许您完全灵活地使用指针，另一方面允许您在需要时访问 GC 并访问框架。

当然。你只需要对类进行编码。 C# 中的 XOR 运算符是 ^这应该是您开始编码所需的全部内容。请注意，这将要求将代码声明为"不安全"。请参阅此处：了解如何在 C# 中使用指针。

在这里做一个广泛的概括：C#似乎已经走了可读性和干净的接口的道路，而不是位摆弄和尽可能密集地打包所有信息的道路。

因此，除非您在这里有特殊需求，否则您应该使用您提供的列表。未来的维护程序员会为此感谢你。

但是，

您必须了解 C# 如何看待对象。 实例变量实际上不包含对象，而是指向内存中对象的指针。

DateTime dt = DateTime.Now;

dt 是指向内存中包含日期时间方案的结构的指针。

所以你可以做这种类型的链表，尽管我不确定你为什么这样做，因为框架通常已经实现了最有效的集合。 作为思想过期是可能的。

相关文章：