On Data Structures

Wirth famously said: Programs = Algorithms + Data Structures.

This programmer believes that on the right-hand side of the equation, data structures carry more weight than algorithms. Once the data structure is defined, the algorithms you use are basically determined, and the time complexity of those algorithms is in the same ballpark. Last week I shared a topic on data structures internally with my team, and here I’ll share it with you as well.

Modern programming languages come with more and more built-in data structures, from primitive types—integer, float, boolean, string—all the way to complex structures such as array, list, map, set, and so on. These structures are plug-and-play and very convenient, but sometimes we also need to understand their internal implementation (their internal data structures) in order to build high-performance applications. Some ‘clever’ languages, such as Clojure, dynamically switch internal structures according to the use case. For a map, for example, when the number of keys exceeds a certain threshold, it automatically switches to a more efficient structure to meet the demand.

Today, let’s dig into what common data types in programming languages really look like under the hood.

array / tuple

Arrays or tuples are the container data types everyone knows best; internally they can hold other data structures. Their defining characteristic is that the elements inside the container are allocated in contiguous memory and can be accessed randomly by index, with O(1) time complexity. Arrays generally require their contents to be homogeneous, while tuples allow heterogeneity.

For functional programming languages, or languages that provide immutable data structures, handling arrays efficiently is a challenge. If code modifies an element in an array, copying and rebuilding the entire array is too expensive. We need a suitable data structure that can structurally share most of the unaffected data. That data structure is the persistent data structure used by most functional programming languages. A persistent data structure uses a DAG (usually a trie) to describe data. When some part of the DAG changes, we only need to regenerate the nodes on the path related to the change, which is very efficient. For arrays, we can use a Bit Array Mapped Trie / Index Vector Trie:

By slicing the binary representation of the index and traversing the trie, the corresponding leaf node is the node we’re looking for. If we want to modify the contents of that node while keeping the original structure unchanged, we only need to create a new node and generate the relevant intermediate nodes along that path all the way up to the root. The amount of extra copying required depends only on the depth of the trie.

List

In most programming languages, when people mention a list, internally it is generally a doubly linked list with a tail pointer. Therefore, adding new nodes at the head or tail is very efficient—an O(1) operation—while lookup, insertion, and deletion require traversing the list and are O(n) operations. Because it is a linked list, getting its length generally also requires traversal, which is an O(n) operation. Some programming languages optimize this by maintaining the list length at the head of the list, making length retrieval O(1). Please make sure you understand how efficient this operation is in the language you use. In Erlang, the length function has O(n) complexity, so don’t abuse length on large lists.

Map

A map is called an associative array (PHP), dict (Python), and so on in many languages. It is a container of key/value pairs. In theory it can hold any number of key/value pairs. In a map, keys are unique, and both keys and values can generally be arbitrary data structures. When keys can only be strings, some languages use a standard trie or a Patricia trie to handle them.

Early maps were implemented with a hash array + collision avoidance; typical collision avoidance strategies include chaining and probing. After a key passes through some hash function, it corresponds to a position in the hash array. If that position already contains data, then either the data is chained together with a linked list—this is chaining—or a free slot is found at some fixed subsequent position in the array (probe) and written to—this is probing.

The problem with chaining is that if the number of keys greatly exceeds the length of the hash array, collisions become severe, greatly reducing performance. In the worst case, time complexity is O(n/k). The problem with probing is that the hash table must be as large as the key space; if the hash function is poorly chosen, it easily causes large-scale collisions. For maps that support dynamically adding and removing keys, it is often necessary to enlarge the hash table and then rehash, which carries considerable memory and computational costs. Python’s dict is implemented using a hash array + collision avoidance.

C++ and many other languages use red-black trees to support maps. Here’s a comparison between hash arrays and red-black trees:

Today most FP languages use maps based on the persistent data structure mentioned above: HAMT (Hash Array Mapped Trie, by Phil Bagwell):

It processes the key through a hash function into a number, then searches downward starting from the low bits of that hash value until it finds a leaf node. If the data on the leaf node matches the key, the lookup succeeds; otherwise, it fails. HAMT uses a 32-bit / 64-bit hash value (the diagram above is merely illustrative), so the probability of hash collision is very small. If a collision does occur, the leaf node is converted into an index node, and a different hash method is used to compute the original leaf node and the new node, mounting them under the index node.

Tree

There are many kinds of trees. Here I’ll discuss the commonly used AVL, Trie, and the recently popular Merkle tree.

AVL is a relatively simple tree: the heights of the left and right subtrees differ by no more than 1. If a newly inserted node breaks this balance, rotations (possibly multiple) are needed to restore balance.

A Trie is a prefix tree and can be used for routing queries. Erlang’s pattern matching mechanism compiles code that uses pattern matching into a code structure similar to a Trie.

The Merkle tree originated from cryptographic algorithms. It can verify the correctness of any part of the tree and is widely used in file systems (ZFS), chunked file downloads (BitTorrent), blockchains, and so on.

In a Merkle tree, each data unit generates a hash, adjacent hashes are paired together to generate another hash, and this pairwise combination continues all the way to the root. If the total number of data units is odd, the last hash is combined with itself.

Let’s take file synchronization verification as an example. Suppose a local disk and a cloud drive each have 128 files (2^7), and each generates a Merkle tree. We only need to compare from the root node downward, with O(logN) efficiency, to find the files that differ.