是否总是需要使用动态内存分配实现散列 table？

Question

我已经在网上搜索过这个问题并问过我的助教，但我没有得到非常可靠的答案。我正在测试不同数据结构的插入和搜索性能。我正在测试的数据结构之一是散列 table.

我知道如果您不知道数组的最终大小并且出于各种原因想要实现双精度数组，动态分配内存是有益的。但是假设我们知道数据量。在本例中为 40,000 个整数值。我是否需要在堆上动态分配一个数组，或者我能否通过使用堆栈静态实例化来获得相同的功能和使用？我会做同样的事情，创建我的头文件、我的实现文件和 main() 但不动态分配内存。

Answer 1

如果您知道您的散列 table 的最大（或固定）大小，您可以非常静态地分配它。

动态分配的主要原因是在运行时改变大小并能够在函数之间传递结构的所有权。例如（这与哈希 tables 完全无关，所以我只使用通用结构）：

Item *GetItem() {
    return new Item();
}

动态分配项目并将其传递回调用者（连同所有权（管理其生命周期的责任））。避免动态分配的一种天真的方法是：

Item *GetItem() {
    Item item;
    return &item;
}

不幸的是，该地址在 return 上不可用，因为此时 item 已超出范围，因此您可以通过以下方式阻止这种情况发生：

Item *GetItem() {
    static Item item;
    return &item;
}

即使在 return 从函数中保留对象，但有一个限制，即它只存在一个副本。如果您尝试从该函数中获取两项，它们将是同一项，除非您意识到这一点，否则您可能会遇到错误。

所以，我想说的是，只要您只需要一个散列 table，您就可以通过拥有它的静态副本来避免动态内存分配。

当然，除了单副本限制外，这也有一个缺点，那就是需要你分配最大space。这不一定是个坏主意（尤其是如果它的大小固定），但它可能导致效率低下。

无论如何，您可能会不必要地担心性能。您可以轻松地预先动态分配其 maximum/fixed 大小的结构（而不是进行大量小分配和取消分配）。由于每个散列 table 实际上只发生一次（希望在释放之前对散列 table 进行大量使用），成本将相对较小。

它使您能够在程序中拥有多个哈希 table。

Answer 2

好问题。你可以在没有动态内存分配的系统上实现 malloc，只需在 malloc.c 中放置一个大的空 table，然后处理它的一部分，直到你运行出来。 Free 会将块重新插入其中，因此您可能永远不会运行。

分配内存的相关方法是通过 frame 分配器（有时是池分配器）；之所以这样命名，是因为它分发了对 N M 大小对象的访问权，而不是真正的动态分配器，其中每个对象的大小都不同。帧分配器非常棒，因为它们既快速又简单——一种罕见的组合。

因此，您当然可以在不动态分配的情况下使用您的系统，但您可能需要问问自己为什么？你可以用一个未指定的分配器来编写它，你可以用一个非常简单的帧分配器来实现它，然后根据需要扩展它。

Answer 3

这真的取决于你"dynamic allocation"的意思。

典型的散列 table 包含一个桶数组（或指向桶的指针数组）。每个桶都包含散列为相同散列的事物的集合。因此，如果要将 40000 int 的集合放入哈希 table 中，您将需要为每个存储桶集合本身进行某种形式的动态分配，因为您不知道每个存储桶中最终会有多少项目。

如果动态分配是指 "calls to malloc" 那么您可以管理哈希 table 本身的内存、桶集合、每个单独的桶自己使用“placement new”或一些您自己的内存管理的其他形式。您将计算实现哈希 table 所需的内存量，加上桶的集合，再加上最大使用桶数的最坏内存情况，即 40000，因为最坏情况是每个条目一个bucket 除非你的哈希函数的范围小于 40000

例如，散列 table 可能类似于

template <typename T> class Bucket {
  int size;
  T* items;
};

template <typename T> class HashTable {
  int size;  // optional if you know your hash function's range
  Bucket<T>* buckets;
};

所以你需要

max_buckets = min(hash_table_range, num_items);
bytesNeeded = sizeof(HashTable<T>)
            + num_hash_values * sizeof(Bucket<T>*)
            + max_buckets * sizeof(Bucket<T>)
            + sizeof(T) * num_items;

你仍然需要管理桶的分配（所以在某种意义上有 "dyanmic allocation"）并且你需要能够随着桶的增长而改变它们，因为没有在适当的地方种植它们的空间在我看来会增加大量的开销。只是您自己管理分配，所以是否 "dynamic allocation" 取决于您。

是否总是需要使用动态内存分配实现散列 table？

Is it always necessary to implement a hash table with dynamic memory allocation?

c++

implementation

hashtable

data-structures