diff --git a/clang-tools-extra/clang-tidy/ClangTidy.cpp b/clang-tools-extra/clang-tidy/ClangTidy.cpp
--- a/clang-tools-extra/clang-tidy/ClangTidy.cpp
+++ b/clang-tools-extra/clang-tidy/ClangTidy.cpp
@@ -329,12 +329,11 @@
                                          AnalyzerOptionsRef AnalyzerOptions) {
   StringRef AnalyzerPrefix(AnalyzerCheckNamePrefix);
   for (const auto &Opt : Opts.CheckOptions) {
-    StringRef OptName(Opt.first);
-    if (!OptName.startswith(AnalyzerPrefix))
+    StringRef OptName(Opt.getKey());
+    if (!OptName.consume_front(AnalyzerPrefix))
       continue;
     // Analyzer options are always local options so we can ignore priority.
-    AnalyzerOptions->Config[OptName.substr(AnalyzerPrefix.size())] =
-        Opt.second.Value;
+    AnalyzerOptions->Config[OptName] = Opt.second.Value;
   }
 }
 
diff --git a/clang-tools-extra/clang-tidy/ClangTidyCheck.cpp b/clang-tools-extra/clang-tidy/ClangTidyCheck.cpp
--- a/clang-tools-extra/clang-tidy/ClangTidyCheck.cpp
+++ b/clang-tools-extra/clang-tidy/ClangTidyCheck.cpp
@@ -72,7 +72,7 @@
 ClangTidyCheck::OptionsView::get(StringRef LocalName) const {
   const auto &Iter = CheckOptions.find(NamePrefix + LocalName.str());
   if (Iter != CheckOptions.end())
-    return Iter->second.Value;
+    return Iter->getValue().Value;
   return llvm::make_error<MissingOptionError>((NamePrefix + LocalName).str());
 }
 
@@ -85,7 +85,7 @@
     return IterGlobal;
   if (IterGlobal == Options.end())
     return IterLocal;
-  if (IterLocal->second.Priority >= IterGlobal->second.Priority)
+  if (IterLocal->getValue().Priority >= IterGlobal->getValue().Priority)
     return IterLocal;
   return IterGlobal;
 }
@@ -94,7 +94,7 @@
 ClangTidyCheck::OptionsView::getLocalOrGlobal(StringRef LocalName) const {
   auto Iter = findPriorityOption(CheckOptions, NamePrefix, LocalName);
   if (Iter != CheckOptions.end())
-    return Iter->second.Value;
+    return Iter->getValue().Value;
   return llvm::make_error<MissingOptionError>((NamePrefix + LocalName).str());
 }
 
@@ -135,7 +135,7 @@
 ClangTidyCheck::OptionsView::getLocalOrGlobal<bool>(StringRef LocalName) const {
   auto Iter = findPriorityOption(CheckOptions, NamePrefix, LocalName);
   if (Iter != CheckOptions.end())
-    return getAsBool(Iter->second.Value, Iter->first);
+    return getAsBool(Iter->getValue().Value, Iter->getKey());
   return llvm::make_error<MissingOptionError>((NamePrefix + LocalName).str());
 }
 
@@ -177,7 +177,7 @@
   if (Iter == CheckOptions.end())
     return llvm::make_error<MissingOptionError>((NamePrefix + LocalName).str());
 
-  StringRef Value = Iter->second.Value;
+  StringRef Value = Iter->getValue().Value;
   StringRef Closest;
   unsigned EditDistance = -1;
   for (const auto &NameAndEnum : Mapping) {
@@ -199,9 +199,9 @@
   }
   if (EditDistance < 3)
     return llvm::make_error<UnparseableEnumOptionError>(
-        Iter->first, Iter->second.Value, std::string(Closest));
-  return llvm::make_error<UnparseableEnumOptionError>(Iter->first,
-                                                      Iter->second.Value);
+        Iter->getKey().str(), Iter->getValue().Value, Closest.str());
+  return llvm::make_error<UnparseableEnumOptionError>(Iter->getKey().str(),
+                                                      Iter->getValue().Value);
 }
 
 void ClangTidyCheck::OptionsView::logErrToStdErr(llvm::Error &&Err) {
diff --git a/clang-tools-extra/clang-tidy/ClangTidyOptions.h b/clang-tools-extra/clang-tidy/ClangTidyOptions.h
--- a/clang-tools-extra/clang-tidy/ClangTidyOptions.h
+++ b/clang-tools-extra/clang-tidy/ClangTidyOptions.h
@@ -16,7 +16,6 @@
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include <functional>
-#include <map>
 #include <string>
 #include <system_error>
 #include <utility>
@@ -108,7 +107,7 @@
     unsigned Priority;
   };
   typedef std::pair<std::string, std::string> StringPair;
