[R] beginner Q: hashtable or dictionary?

[Prof Brian Ripley]

On Sun, 29 Jan 2006, hadley wickham wrote:

>> use a 'list':
>
> 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.

Retrieving elements by name from a long vector (including a list) is very 
fast, as an internal hash table is used.  Does the following item from 
ONEWS answer your question?

     o	Indexing a vector by a character vector was slow if both the
 	vector and index were long (say 10,000).  Now hashing is used
 	and the time should be linear in the longer of the lengths
 	(but more memory is used).

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.

-- 
Brian D. Ripley,                  ripley at stats.ox.ac.uk
Professor of Applied Statistics,  http://www.stats.ox.ac.uk/~ripley/
University of Oxford,             Tel:  +44 1865 272861 (self)
1 South Parks Road,                     +44 1865 272866 (PA)
Oxford OX1 3TG, UK                Fax:  +44 1865 272595