diff --git a/tools/gn/builder.h b/tools/gn/builder.h
index c8b54c9..573d8ed 100644
--- a/tools/gn/builder.h
+++ b/tools/gn/builder.h
@@ -5,8 +5,9 @@
 #ifndef TOOLS_GN_BUILDER_H_
 #define TOOLS_GN_BUILDER_H_
 
+#include <map>
+
 #include "base/callback.h"
-#include "base/containers/hash_tables.h"
 #include "base/macros.h"
 #include "tools/gn/builder_record.h"
 #include "tools/gn/label.h"
@@ -130,7 +131,7 @@
   Loader* loader_;
 
   // Owning pointers.
-  typedef base::hash_map<Label, BuilderRecord*> RecordMap;
+  typedef std::map<Label, BuilderRecord*> RecordMap;
   RecordMap records_;
 
   ResolvedGeneratedCallback resolved_and_generated_callback_;
diff --git a/tools/gn/ninja_build_writer.cc b/tools/gn/ninja_build_writer.cc
index a0dd8ce..a805bb9 100644
--- a/tools/gn/ninja_build_writer.cc
+++ b/tools/gn/ninja_build_writer.cc
@@ -134,7 +134,8 @@
 
 NinjaBuildWriter::NinjaBuildWriter(
     const BuildSettings* build_settings,
-    const std::map<const Settings*, const Toolchain*>& used_toolchains,
+    const std::unordered_map<const Settings*, const Toolchain*>&
+        used_toolchains,
     const Toolchain* default_toolchain,
     const std::vector<const Target*>& default_toolchain_targets,
     std::ostream& out,
@@ -167,7 +168,7 @@
   ScopedTrace trace(TraceItem::TRACE_FILE_WRITE, "build.ninja");
 
   std::vector<const Target*> all_targets = builder.GetAllResolvedTargets();
-  std::map<const Settings*, const Toolchain*> used_toolchains;
+  std::unordered_map<const Settings*, const Toolchain*> used_toolchains;
 
   // Find the default toolchain info.
   Label default_toolchain_label = builder.loader()->GetDefaultToolchain();
@@ -260,7 +261,7 @@
 
 void NinjaBuildWriter::WriteAllPools() {
   // Compute the pools referenced by all tools of all used toolchains.
-  std::set<const Pool*> used_pools;
+  std::unordered_set<const Pool*> used_pools;
   for (const auto& pair : used_toolchains_) {
     for (int j = Toolchain::TYPE_NONE + 1; j < Toolchain::TYPE_NUMTYPES; j++) {
       Toolchain::ToolType tool_type = static_cast<Toolchain::ToolType>(j);
@@ -270,16 +271,38 @@
     }
   }
 
-  for (const Pool* pool : used_pools) {
-    std::string pool_name = pool->GetNinjaName(default_toolchain_->label());
-    out_ << "pool " << pool_name << std::endl
+  // Write pools sorted by their name, to make output deterministic.
+  std::vector<const Pool*> sorted_pools(used_pools.begin(), used_pools.end());
+  auto pool_name = [this](const Pool* pool) {
+    return pool->GetNinjaName(default_toolchain_->label());
+  };
+  std::sort(sorted_pools.begin(), sorted_pools.end(),
+            [&pool_name](const Pool* a, const Pool* b) {
+              return pool_name(a) < pool_name(b);
+            });
+  for (const Pool* pool : sorted_pools) {
+    out_ << "pool " << pool_name(pool) << std::endl
          << "  depth = " << pool->depth() << std::endl
          << std::endl;
   }
 }
 
 void NinjaBuildWriter::WriteSubninjas() {
-  for (const auto& pair : used_toolchains_) {
+  // Write toolchains sorted by their name, to make output deterministic.
+  std::vector<std::pair<const Settings*, const Toolchain*>> sorted_settings(
+      used_toolchains_.begin(), used_toolchains_.end());
+  std::sort(sorted_settings.begin(), sorted_settings.end(),
+            [this](const std::pair<const Settings*, const Toolchain*>& a,
+                   const std::pair<const Settings*, const Toolchain*>& b) {
+              // Always put the default toolchain first.
+              if (b.second == default_toolchain_)
+                return false;
+              if (a.second == default_toolchain_)
+                return true;
+              return GetNinjaFileForToolchain(a.first) <
+                     GetNinjaFileForToolchain(b.first);
+            });
+  for (const auto& pair : sorted_settings) {
     out_ << "subninja ";
     path_output_.WriteFile(out_, GetNinjaFileForToolchain(pair.first));
     out_ << std::endl;
diff --git a/tools/gn/ninja_build_writer.h b/tools/gn/ninja_build_writer.h
index cf72852..530ac71 100644
--- a/tools/gn/ninja_build_writer.h
+++ b/tools/gn/ninja_build_writer.h
@@ -25,13 +25,13 @@
 // build itself.
 class NinjaBuildWriter {
  public:
-  NinjaBuildWriter(
-      const BuildSettings* settings,
-      const std::map<const Settings*, const Toolchain*>& used_toolchains,
-      const Toolchain* default_toolchain,
-      const std::vector<const Target*>& default_toolchain_targets,
-      std::ostream& out,
-      std::ostream& dep_out);
+  NinjaBuildWriter(const BuildSettings* settings,
+                   const std::unordered_map<const Settings*, const Toolchain*>&
+                       used_toolchains,
+                   const Toolchain* default_toolchain,
+                   const std::vector<const Target*>& default_toolchain_targets,
+                   std::ostream& out,
+                   std::ostream& dep_out);
   ~NinjaBuildWriter();
 
   // The design of this class is that this static factory function takes the
@@ -57,7 +57,7 @@
 
   const BuildSettings* build_settings_;
 
-  const std::map<const Settings*, const Toolchain*>& used_toolchains_;
+  const std::unordered_map<const Settings*, const Toolchain*>& used_toolchains_;
   const Toolchain* default_toolchain_;
   const std::vector<const Target*>& default_toolchain_targets_;
 
diff --git a/tools/gn/ninja_build_writer_unittest.cc b/tools/gn/ninja_build_writer_unittest.cc
index 9fee37a..9885231 100644
--- a/tools/gn/ninja_build_writer_unittest.cc
+++ b/tools/gn/ninja_build_writer_unittest.cc
@@ -48,7 +48,7 @@
   Settings other_settings(setup.build_settings(), "toolchain/");
   other_settings.set_toolchain_label(other_toolchain_label);
 
-  std::map<const Settings*, const Toolchain*> used_toolchains;
+  std::unordered_map<const Settings*, const Toolchain*> used_toolchains;
   used_toolchains[setup.settings()] = setup.toolchain();
   used_toolchains[&other_settings] = &other_toolchain;
 
@@ -117,7 +117,7 @@
   target_bar.SetToolchain(setup.toolchain());
   ASSERT_TRUE(target_bar.OnResolved(&err));
 
-  std::map<const Settings*, const Toolchain*> used_toolchains;
+  std::unordered_map<const Settings*, const Toolchain*> used_toolchains;
   used_toolchains[setup.settings()] = setup.toolchain();
   std::vector<const Target*> targets = { &target_foo, &target_bar };
   std::ostringstream ninja_out;