-  typedef std::map<std::string, ClangTidyValue> OptionMap;
+  typedef llvm::StringMap<ClangTidyValue> OptionMap;
 
   /// Key-value mapping used to store check-specific options.
   OptionMap CheckOptions;
diff --git a/clang-tools-extra/clang-tidy/ClangTidyOptions.cpp b/clang-tools-extra/clang-tidy/ClangTidyOptions.cpp
--- a/clang-tools-extra/clang-tidy/ClangTidyOptions.cpp
+++ b/clang-tools-extra/clang-tidy/ClangTidyOptions.cpp
@@ -70,7 +70,7 @@
   NOptionMap(IO &, const ClangTidyOptions::OptionMap &OptionMap) {
     Options.reserve(OptionMap.size());
     for (const auto &KeyValue : OptionMap)
-      Options.emplace_back(KeyValue.first, KeyValue.second.Value);
+      Options.emplace_back(KeyValue.getKey(), KeyValue.getValue().Value);
   }
   ClangTidyOptions::OptionMap denormalize(IO &) {
     ClangTidyOptions::OptionMap Map;
@@ -157,8 +157,10 @@
   mergeVectors(Result.ExtraArgsBefore, Other.ExtraArgsBefore);
 
   for (const auto &KeyValue : Other.CheckOptions) {
-    Result.CheckOptions[KeyValue.first] = ClangTidyValue(
-        KeyValue.second.Value, KeyValue.second.Priority + Priority);
+    Result.CheckOptions.insert_or_assign(
+        KeyValue.getKey(),
+        ClangTidyValue(KeyValue.getValue().Value,
+                       KeyValue.getValue().Priority + Priority));
   }
 
   return Result;
diff --git a/clang-tools-extra/test/clang-tidy/checkers/google-module.cpp b/clang-tools-extra/test/clang-tidy/checkers/google-module.cpp
--- a/clang-tools-extra/test/clang-tidy/checkers/google-module.cpp
+++ b/clang-tools-extra/test/clang-tidy/checkers/google-module.cpp
@@ -1,10 +1,6 @@
 // RUN: clang-tidy -checks='-*,google*' -config='{}' -dump-config - -- | FileCheck %s
 // CHECK: CheckOptions:
-// CHECK: {{- key: *google-readability-braces-around-statements.ShortStatementLines}}
-// CHECK-NEXT: {{value: *'1'}}
-// CHECK: {{- key: *google-readability-function-size.StatementThreshold}}
-// CHECK-NEXT: {{value: *'800'}}
-// CHECK: {{- key: *google-readability-namespace-comments.ShortNamespaceLines}}
-// CHECK-NEXT: {{value: *'10'}}
-// CHECK: {{- key: *google-readability-namespace-comments.SpacesBeforeComments}}
-// CHECK-NEXT: {{value: *'2'}}
+// CHECK-DAG: {{- key: *google-readability-braces-around-statements.ShortStatementLines *[[:space:]] *value: *'1'}}
+// CHECK-DAG: {{- key: *google-readability-function-size.StatementThreshold *[[:space:]] *value: *'800'}}
+// CHECK-DAG: {{- key: *google-readability-namespace-comments.ShortNamespaceLines *[[:space:]] *value: *'10'}}
+// CHECK-DAG: {{- key: *google-readability-namespace-comments.SpacesBeforeComments *[[:space:]] *value: *'2'}}
diff --git a/clang-tools-extra/test/clang-tidy/infrastructure/config-files.cpp b/clang-tools-extra/test/clang-tidy/infrastructure/config-files.cpp
--- a/clang-tools-extra/test/clang-tidy/infrastructure/config-files.cpp
+++ b/clang-tools-extra/test/clang-tidy/infrastructure/config-files.cpp
@@ -17,14 +17,10 @@
 // For this test we have to use names of the real checks because otherwise values are ignored.
 // RUN: clang-tidy -dump-config %S/Inputs/config-files/4/44/- -- | FileCheck %s -check-prefix=CHECK-CHILD4
 // CHECK-CHILD4: Checks: {{.*}}modernize-loop-convert,modernize-use-using,llvm-qualified-auto
-// CHECK-CHILD4: - key: llvm-qualified-auto.AddConstToQualified
-// CHECK-CHILD4-NEXT: value: 'true'
-// CHECK-CHILD4: - key: modernize-loop-convert.MaxCopySize
-// CHECK-CHILD4-NEXT: value: '20'
-// CHECK-CHILD4: - key: modernize-loop-convert.MinConfidence
-// CHECK-CHILD4-NEXT: value: reasonable
-// CHECK-CHILD4: - key: modernize-use-using.IgnoreMacros
-// CHECK-CHILD4-NEXT: value: 'false'
+// CHECK-CHILD4-DAG: - key: llvm-qualified-auto.AddConstToQualified{{ *[[:space:]] *}}value: 'true'
+// CHECK-CHILD4-DAG: - key: modernize-loop-convert.MaxCopySize{{ *[[:space:]] *}}value: '20'
+// CHECK-CHILD4-DAG: - key: modernize-loop-convert.MinConfidence{{ *[[:space:]] *}}value: reasonable
+// CHECK-CHILD4-DAG: - key: modernize-use-using.IgnoreMacros{{ *[[:space:]] *}}value: 'false'
 
 // RUN: clang-tidy --explain-config %S/Inputs/config-files/4/44/- -- | FileCheck %s -check-prefix=CHECK-EXPLAIN
 // CHECK-EXPLAIN: 'llvm-qualified-auto' is enabled in the {{.*}}{{[/\\]}}Inputs{{[/\\]}}config-files{{[/\\]}}4{{[/\\]}}44{{[/\\]}}.clang-tidy.
@@ -37,16 +33,13 @@
 // RUN: CheckOptions: [{key: modernize-loop-convert.MaxCopySize, value: 21}]}' \
 // RUN: %S/Inputs/config-files/4/44/- -- | FileCheck %s -check-prefix=CHECK-CHILD5
 // CHECK-CHILD5: Checks: {{.*}}modernize-loop-convert,modernize-use-using,llvm-qualified-auto,-llvm-qualified-auto
-// CHECK-CHILD5: - key: modernize-loop-convert.MaxCopySize
-// CHECK-CHILD5-NEXT: value: '21'
-// CHECK-CHILD5: - key: modernize-loop-convert.MinConfidence
-// CHECK-CHILD5-NEXT: value: reasonable
-// CHECK-CHILD5: - key: modernize-use-using.IgnoreMacros
-// CHECK-CHILD5-NEXT: value: 'false'
+// CHECK-CHILD5-DAG: - key: modernize-loop-convert.MaxCopySize{{ *[[:space:]] *}}value: '21'
+// CHECK-CHILD5-DAG: - key: modernize-loop-convert.MinConfidence{{ *[[:space:]] *}}value: reasonable
+// CHECK-CHILD5-DAG: - key: modernize-use-using.IgnoreMacros{{ *[[:space:]] *}}value: 'false'
 
 // RUN: clang-tidy -dump-config \
 // RUN: --config='{InheritParentConfig: false, \
 // RUN: Checks: -llvm-qualified-auto}' \
 // RUN: %S/Inputs/config-files/4/44/- -- | FileCheck %s -check-prefix=CHECK-CHILD6
-// CHECK-CHILD6: Checks: {{.*}}-llvm-qualified-auto
+// CHECK-CHILD6: Checks: {{.*-llvm-qualified-auto'? *$}}
 // CHECK-CHILD6-NOT: - key: modernize-use-using.IgnoreMacros