6.355
Speeding up Lookup with Hash Maps in R

list.of.packages <- c("r2r")
new.packages <- list.of.packages[!(list.of.packages %in% installed.packages()[,"Package"])]
if(length(new.packages)) install.packages(new.packages, repos='http://cran.us.r-project.org', verbose = F, quiet = T)

Introduction

A hash map (also often called a hash table or associative array), is a common key-value data structure. While most programming languages provide some implementation of this vital data structure, there is no equivalent in R due to the way R manages memory and doesn’t allow dynamic data structures such as linked lists. There are some options, nevertheless, which we will demonstrate in this lesson.

The principal reason for using a hash map is that looking up a value based on its key is constant time (\(O(1)\)) regardless of the number of elements in the map. In contrast, looking up a value in an array or list of \(O(n)\), i.e., it increases linearly with the number of elements in the structure.

Key/Value Pairs

A key/value pair is a key plus some value that is stored for that key. For example, a table in a relational database can be considered a set of of key/value pairs where the key is the “primary key” of the table and the value is the set of non-prime attributes. Another example is a journal identified by its ISSN and the value would be the journal’s title.

For the experiments in the remainder of the lesson we will need some sample key/value pairs. The code below generates a set of those with unique keys with corresponding values.

n <- 10
keys.10 <- as.character(sample(100001:999999, n))
vals.10 <- paste0("value-", keys.10)

n <- 100
keys.100 <- as.character(sample(100001:999999, n))
vals.100 <- paste0("value-", keys.100)

n <- 1000
keys.1000 <- as.character(sample(100001:999999, n))
vals.1000 <- paste0("value-", keys.1000)

n <- 10000
keys.10000 <- as.character(sample(100001:999999, n))
vals.10000 <- paste0("value-", keys.10000)

n <- 100000
keys.100000 <- as.character(sample(100001:999999, n))
vals.100000 <- paste0("value-", keys.100000)

n <- 1000000
keys.1000000 <- as.character(sample(1000001:9999999, n))
vals.1000000 <- paste0("value-", keys.1000000)

Linear Lookup

While R does support named vectors and lists and allows for associative access, the performance is \(O(n)\) and does not scale. Essentially, any lookup is a linear search through the vector or list.

lookup.linear <- function (x, keys, vals)
{
  s <- 1:(length(m))
  
  for (i in s) {
    if (keys[i] == x)
      return (vals[i])
  }
  
  return (NA)
}

Let’s add some data to this data structure so we can perform some timings on lookup performance. Keys have to be unique so we need to generate some number of unique key values.

Named Vectors

Hash Maps

Operations on Hash Tables

There are three main operations that must be implemented for a functioning hash map data structure. Given a key (as a string) and a value associated with that key:

• INSERT will add the key/value pair to the hash map
• LOOKUP will search the hash map for a key and return the associated value if it exists
• DELETE will remove a value based on a key

There are other useful operations, such as EXISTS that returns true if the key exists and false otherwise.

Package r2r

library(r2r)

hm <- hashmap()

Summary

---

Files & Resources

All Files for Lesson 6.355

---

References

Horner, J. (March 24, 2015). Hash Table Performance in R: Part I. R-bloggers.

r2r: R-Object to R-Object Hash Maps

Errata

Let us know.