How are hashtables (maps) stored in memory?

Question

This question is specifically for hashtables, but might also cover other data structures such as linked lists or trees.

For instance, if you have a struct as follows:

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

And each integer is 4-byte aligned and stored in memory sequentially, are the key and value of a hash table stored sequentially as well? If you consider the following:

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

Is that first element represented like this?

struct ListNode
{
 int key;
 string value;
}

And if the key and value are 4-byte aligned and stored sequentially, does it matter where the next pair is stored?

What about a node in a linked list?

Just trying to visualize this conceptually, and also see if the same guidelines for memory storage also apply for open-addressing hashing (the load is under 1) vs. chained hashing (load doesn't matter).

Answer 1

It's highly implementation-specific. And by that I am not only referring to the compiler, CPU architecture and ABI, but also the implementation of the hash table. Some hash tables use a struct that contains a key and a value next to each other, much like you have guessed. Others have one array of keys and one array of values, so that values[i] is the associated value for the key at keys[i]. This is independent of the "open addressing vs. separate chaining" question.

• reectrix: Thank you, that clears it up. Essentially, it depends on many different variables

Answer 2

A hash is a data structure itself. Here's your visualizing:

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

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

Using a hash function (langauge-specific), the keys are turned into places, and the values are placed there (in an array.)

Linked-lists i'm not as sure about, but i would be they are stored sequentially if they are created sequentially. Obviously, if what the nodes hold increases in size, they'd need to be moved and the pointer redefined to that point.

Answer 3

Usually when the value is not that big (int) it's best to group it together with the key (which by default shouldn't be too big), otherwise only a pointer to it is kept.

Answer 4

The simplest representation of a hash table is an array (the table). A hash function generates a number between 0 and the size of the array. That number is the index for the item.

There is more to it than this, bit that's the general concept and explains why lookups are so fast.