Re: Not preserving order in chained list of hash table Any consequences

[Sven Neumann <sven gimp org>]

Hi,

Ariel Burbaickij mni fh-giessen de writes:

> As I see from following code excerpt from g_hash_table_resize():
> 
>   for (i = 0; i < hash_table->size; i++)
>     for (node = hash_table->nodes[i]; node; node = next)
>       {
>         next = node->next;
> 
>         hash_val = (* hash_table->hash_func) (node->key) % new_size;
> 
>         node->next = new_nodes[hash_val];
>         new_nodes[hash_val] = node;
>       }
> order of entries in the appropriate chained list is not preserved while
> resizing the table. All entries in the list are linked to the head of the list
> one after another. So one can even say that the chained list is reversed.
> 
> My questions:
> 1) Am I right with my view of the matter ?
> If the first question is answered with "yes"
>   1a) Can violation of order lead to some unpleasant consequencies
>       for application programmer supposing some particular order of elements
>       in chained list?
>   1b) Should probably the notice be made in source code that the order is not
>       preserved?

I think you are right but a hash table by definition doesn't allow the
developer to make any assumptions about the order of elements. Or, in
other words, the order of elements in a hash table is absolutely
undeterministic. Any code that assumes anything about the order of
elements is broken.


Salut, Sven