diff --git a/re2/compile.cc b/re2/compile.cc
index 26b8e43..9a19bde 100644
--- a/re2/compile.cc
+++ b/re2/compile.cc
@@ -10,7 +10,7 @@
 
 #include <stdint.h>
 #include <string.h>
-#include <map>
+#include <unordered_map>
 #include <utility>
 
 #include "util/logging.h"
@@ -245,7 +245,7 @@
 
   int64_t max_mem_;    // Total memory budget.
 
-  std::map<uint64_t, int> rune_cache_;
+  std::unordered_map<uint64_t, int> rune_cache_;
   Frag rune_range_;
 
   RE2::Anchor anchor_;  // anchor mode for RE2::Set
@@ -495,7 +495,7 @@
 int Compiler::CachedRuneByteSuffix(uint8_t lo, uint8_t hi, bool foldcase,
                                    int next) {
   uint64_t key = MakeRuneCacheKey(lo, hi, foldcase, next);
-  std::map<uint64_t, int>::const_iterator it = rune_cache_.find(key);
+  std::unordered_map<uint64_t, int>::const_iterator it = rune_cache_.find(key);
   if (it != rune_cache_.end())
     return it->second;
   int id = UncachedRuneByteSuffix(lo, hi, foldcase, next);