这个问题是专门针对哈希表的,但也可能涉及其他数据结构,如链表或树。
例如,如果你有一个如下的结构:
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)与链式散列(负载无关紧要)。
发布于 2013-08-24 05:42:55
它是高度特定于实现的。这里我指的不仅是编译器、CPU体系结构和ABI,还包括哈希表的实现。一些哈希表使用一个结构,该结构包含一个键和一个值,就像您已经猜到的那样。其他的则有一个键数组和一个值数组,因此values[i]是keys[i]中的键的关联值。这与“开放寻址与独立链接”的问题无关。
发布于 2013-08-24 05:43:46
哈希本身就是一种数据结构。这是你的视觉化:
http://en.wikipedia.org/wiki/Hash_table
http://en.wikipedia.org/wiki/Hash_function
使用散列函数(特定于langauge),将键转换为位置,并将值放在那里(在数组中)。
链表-我不太确定,但如果它们是按顺序创建的,我会按顺序存储它们。显然,如果节点的大小增加,则需要移动节点并重新定义指针。
发布于 2013-08-24 10:11:08
通常,当值不是很大(int)时,最好将它与键(默认情况下不应该太大)组合在一起,否则只保留一个指向它的指针。
https://stackoverflow.com/questions/18412240
复制相似问题