c++ - 散列中的单独链接

Question

我正在阅读有关 C++ 算法的 Robert Sedwick 一书中的哈希

We might be using a header node to streamline the code for insertion into an ordered list, but we might not want to use M header nodes for individual lists in separate chaining. Indeed, we could even eliminate the M links to the lists by having the first nodes in the lists comprise the table

.

class ST
{
    struct node
    {
        Item item;
        node* next;

        node(Item x, node* t)
            { item = x; next = t; }
     };

     typedef node *link;

  private:
     link* heads;
     int N, M;

     Item searchR(link t, Key v)
     {
          if (t == 0) return nullItem;
          if (t->item.key() == v) return t->item;
          return searchR(t->next, v);
     }

   public:
     ST(int maxN)
     {
          N = 0; M = maxN/5;
          heads = new link[M];
          for (int i = 0; i < M; i++) heads[i] = 0;
     }

     Item search(Key v)
         { return searchR(heads[hash(v, M)], v); }

     void insert(Item item)
         { int i = hash(item.key(), M);
           heads[i] = new node(item, heads[i]); N++; }
};

我对以上文字的两个问题作者的意思是什么

1. “我们甚至可以通过让列表中的第一个节点构成表格来消除指向列表的 M 个链接。”我们如何为此修改上面的代码？

2. “我们可能不想在单独的链中为单个列表使用 M 个头节点。”这句话是什么意思。

Answer 1

"We could even eliminate the M links to the lists by having the first nodes in the lists comprise the table."

考虑 Node* x[n] 与 Node x[n]:前者需要一个额外的指针和分配给头 Node 的插入内存 每个非空元素，以及每个哈希表操作的额外间接寻址，而后者消除了 n 指针，但要求任何未使用的元素都能够放在一些可识别的位置未使用状态(跟踪可能需要也可能不需要额外内存)，如果 sizeof(Node) 大小大于 sizeof(Node*)，它反正可能更浪费内存。内存使用的差异也会影响缓存使用的效率:如果表的元素与桶的比率很高，那么 Node[] 会将 Node 数据放入较少的连续内存页中，如果您迭代(以未排序的顺序)然后它的缓存效率非常高，而 Node*[] 将跳转到单独的内存分配，这些内存分配可能遍布整个地方(或者另一方面，实际上可能非常接近)在一些实际有用的情况下:例如，如果访问模式和动态内存分配地址都与对象创建的时间顺序相关。

How can we modify above code for this?

首先，您现有的代码有一个问题:heads[i] = new node(item, heads[i]); 在没有首先检查它是否为空的情况下覆盖哈希表中的条目。 . 如果那里有任何内容，那么您应该将其添加到列表中，而不是覆盖数组。

设计变更讨论需求:

link* heads;

...改为...

node* head;

你会像这样初始化它:

head = new node[M];

这需要一个额外的node构造函数(如果item有一个等效的默认构造函数，你可以在下面省略它的初始化)

node() : item(nullItem), next(nullptr) { }

然后对您的其余代码进行一些修改，这些修改很容易完成。基本上，您将摆脱一层指针。

"we might not want to use M header nodes for individual lists in separate chaining." What does this statement mean.

这不是我写的所以不能权威地说，但它似乎是说在设计列表代码时，可能已经决定即使在空列表中也有一个初始节点，因为这样可以简化代码用于几个列表操作。虽然额外的无数据节点在考虑列表的“常规”使用时似乎是一个合理的价格，但哈希表是不寻常的，因为您希望大多数链接到桶的列表具有 0 或 1 个元素，并且应该呈指数级减少越来越长。因此，这样的列表实现不太适合在哈希表中使用。