diff --git a/include/ftl/SmallMap.h b/include/ftl/SmallMap.h
new file mode 100644
index 0000000..87ae99c
--- /dev/null
+++ b/include/ftl/SmallMap.h
@@ -0,0 +1,205 @@
+/*
+ * Copyright 2020 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#pragma once
+
+#include <ftl/InitializerList.h>
+#include <ftl/SmallVector.h>
+
+#include <functional>
+#include <optional>
+#include <type_traits>
+#include <utility>
+
+namespace android::ftl {
+
+// Associative container with unique, unordered keys. Unlike std::unordered_map, key-value pairs are
+// stored in contiguous storage for cache efficiency. The map is allocated statically until its size
+// exceeds N, at which point mappings are relocated to dynamic memory.
+//
+// SmallMap<K, V, 0> unconditionally allocates on the heap.
+//
+// Example usage:
+//
+//    ftl::SmallMap<int, std::string, 3> map;
+//    assert(map.empty());
+//    assert(!map.dynamic());
+//
+//    map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+//    assert(map.size() == 3u);
+//    assert(!map.dynamic());
+//
+//    assert(map.contains(123));
+//    assert(map.find(42, [](const std::string& s) { return s.size(); }) == 3u);
+//
+//    const auto opt = map.find(-1);
+//    assert(opt);
+//
+//    std::string& ref = *opt;
+//    assert(ref.empty());
+//    ref = "xyz";
+//
+//    assert(map == SmallMap(ftl::init::map(-1, "xyz")(42, "???")(123, "abc")));
+//
+template <typename K, typename V, size_t N>
+class SmallMap final {
+    using Map = SmallVector<std::pair<const K, V>, N>;
+
+public:
+    using key_type = K;
+    using mapped_type = V;
+
+    using value_type = typename Map::value_type;
+    using size_type = typename Map::size_type;
+    using difference_type = typename Map::difference_type;
+
+    using reference = typename Map::reference;
+    using iterator = typename Map::iterator;
+
+    using const_reference = typename Map::const_reference;
+    using const_iterator = typename Map::const_iterator;
+
+    // Creates an empty map.
+    SmallMap() = default;
+
+    // Constructs at most N key-value pairs in place by forwarding per-pair constructor arguments.
+    // The template arguments K, V, and N are inferred using the deduction guide defined below.
+    // The syntax for listing pairs is as follows:
+    //
+    //     ftl::SmallMap map = ftl::init::map<int, std::string>(123, "abc")(-1)(42, 3u, '?');
+    //
+    //     static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, std::string, 3>>);
+    //     assert(map.size() == 3u);
+    //     assert(map.contains(-1) && map.find(-1)->get().empty());
+    //     assert(map.contains(42) && map.find(42)->get() == "???");
+    //     assert(map.contains(123) && map.find(123)->get() == "abc");
+    //
+    // The types of the key and value are deduced if the first pair contains exactly two arguments:
+    //
+    //     ftl::SmallMap map = ftl::init::map(0, 'a')(1, 'b')(2, 'c');
+    //     static_assert(std::is_same_v<decltype(map), ftl::SmallMap<int, char, 3>>);
+    //
+    template <typename U, size_t... Sizes, typename... Types>
+    SmallMap(InitializerList<U, std::index_sequence<Sizes...>, Types...>&& init)
+          : mMap(std::move(init)) {
+        // TODO: Enforce unique keys.
+    }
+
+    size_type max_size() const { return mMap.max_size(); }
+    size_type size() const { return mMap.size(); }
+    bool empty() const { return mMap.empty(); }
+
+    // Returns whether the map is backed by static or dynamic storage.
+    bool dynamic() const { return mMap.dynamic(); }
+
+    iterator begin() { return mMap.begin(); }
+    const_iterator begin() const { return cbegin(); }
+    const_iterator cbegin() const { return mMap.cbegin(); }
+
+    iterator end() { return mMap.end(); }
+    const_iterator end() const { return cend(); }
+    const_iterator cend() const { return mMap.cend(); }
+
+    // Returns whether a mapping exists for the given key.
+    bool contains(const key_type& key) const {
+        return find(key, [](const mapped_type&) {});
+    }
+
+    // Returns a reference to the value for the given key, or std::nullopt if the key was not found.
+    //
+    //     ftl::SmallMap map = ftl::init::map('a', 'A')('b', 'B')('c', 'C');
+    //
+    //     const auto opt = map.find('c');
+    //     assert(opt == 'C');
+    //
+    //     char d = 'd';
+    //     const auto ref = map.find('d').value_or(std::ref(d));
+    //     ref.get() = 'D';
+    //     assert(d == 'D');
+    //
+    auto find(const key_type& key) const
+            -> std::optional<std::reference_wrapper<const mapped_type>> {
+        return find(key, [](const mapped_type& v) { return std::cref(v); });
+    }
+
+    auto find(const key_type& key) -> std::optional<std::reference_wrapper<mapped_type>> {
+        return find(key, [](mapped_type& v) { return std::ref(v); });
+    }
+
+    // Returns the result R of a unary operation F on (a constant or mutable reference to) the value
+    // for the given key, or std::nullopt if the key was not found. If F has a return type of void,
+    // then the Boolean result indicates whether the key was found.
+    //
+    //     ftl::SmallMap map = ftl::init::map('a', 'x')('b', 'y')('c', 'z');
+    //
+    //     assert(map.find('c', [](char c) { return std::toupper(c); }) == 'Z');
+    //     assert(map.find('c', [](char& c) { c = std::toupper(c); }));
+    //
+    template <typename F, typename R = std::invoke_result_t<F, const mapped_type&>>
+    auto find(const key_type& key, F f) const
+            -> std::conditional_t<std::is_void_v<R>, bool, std::optional<R>> {
+        for (auto& [k, v] : *this) {
+            if (k == key) {
+                if constexpr (std::is_void_v<R>) {
+                    f(v);
+                    return true;
+                } else {
+                    return f(v);
+                }
+            }
+        }
+
+        return {};
+    }
+
+    template <typename F>
+    auto find(const key_type& key, F f) {
+        return std::as_const(*this).find(key, [&f](const mapped_type& v) {
+            return f(const_cast<mapped_type&>(v));
+        });
+    }
+
+private:
+    Map mMap;
+};
+
+// Deduction guide for in-place constructor.
+template <typename K, typename V, size_t... Sizes, typename... Types>
+SmallMap(InitializerList<KeyValue<K, V>, std::index_sequence<Sizes...>, Types...>&&)
+        -> SmallMap<K, V, sizeof...(Sizes)>;
+
+// Returns whether the key-value pairs of two maps are equal.
+template <typename K, typename V, size_t N, typename Q, typename W, size_t M>
+bool operator==(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
+    if (lhs.size() != rhs.size()) return false;
+
+    for (const auto& [k, v] : lhs) {
+        const auto& lv = v;
+        if (!rhs.find(k, [&lv](const auto& rv) { return lv == rv; }).value_or(false)) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+// TODO: Remove in C++20.
+template <typename K, typename V, size_t N, typename Q, typename W, size_t M>
+inline bool operator!=(const SmallMap<K, V, N>& lhs, const SmallMap<Q, W, M>& rhs) {
+    return !(lhs == rhs);
+}
+
+} // namespace android::ftl