[R] beginner Q: hashtable or dictionary?

[hadley wickham]

> > Is a list O(1) for setting and getting?
>
> Can you elaborate?  R is a vector language, and normally you create a list
> in one pass, and you can retrieve multiple elements at once.

When you use a hash table you expect it to be O(1) (on average) for
getting and setting values (conditional on having a good hash
function, a large enough table etc...).  (and thanks for the pointer
to that RNEWS item)

> Indexing by number is O(1) except where replacement causes the list vector
> to be copied.  There is always the option to use match() to convert to
> numeric indexing.

I read this to mean that setting a value in list will be O(n) (where n
is the length of the new list) - If you blindly expect a list to act
like a hash table you will be badly surprised.  If you are copying an
algorithm from another language, you will probably need to rethink the
way that updates work.  If however, you just want an object that can
be indexed by a string, then a list will be fine.

Regards,

Hadley