memory - 哈希表（映射）如何存储在内存中？

Question

这个问题专门针对哈希表，但也可能涉及其他数据结构，例如链表或树。

例如，如果您有如下结构：

struct Data 
{
   int value1;
   int value2;
   int value3;
}

并且每个整数都是 4 字节对齐并按顺序存储在内存中的，哈希表的键和值是否也按顺序存储？如果您考虑以下情况：

std::map<int, string> list;
list[0] = "first";

第一个元素是这样表示的吗？

struct ListNode
{
   int key;
   string value;
}

如果键和值是 4 字节对齐并按顺序存储的，那么下一对存储在哪里有关系吗？

那么链表中的节点呢？

只是试图在概念上可视化这一点，并查看内存存储的相同准则是否也适用于开放寻址散列（负载低于 1）与链式散列（负载无关紧要）。

score 2 · Accepted Answer

它是高度特定于实现的。我不仅指的是编译器、CPU 架构和 ABI，还指的是哈希表的实现。一些哈希表使用一个结构，它包含一个键和一个值，就像你猜到的一样。其他人有一个键数组和一个值数组，因此这values[i]是键的关联值 at keys[i]。这与“开放寻址与单独链接”问题无关。

score 0 · Accepted Answer

通常当值不是那么大（int）时，最好将它与键组合在一起（默认情况下不应该太大），否则只保留指向它的指针。

score 0 · Accepted Answer

哈希本身就是一种数据结构。这是您的可视化：

使用哈希函数（特定于语言），将键转换为位置，并将值放置在那里（在数组中）。

链接列表我不太确定，但如果它们是按顺序创建的，我会按顺序存储它们。显然，如果节点持有的大小增加，则需要移动它们并将指针重新定义到该点。

3 回答 3