Re: adjustable array vs hash-table

On Jan 30, 10:09 pm, Slobodan Blazeski <slobodan.blaze...@xxxxxxxxx>
wrote:
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...
functionality is the same. So which one is more efficient at
a. Expanding when new elements are added when container can't hold
them
b. Accessing elements via index / key.

thanks
Slobodan

Adjustable arrays should prove faster, and save memory (unless a
minimal perfect hash function is used).
1. If you can preallocate the expected number of array slots when the
array is first created, you minimize memory reallocations.
2. if your keys are really 0,1,2,3,..., then it sounds like you can
get around having to call a hash function (which saves time).
3. arrays are a little more cache-friendly than hash tables because
data is more localized/dense than if a bunch of pointers are used to
create the hash table.
4. side benefit: arrays give you some sort of ordering that standard
hash tables do not provide.
Lou
.

Relevant Pages

  • 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)
  • Re: problem with hash & sort array
    ... Then I put the hash into an array with the sort ... The twist is I have to identify the duplicate ... a real data structure, and in the next place I make the exact opposite ...
    (comp.lang.perl.misc)