Re: adjustable array vs hash-table

Slobodan Blazeski <slobodan.blazeski@xxxxxxxxx> writes:

I could use a hash-table or an adjustable array. Considering the keys
of the hash-table are equal to indices in the array 0.1.2.3.4...

You may consider binary trees, too, if your indeces are sparse (though
from your description, I'm assuming they're not).

functionality is the same. So which one is more efficient at
a. Expanding when new elements are added when container can't hold
them

This probably depends on the implementation, but a natural
implementation of hash tables will probably be an array with some kind
of linked list for the buckets. Which means that growing a hash table
should have about the same overhead as growing an array + the overhead
of redistributing the elements over the buckets. So hash tables are
probably slower to grow. Whether that really makes a difference depends
on how many times you're actually growing.

b. Accessing elements via index / key.

Hash tables will never be faster than arrays, and arrays are probably a
lot easier to optimize for homogenous simple values too.

Joost.



.

Relevant Pages

  • Re: memory leak in (?)... (redux)
    ... > the mem leaks in our long-running tcl daemons. ... There is an overhead, I'm not sure how well hidden it is, with array creation. ... the global variable hash table. ...
    (comp.lang.tcl)
  • Duck Typed Concepts for Ruby (was Re: A use case for an ordered hash)
    ... An Sequencable mixin can be defined that implements all sorts of operations such as append, concat, splice, sort, etc. ... extending an instance of Array with Sorted if the array is known to be sorted. ... Now returning to the thread at hand we can see that the difference between the associative array and hash hierarchies is that the hash hierarchy depends upon Hashable keys. ...
    (comp.lang.ruby)
  • Re: Suggestions for double-hashing scheme
    ... >> The items that are being moved are the items in the hash table itself, ... >> which are of fixed size (they are in an array, ... > typedef struct { ... One "uchar" aka 'unsigned char' is plenty to hold a probe ...
    (comp.programming)
  • [SUMMARY] Index and Query (#54)
    ... This was a fun quiz for me because I really don't know anything about indexing ... We see in initializethat the index is just a Hash. ... an Array of symbolic document names where the word can be found ). ...
    (comp.lang.ruby)
  • Re: Comment on how to uniquely track your objects in C# / hash table / get hash code
    ... Array, correct? ... This is largely irrelevant to the issue of performance, since hash ... where both insertions and lookups happen frequently, ... about fast lookups for balanced red/black binary trees. ...
    (microsoft.public.dotnet.languages.csharp)