E
Evangelista Sami
hello all
i am implementing an application in which a large number of (char *)
is stored into a hash table structure.
As there may be collisions, each (char *) inserted into my hash table
is put into an array. here is the definition of my hash table :
typedef struct
{
short size;
char **elements;
} hash_cell;
hash_cell hash_table[100000];
with this approach, each time i want to store an additional (char *) i
reallocate the array elements and add it an additional element.
this works fine but i have an overhead of a (char *) per element.
Another idea is to use a single (char *) by cell in the hash table and
to encode the size of each (char *) in this one with for instance 16
bits. the definition of this hash table should be :
typedef struct
{
short size;
char *elements;
} hash_cell;
hash_cell hash_table[100000];
For example if in the cell 0 i have three elements "toto", "abc", and
"peter",
i will have :
hash_table[0].elements[0 .. 1] = 4
hash_table[0].elements[2 .. 5] = "toto"
hash_table[0].elements[6 .. 7] = 3
hash_table[0].elements[8 .. 10] = "abc"
hash_table[0].elements[11 .. 12] = 3
hash_table[0].elements[13 .. 17] = "peter"
this makes me save 4 - 2 = 2 bytes if i assume that the size of (char
*) is 4 bytes and that the length of each element is encoded with 2
bytes.
However when i make the "ps aux" command during the execution, it
appears that the whole memory consumed by the first method is less
than with the second method and i cant see why.
Any explanation would be very useful
Sami Evangelista
i am implementing an application in which a large number of (char *)
is stored into a hash table structure.
As there may be collisions, each (char *) inserted into my hash table
is put into an array. here is the definition of my hash table :
typedef struct
{
short size;
char **elements;
} hash_cell;
hash_cell hash_table[100000];
with this approach, each time i want to store an additional (char *) i
reallocate the array elements and add it an additional element.
this works fine but i have an overhead of a (char *) per element.
Another idea is to use a single (char *) by cell in the hash table and
to encode the size of each (char *) in this one with for instance 16
bits. the definition of this hash table should be :
typedef struct
{
short size;
char *elements;
} hash_cell;
hash_cell hash_table[100000];
For example if in the cell 0 i have three elements "toto", "abc", and
"peter",
i will have :
hash_table[0].elements[0 .. 1] = 4
hash_table[0].elements[2 .. 5] = "toto"
hash_table[0].elements[6 .. 7] = 3
hash_table[0].elements[8 .. 10] = "abc"
hash_table[0].elements[11 .. 12] = 3
hash_table[0].elements[13 .. 17] = "peter"
this makes me save 4 - 2 = 2 bytes if i assume that the size of (char
*) is 4 bytes and that the length of each element is encoded with 2
bytes.
However when i make the "ps aux" command during the execution, it
appears that the whole memory consumed by the first method is less
than with the second method and i cant see why.
Any explanation would be very useful
Sami Evangelista