diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
index ba21a14..cb9ae97 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/CompactPersistentActionCache.java
@@ -85,7 +85,7 @@
     private final PersistentStringIndexer indexer;
     private long nextUpdateSecs;
 
-    public ActionMap(
+    ActionMap(
         ConcurrentMap<Integer, byte[]> map,
         PersistentStringIndexer indexer,
         Clock clock,
@@ -346,8 +346,8 @@
   @Override
   @Nullable
   public ActionCache.Entry get(String key) {
-    int index = indexer.getIndex(key);
-    if (index < 0) {
+    Integer index = indexer.getIndex(key);
+    if (index == null) {
       return null;
     }
     byte[] data = map.get(index);
@@ -366,7 +366,7 @@
   @Override
   public void put(String key, ActionCache.Entry entry) {
     // Encode record. Note that both methods may create new mappings in the indexer.
-    int index = indexer.getOrCreateIndex(key);
+    Integer index = indexer.getOrCreateIndex(key);
     byte[] content;
     try {
       content = encode(indexer, entry);
@@ -391,7 +391,10 @@
 
   @Override
   public void remove(String key) {
-    map.remove(indexer.getIndex(key));
+    Integer index = indexer.getIndex(key);
+    if (index != null) {
+      map.remove(index);
+    }
   }
 
   @Override
@@ -652,7 +655,7 @@
   }
 
   private static String getStringForIndex(StringIndexer indexer, int index) throws IOException {
-    String path = (index >= 0 ? indexer.getStringForIndex(index) : null);
+    String path = index >= 0 ? indexer.getStringForIndex(index) : null;
     if (path == null) {
       throw new IOException("Corrupted string index");
     }
diff --git a/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java b/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java
index 18a401e..58040cf 100644
--- a/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java
+++ b/src/main/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexer.java
@@ -42,7 +42,6 @@
 @ConditionallyThreadSafe // Each instance must be instantiated with a different dataPath.
 final class PersistentStringIndexer implements StringIndexer {
 
-  private static final int NOT_FOUND = -1;
   private static final int INITIAL_ENTRIES = 10000;
 
   /** Instantiates and loads instance of the persistent string indexer. */
@@ -84,35 +83,35 @@
   }
 
   @Override
-  public int getOrCreateIndex(String s) {
+  public Integer getOrCreateIndex(String s) {
     Integer i = stringToInt.get(s);
-    if (i == null) {
-      s = StringCanonicalizer.intern(s);
-      synchronized (this) {
-        // First, make sure another thread hasn't just added the entry:
-        i = stringToInt.get(s);
-        if (i != null) {
-          return i;
-        }
-
-        int ind = intToString.size();
-        stringToInt.put(s, ind);
-        intToString.put(ind, s);
-        return ind;
+    if (i != null) {
+      return i;
+    }
+    s = StringCanonicalizer.intern(s);
+    synchronized (this) {
+      // First, make sure another thread hasn't just added the entry.
+      i = stringToInt.get(s);
+      if (i != null) {
+        return i;
       }
-    } else {
+
+      i = intToString.size();
+      stringToInt.put(s, i);
+      intToString.put(i, s);
       return i;
     }
   }
 
   @Override
-  public int getIndex(String s) {
-    return stringToInt.getOrDefault(s, NOT_FOUND);
+  @Nullable
+  public Integer getIndex(String s) {
+    return stringToInt.get(s);
   }
 
   @Override
   @Nullable
-  public String getStringForIndex(int i) {
+  public String getStringForIndex(Integer i) {
     return intToString.get(i);
   }
 
diff --git a/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java b/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
index 28a4f39..e6d992f0 100644
--- a/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
+++ b/src/main/java/com/google/devtools/build/lib/util/StringIndexer.java
@@ -15,7 +15,13 @@
 
 import javax.annotation.Nullable;
 
-/** Provides bidirectional string ⇔ unique integer mapping. */
+/**
+ * Provides bidirectional {@link String} ⇔ unique {@link Integer} mapping.
+ *
+ * <p>{@link Integer} is used in place of primitive {@code int} as it is assumed that indices will
+ * be stored in maps. Passing {@link Integer} across API boundaries makes it less likely to store
+ * duplicate instances and create garbage due to autoboxing.
+ */
 public interface StringIndexer {
 
   /** Removes all mappings. */
@@ -24,21 +30,19 @@
   /** Returns the number of strings in the index. */
   int size();
 
-  /**
-   * Creates new mapping for the given string if necessary and returns string index. Also, as a side
-   * effect, additional mappings may be created for various prefixes of the given string.
-   */
-  int getOrCreateIndex(String s);
+  /** Creates new mapping for the given string if necessary and returns string index. */
+  Integer getOrCreateIndex(String s);
 
   /**
    * Returns the unique index for the given string if one was created via {@link #getOrCreateIndex},
-   * or else {@code -1}.
+   * or else {@code null}.
    */
-  int getIndex(String s);
+  @Nullable
+  Integer getIndex(String s);
 
   /**
    * Returns the string associated with the given index or {@code null} if it is not in the index.
    */
   @Nullable
-  String getStringForIndex(int i);
+  String getStringForIndex(Integer i);
 }
diff --git a/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java b/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java
index 6876590..0d2f486 100644
--- a/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java
+++ b/src/test/java/com/google/devtools/build/lib/actions/cache/PersistentStringIndexerTest.java
@@ -35,22 +35,22 @@
 import org.junit.runner.RunWith;
 import org.junit.runners.JUnit4;
 
-/**
- * Test for the PersistentStringIndexer class.
- */
+/** Tests for {@link PersistentStringIndexer}. */
 @RunWith(JUnit4.class)
-public class PersistentStringIndexerTest {
+public final class PersistentStringIndexerTest {
 
   private static class ManualClock implements Clock {
     private long currentTime = 0L;
 
-    ManualClock() { }
+    ManualClock() {}
 
-    @Override public long currentTimeMillis() {
+    @Override
+    public long currentTimeMillis() {
       throw new AssertionError("unexpected method call");
     }
 
-    @Override  public long nanoTime() {
+    @Override
+    public long nanoTime() {
       return currentTime;
     }
 
@@ -59,40 +59,37 @@
     }
   }
 
-  private PersistentStringIndexer psi;
-  private Map<Integer, String> mappings = new ConcurrentHashMap<>();
-  private Scratch scratch = new Scratch();
-  private ManualClock clock = new ManualClock();
-  private Path dataPath;
-  private Path journalPath;
+  private final Map<Integer, String> mappings = new ConcurrentHashMap<>();
+  private final Scratch scratch = new Scratch();
+  private final ManualClock clock = new ManualClock();
+  private final Path dataPath = scratch.resolve("/cache/test.dat");
+  private final Path journalPath = scratch.resolve("/cache/test.journal");
 
+  private PersistentStringIndexer indexer;
 
   @Before
-  public final void createIndexer() throws Exception  {
-    dataPath = scratch.resolve("/cache/test.dat");
-    journalPath = scratch.resolve("/cache/test.journal");
-    psi = PersistentStringIndexer.create(dataPath, clock);
+  public void createIndexer() throws Exception {
+    indexer = PersistentStringIndexer.create(dataPath, clock);
   }
 
   private void assertSize(int expected) {
-    assertThat(psi.size()).isEqualTo(expected);
+    assertThat(indexer.size()).isEqualTo(expected);
   }
 
   private void assertIndex(int expected, String s) {
-    int index = psi.getOrCreateIndex(s);
+    int index = indexer.getOrCreateIndex(s);
     assertThat(index).isEqualTo(expected);
     mappings.put(expected, s);
   }
 
   private void assertContent() {
-    for (int i = 0; i < psi.size(); i++) {
-      if(mappings.get(i) != null) {
-        assertThat(mappings).containsEntry(i, psi.getStringForIndex(i));
+    for (int i = 0; i < indexer.size(); i++) {
+      if (mappings.get(i) != null) {
+        assertThat(mappings).containsEntry(i, indexer.getStringForIndex(i));
       }
     }
   }
 
-
   private void setupTestContent() {
     assertSize(0);
     assertIndex(0, "abcdefghi");  // Create leafs
@@ -111,13 +108,12 @@
   }
 
   /**
-   * Writes lots of entries with labels "fooconcurrent[int]" at the same time.
-   * The set of labels written is deterministic, but the label:index mapping is
-   * not.
+   * Writes lots of entries with labels "fooconcurrent[int]" at the same time. The set of labels
+   * written is deterministic, but the label:index mapping is not.
    */
-  private void writeLotsOfEntriesConcurrently(final int numToWrite) throws InterruptedException {
-    final int NUM_THREADS = 10;
-    final CountDownLatch synchronizerLatch = new CountDownLatch(NUM_THREADS);
+  private void writeLotsOfEntriesConcurrently(int numToWrite) throws InterruptedException {
+    int numThreads = 10;
+    CountDownLatch synchronizerLatch = new CountDownLatch(numThreads);
 
     TestRunnable indexAdder =
         () -> {
@@ -126,12 +122,12 @@
             synchronizerLatch.await();
 
             String value = "fooconcurrent" + i;
-            mappings.put(psi.getOrCreateIndex(value), value);
+            mappings.put(indexer.getOrCreateIndex(value), value);
           }
         };
 
     Collection<TestThread> threads = new ArrayList<>();
-    for (int i = 0; i < NUM_THREADS; i++) {
+    for (int i = 0; i < numThreads; i++) {
       TestThread thread = new TestThread(indexAdder);
       thread.start();
       threads.add(thread);
@@ -143,6 +139,21 @@
   }
 
   @Test
+  public void returnsSameIntegerInstance() {
+    int n = 1000; // Greater than the default java.lang.Integer.IntegerCache.high of 127.
+    for (int i = 0; i < n; i++) {
+      String s = "a".repeat(i);
+      Integer index = indexer.getOrCreateIndex(s);
+      assertThat(indexer.getIndex(s)).isSameInstanceAs(index);
+    }
+  }
+
+  @Test
+  public void unindexedStringReturnsNull() {
+    assertThat(indexer.getIndex("absent")).isNull();
+  }
+
+  @Test
   public void testNormalOperation() throws Exception {
     assertThat(dataPath.exists()).isFalse();
     assertThat(journalPath.exists()).isFalse();
@@ -155,12 +166,12 @@
     assertThat(dataPath.exists()).isFalse();
     assertThat(journalPath.exists()).isTrue();
 
-    psi.save(); // Successful save will remove journal file.
+    indexer.save(); // Successful save will remove journal file.
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
 
     // Now restore data from file and verify it.
-    psi = PersistentStringIndexer.create(dataPath, clock);
+    indexer = PersistentStringIndexer.create(dataPath, clock);
     assertThat(journalPath.exists()).isFalse();
     clock.advance(4);
     assertSize(10);
@@ -182,7 +193,7 @@
     assertThat(journalPath.exists()).isTrue();
 
     // Now restore data from file and verify it. All data should be restored from journal;
-    psi = PersistentStringIndexer.create(dataPath, clock);
+    indexer = PersistentStringIndexer.create(dataPath, clock);
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
     clock.advance(4);
@@ -196,7 +207,7 @@
     assertThat(dataPath.exists()).isFalse();
     assertThat(journalPath.exists()).isFalse();
     setupTestContent();
-    psi.save();
+    indexer.save();
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
     long oldDataFileLen = dataPath.getFileSize();
@@ -208,7 +219,7 @@
     assertThat(journalPath.exists()).isTrue();
 
     // Now restore data from file and verify it. All data should be restored from journal;
-    psi = PersistentStringIndexer.create(dataPath, clock);
+    indexer = PersistentStringIndexer.create(dataPath, clock);
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
     assertThat(dataPath.getFileSize())
@@ -224,12 +235,12 @@
     assertThat(dataPath.exists()).isFalse();
     assertThat(journalPath.exists()).isFalse();
     setupTestContent();
-    psi.save();
+    indexer.save();
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
     long oldDataFileLen = dataPath.getFileSize();
 
-    int size = psi.size();
+    int size = indexer.size();
     int numToWrite = 50000;
     writeLotsOfEntriesConcurrently(numToWrite);
     assertThat(journalPath.exists()).isFalse();
@@ -240,7 +251,7 @@
     assertThat(journalPath.exists()).isTrue();
 
     // Now restore data from file and verify it. All data should be restored from journal;
-    psi = PersistentStringIndexer.create(dataPath, clock);
+    indexer = PersistentStringIndexer.create(dataPath, clock);
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
     assertThat(dataPath.getFileSize())
@@ -257,7 +268,7 @@
     FileSystemUtils.writeContentAsLatin1(journalPath, "bogus content");
     IOException e =
         assertThrows(
-            IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+            IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
     assertThat(e).hasMessageThat().contains("too short: Only 13 bytes");
 
     journalPath.delete();
@@ -273,30 +284,32 @@
     byte[] journalContent = FileSystemUtils.readContent(journalPath);
 
     // Now restore data from file and verify it. All data should be restored from journal;
-    psi = PersistentStringIndexer.create(dataPath, clock);
+    indexer = PersistentStringIndexer.create(dataPath, clock);
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
 
     // Now put back truncated journal. We should get an error.
     assertThat(dataPath.delete()).isTrue();
-    FileSystemUtils.writeContent(journalPath,
-        Arrays.copyOf(journalContent, journalContent.length - 1));
-    assertThrows(EOFException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+    FileSystemUtils.writeContent(
+        journalPath, Arrays.copyOf(journalContent, journalContent.length - 1));
+    assertThrows(
+        EOFException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
 
     // Corrupt the journal with a negative size value.
     byte[] journalCopy = journalContent.clone();
     // Flip this bit to make the key size negative.
     journalCopy[95] = -2;
-    FileSystemUtils.writeContent(journalPath,  journalCopy);
+    FileSystemUtils.writeContent(journalPath, journalCopy);
     e =
         assertThrows(
-            IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+            IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
     assertThat(e).hasMessageThat().contains("corrupt key length");
 
     // Now put back corrupted journal. We should get an error.
     journalContent[journalContent.length - 13] = 100;
-    FileSystemUtils.writeContent(journalPath,  journalContent);
-    assertThrows(IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+    FileSystemUtils.writeContent(journalPath, journalContent);
+    assertThrows(
+        IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
   }
 
   @Test
@@ -306,7 +319,7 @@
     assertThat(journalPath.exists()).isFalse();
 
     assertIndex(9, "abc1234"); // This should flush journal to disk.
-    psi.save();
+    indexer.save();
     assertThat(dataPath.exists()).isTrue();
     assertThat(journalPath.exists()).isFalse();
 
@@ -331,7 +344,7 @@
 
     IOException e =
         assertThrows(
-            IOException.class, () -> psi = PersistentStringIndexer.create(dataPath, clock));
+            IOException.class, () -> indexer = PersistentStringIndexer.create(dataPath, clock));
     assertThat(e).hasMessageThat().contains("Corrupted filename index has duplicate entry");
   }
 
@@ -353,7 +366,7 @@
     // Subsequent updates should succeed even though journaling is disabled at this point.
     clock.advance(4);
     assertIndex(10, "another record");
-    IOException e = assertThrows(IOException.class, () -> psi.save());
+    IOException e = assertThrows(IOException.class, () -> indexer.save());
     assertThat(e).hasMessageThat().contains(journalPath.getPathString() + " (Is a directory)");
   }
 }