Hash tables are among the most useful data structures for efficient coding. An hash table can be abstractly thought as a map from a set of unique keys (which may be strings, numbers, or even more complicated objects) to a set of values. From a computational viewpoint, its most distinctive feature is that its read/write operations (i.e. storing, retrieving or deleting a particular key or key-value pair) have average \(O(1)\) time complexity, independent of the table size.
Many programming languages come with their own native implementation of hash tables (for instance
std::unordered_map/sets in C++, or
sets in Python); in base R, the objects which come closest to hash tables are
environments. These, however, can be somewhat cumbersome to handle from the user point of view, and only support string type keys. The purpose of r2r is to provide a more flexible implementation of hash tables in R, building on top of base R
r2r hash tables support:
This document provides a quick hands-on introduction to
r2r hash tables.
We create an empty hash map with:
m <- hashmap()
We can insert key-value pairs in
m in several different ways:
In addition to hash maps, we can also create hash sets, which simply store keys:
There is no restriction on the type of object you can use as keys and values. For instance:
You can set default values for missing keys. For instance:
m <- hashmap(default = 0)
which is useful for creating a counter:
objects <- list(1, 1, "1", FALSE, "1", 1) for (object in objects) m[[object]] <- m[[object]] + 1 m[["1"]] #>  2
Alternatively, you may throw an exception upon querying a missing key:
hashmaps use by default
base::identical() to compare keys. For instance:
m <- hashmap() m[] <- "double" m[["1"]] <- "character" m[] #>  "double"
This behavior can be changed by explicitly providing a key comparison function. For this to work correctly, one must also explicitly provide an hash function which produces the same hashes for equivalent keys. A simple way to do this is to apply a preprocessing function to keys, as illustrated by the following example.
We assume that keys are length one complex numbers, and consider two keys equivalent when they have the same direction in the complex plane. The direction of a complex vector can be found applying the R function
Arg(), which is thus a sensible key preprocessing function. We can instruct an hashmap to preprocess its keys in this way through the constructor’s
m <- hashmap(key_preproc_fn = Arg)
Let us check that everything works as intended: