首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >哈希表(映射)是如何存储在内存中的?

问哈希表(映射)是如何存储在内存中的?
EN

Stack Overflow用户
提问于 2013-08-24 05:36:09
回答 3查看 1.6K关注 0票数 1

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

例如,如果你有一个如下的结构:

代码语言:javascript
复制
struct Data 
{
   int value1;
   int value2;
   int value3;
}

而且每个整数都是4字节对齐的,并按顺序存储在内存中,哈希表的键和值是否也按顺序存储?如果您考虑以下几点:

代码语言:javascript
复制
std::map<int, string> list;
list[0] = "first";

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

代码语言:javascript
复制
struct ListNode
{
   int key;
   string value;
}

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

那么链表中的一个节点呢?

只是尝试在概念上可视化这一点,并查看内存存储的相同指导原则是否也适用于开放寻址散列(负载低于1)与链式散列(负载无关紧要)。

EN

回答 3

Stack Overflow用户

发布于 2013-08-24 05:42:55

它是高度特定于实现的。这里我指的不仅是编译器、CPU体系结构和ABI,还包括哈希表的实现。一些哈希表使用一个结构,该结构包含一个键和一个值,就像您已经猜到的那样。其他的则有一个键数组和一个值数组,因此values[i]是keys[i]中的键的关联值。这与“开放寻址与独立链接”的问题无关。

票数 2
EN

Stack Overflow用户

发布于 2013-08-24 05:43:46

哈希本身就是一种数据结构。这是你的视觉化:

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

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

使用散列函数(特定于langauge),将键转换为位置,并将值放在那里(在数组中)。

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

票数 0
EN

Stack Overflow用户

发布于 2013-08-24 10:11:08

通常,当值不是很大(int)时,最好将它与键(默认情况下不应该太大)组合在一起,否则只保留一个指向它的指针。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/18412240

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档