diff --git a/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java b/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java
index 3340e46..adecc39 100644
--- a/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java
+++ b/src/main/java/com/android/tools/r8/synthesis/SyntheticClassBuilder.java
@@ -26,6 +26,8 @@
 import com.android.tools.r8.origin.Origin;
 import com.android.tools.r8.synthesis.SyntheticNaming.SyntheticKind;
 import com.android.tools.r8.utils.ReachabilitySensitiveValue;
+import com.android.tools.r8.utils.structural.HasherWrapper;
+import com.android.tools.r8.utils.structural.StructuralItem;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
@@ -186,11 +188,6 @@
         directMethods.add(method);
       }
     }
-    long checksum =
-        7 * (long) directMethods.hashCode()
-            + 11 * (long) virtualMethods.hashCode()
-            + 13 * (long) staticFields.hashCode()
-            + 17 * (long) instanceFields.hashCode();
     C clazz =
         getClassKind()
             .create(
@@ -214,7 +211,7 @@
                 DexEncodedMethod.EMPTY_ARRAY,
                 DexEncodedMethod.EMPTY_ARRAY,
                 factory.getSkipNameValidationForTesting(),
-                c -> checksum,
+                c -> getChecksum(),
                 null,
                 ReachabilitySensitiveValue.DISABLED);
     if (useSortedMethodBacking) {
@@ -224,4 +221,17 @@
     clazz.setVirtualMethods(virtualMethods.toArray(DexEncodedMethod.EMPTY_ARRAY));
     return clazz;
   }
+
+  private long getChecksum() {
+    return 7 * hashEntries(virtualMethods, directMethods)
+        + 13 * hashEntries(instanceFields, staticFields);
+  }
+
+  private <S extends StructuralItem<S>> long hashEntries(List<S>... entryLists) {
+    HasherWrapper hasherWrapper = HasherWrapper.murmur3128Hasher();
+    for (List<S> entryList : entryLists) {
+      entryList.stream().sorted().forEach(e -> e.hash(hasherWrapper));
+    }
+    return hasherWrapper.hash().hashCode();
+  }
 }
diff --git a/src/test/bootstrap/com/android/tools/r8/bootstrap/BootstrapDeterminismTest.java b/src/test/bootstrap/com/android/tools/r8/bootstrap/BootstrapDeterminismTest.java
index 6afaa95..1ba438d 100644
--- a/src/test/bootstrap/com/android/tools/r8/bootstrap/BootstrapDeterminismTest.java
+++ b/src/test/bootstrap/com/android/tools/r8/bootstrap/BootstrapDeterminismTest.java
@@ -6,6 +6,7 @@
 import static org.junit.Assert.assertTrue;
 
 import com.android.tools.r8.ClassFileConsumer;
+import com.android.tools.r8.DexIndexedConsumer.ArchiveConsumer;
 import com.android.tools.r8.JdkClassFileProvider;
 import com.android.tools.r8.TestBase;
 import com.android.tools.r8.TestParameters;
@@ -51,6 +52,18 @@
     assertTrue(Files.exists(logDirectory.resolve("0.log")));
   }
 
+  @Test
+  public void testD8DeterminismWithChecksums() throws Exception {
+    Path logDirectory = temp.newFolder().toPath();
+    Path ref = compileD8WithChecksums(1, logDirectory);
+    for (int i = 2; i <= ITERATIONS; i++) {
+      Path next = compileD8WithChecksums(i, logDirectory);
+      assertProgramsEqual(ref, next);
+    }
+    // Check that setting the determinism checker wrote a log file.
+    assertTrue(Files.exists(logDirectory.resolve("0.log")));
+  }
+
   private Path compile(int iteration, Path logDirectory) throws Exception {
     System.out.println("= compiling " + iteration + "/" + ITERATIONS + " ======================");
     Path out = temp.newFolder().toPath().resolve("out.jar");
@@ -71,4 +84,25 @@
         .compile();
     return out;
   }
+
+  private Path compileD8WithChecksums(int iteration, Path logDirectory) throws Exception {
+    System.out.println("= compiling d8 " + iteration + "/" + ITERATIONS + " =====================");
+    Path out = temp.newFolder().toPath().resolve("out.jar");
+    testForD8(Backend.DEX)
+        .addProgramFiles(ToolHelper.getR8WithRelocatedDeps())
+        .addLibraryProvider(JdkClassFileProvider.fromSystemJdk())
+        .addOptionsModification(
+            options -> {
+              options
+                  .getTestingOptions()
+                  .setDeterminismChecker(DeterminismChecker.createWithFileBacking(logDirectory));
+              // Ensure that we generate the same check sums, see b/359616078
+              options.encodeChecksums = true;
+            })
+        .allowStdoutMessages()
+        .allowStderrMessages()
+        .setProgramConsumer(new ArchiveConsumer(out))
+        .compile();
+    return out;
+  }
 }