diff --git a/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h b/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h
--- a/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h
+++ b/clang/include/clang/Tooling/DependencyScanning/DependencyScanningTool.h
@@ -13,9 +13,8 @@
 #include "clang/Tooling/DependencyScanning/DependencyScanningWorker.h"
 #include "clang/Tooling/DependencyScanning/ModuleDepCollector.h"
 #include "clang/Tooling/JSONCompilationDatabase.h"
+#include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/MapVector.h"
-#include "llvm/ADT/StringSet.h"
-#include "llvm/ADT/StringMap.h"
 #include <optional>
 #include <string>
 #include <vector>
@@ -125,17 +124,16 @@
   llvm::Expected<TranslationUnitDeps>
   getTranslationUnitDependencies(const std::vector<std::string> &CommandLine,
                                  StringRef CWD,
-                                 const llvm::StringSet<> &AlreadySeen,
+                                 const llvm::DenseSet<ModuleID> &AlreadySeen,
                                  LookupModuleOutputCallback LookupModuleOutput);
 
   /// Given a compilation context specified via the Clang driver command-line,
   /// gather modular dependencies of module with the given name, and return the
   /// information needed for explicit build.
-  llvm::Expected<ModuleDepsGraph>
-  getModuleDependencies(StringRef ModuleName,
-                        const std::vector<std::string> &CommandLine,
-                        StringRef CWD, const llvm::StringSet<> &AlreadySeen,
-                        LookupModuleOutputCallback LookupModuleOutput);
+  llvm::Expected<ModuleDepsGraph> getModuleDependencies(
+      StringRef ModuleName, const std::vector<std::string> &CommandLine,
+      StringRef CWD, const llvm::DenseSet<ModuleID> &AlreadySeen,
+      LookupModuleOutputCallback LookupModuleOutput);
 
 private:
   DependencyScanningWorker Worker;
@@ -143,7 +141,7 @@
 
 class FullDependencyConsumer : public DependencyConsumer {
 public:
-  FullDependencyConsumer(const llvm::StringSet<> &AlreadySeen)
+  FullDependencyConsumer(const llvm::DenseSet<ModuleID> &AlreadySeen)
       : AlreadySeen(AlreadySeen) {}
 
   void handleBuildCommand(Command Cmd) override {
@@ -161,7 +159,7 @@
   }
 
   void handleModuleDependency(ModuleDeps MD) override {
-    ClangModuleDeps[MD.ID.ContextHash + MD.ID.ModuleName] = std::move(MD);
+    ClangModuleDeps[MD.ID] = std::move(MD);
   }
 
   void handleContextHash(std::string Hash) override {
@@ -174,12 +172,11 @@
 private:
   std::vector<std::string> Dependencies;
   std::vector<PrebuiltModuleDep> PrebuiltModuleDeps;
-  llvm::MapVector<std::string, ModuleDeps, llvm::StringMap<unsigned>>
-      ClangModuleDeps;
+  llvm::MapVector<ModuleID, ModuleDeps> ClangModuleDeps;
   std::vector<Command> Commands;
   std::string ContextHash;
   std::vector<std::string> OutputPaths;
-  const llvm::StringSet<> &AlreadySeen;
+  const llvm::DenseSet<ModuleID> &AlreadySeen;
 };
 
 /// A simple dependency action controller that uses a callback. If no callback
diff --git a/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h b/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h
--- a/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h
+++ b/clang/include/clang/Tooling/DependencyScanning/ModuleDepCollector.h
@@ -17,6 +17,7 @@
 #include "clang/Lex/PPCallbacks.h"
 #include "clang/Serialization/ASTReader.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/raw_ostream.h"
 #include <optional>
@@ -296,15 +297,17 @@
 } // end namespace clang
 
 namespace llvm {
+inline hash_code hash_value(const clang::tooling::dependencies::ModuleID &ID) {
+  return hash_combine(ID.ModuleName, ID.ContextHash);
+}
+
 template <> struct DenseMapInfo<clang::tooling::dependencies::ModuleID> {
   using ModuleID = clang::tooling::dependencies::ModuleID;
   static inline ModuleID getEmptyKey() { return ModuleID{"", ""}; }
   static inline ModuleID getTombstoneKey() {
     return ModuleID{"~", "~"}; // ~ is not a valid module name or context hash
   }
-  static unsigned getHashValue(const ModuleID &ID) {
-    return hash_combine(ID.ModuleName, ID.ContextHash);
-  }
+  static unsigned getHashValue(const ModuleID &ID) { return hash_value(ID); }
   static bool isEqual(const ModuleID &LHS, const ModuleID &RHS) {
     return LHS == RHS;
   }
diff --git a/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp b/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp
--- a/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp
+++ b/clang/lib/Tooling/DependencyScanning/DependencyScanningTool.cpp
@@ -145,7 +145,7 @@
 llvm::Expected<TranslationUnitDeps>
 DependencyScanningTool::getTranslationUnitDependencies(
     const std::vector<std::string> &CommandLine, StringRef CWD,
-    const llvm::StringSet<> &AlreadySeen,
+    const llvm::DenseSet<ModuleID> &AlreadySeen,
     LookupModuleOutputCallback LookupModuleOutput) {
   FullDependencyConsumer Consumer(AlreadySeen);
   CallbackActionController Controller(LookupModuleOutput);
@@ -158,7 +158,7 @@
 
 llvm::Expected<ModuleDepsGraph> DependencyScanningTool::getModuleDependencies(
     StringRef ModuleName, const std::vector<std::string> &CommandLine,
-    StringRef CWD, const llvm::StringSet<> &AlreadySeen,
+    StringRef CWD, const llvm::DenseSet<ModuleID> &AlreadySeen,
     LookupModuleOutputCallback LookupModuleOutput) {
   FullDependencyConsumer Consumer(AlreadySeen);
   CallbackActionController Controller(LookupModuleOutput);
diff --git a/clang/tools/clang-scan-deps/ClangScanDeps.cpp b/clang/tools/clang-scan-deps/ClangScanDeps.cpp
--- a/clang/tools/clang-scan-deps/ClangScanDeps.cpp
+++ b/clang/tools/clang-scan-deps/ClangScanDeps.cpp
@@ -472,8 +472,7 @@
     mutable size_t InputIndex;
 
     bool operator==(const IndexedModuleID &Other) const {
-      return std::tie(ID.ModuleName, ID.ContextHash) ==
-             std::tie(Other.ID.ModuleName, Other.ID.ContextHash);
+      return ID == Other.ID;
     }
 
     bool operator<(const IndexedModuleID &Other) const {
@@ -493,7 +492,7 @@
 
     struct Hasher {
       std::size_t operator()(const IndexedModuleID &IMID) const {
-        return llvm::hash_combine(IMID.ID.ModuleName, IMID.ID.ContextHash);
+        return llvm::hash_value(IMID.ID);
       }
     };
   };
@@ -880,7 +879,7 @@
 
   for (unsigned I = 0; I < Pool.getThreadCount(); ++I) {
     Pool.async([&, I]() {
-      llvm::StringSet<> AlreadySeenModules;
+      llvm::DenseSet<ModuleID> AlreadySeenModules;
       while (auto MaybeInputIndex = GetNextInputIndex()) {
         size_t LocalIndex = *MaybeInputIndex;
         const tooling::CompileCommand *Input = &Inputs[LocalIndex];