## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

## Chapter 13. Maps and Hash Tables

Lots of programming problems require dealing with data organized as key/value pairs. Maybe the simplest way of representing such data in OCaml is an association list, which is simply a list of pairs of keys and values. For example, you could represent a mapping between the 10 digits and their English names as follows:

OCaml utop (part 1)

````# ``let digit_alist =`
`    [ 0, "zero"; 1, "one"; 2, "two"  ; 3, "three"; 4, "four"`
`    ; 5, "five"; 6, "six"; 7, "seven"; 8, "eight"; 9, "nine" ]`
`  ;;`
`val digit_alist : (int * string) list =`
`  [(0, "zero"); (1, "one"); (2, "two"); (3, "three"); (4, "four");`
`   (5, "five"); (6, "six"); (7, "seven"); (8, "eight"); (9, "nine")]````

We can use functions from the `List.Assoc` module to manipulate this data:

OCaml utop (part 2)

````# ``List.Assoc.find digit_alist 6;;`
`- : string option = Some "six"`
`# ``List.Assoc.find digit_alist 22;;`
`- : string option = None`
`# ``List.Assoc.add digit_alist 0 "zilch";;`
`- : (int, string) List.Assoc.t =`
`[(0, "zilch"); (1, "one"); (2, "two"); (3, "three"); (4, "four");`
` (5, "five"); (6, "six"); (7, "seven"); (8, "eight"); (9, "nine")]````

Association lists are simple and easy to use, but their performance is not ideal, since almost every nontrivial operation on an association list requires a linear-time scan of the list.

In this chapter, we’ll talk about two more efficient alternatives to association lists: maps and hash tables. A map is an immutable tree-based data structure where most operations take time logarithmic in the size ...

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required