This is kind of a nit-picky thing, and I wouldn't bring it up normally because you are like a superhero when it comes to Java, but seriously this isn't going to make much of a difference really, it's more of a preference thing

/**
 * Identify whether an index is mapped to a key.
 * 
 * @param index
 *            the index to check the mapping for.
 * @return true if the key was previously mapped.
 */
public boolean containsIndex(final int index) {
    if (index < 0 || index >= size) {
        return false;
    }
    if (deletedCount > 0 && Arrays.stream(deletedIndices, 0, deletedCount).anyMatch(i -> i == index)) {
        return false;
    }
    return true;
}

You could do 2 things here

1. Merge the conditions into a single if statement
2. Make the second if statement an else if statement

The first option is going to make the condition really cluttered and give it 2 extra sets of parenthesis. Personally I would go with the second option, it shows continuity in the flow of the method.

if (A || B) then 
    do Z
else if (X && Y) then
    do Z

If the conditions were this simple I would go with option 1 though

if ((A || B ) || (X && Y)) then
    do Z

but the conditions are a little more complex and make for a long condition statement, but this is really an else if situation.

more nit-picky stuff.

private boolean same(final IntKeyIndex them, final int index) {
    final int k = keys.get(index);
    int t = them.getIndex(k);
    if (t != index) {
        return false;
    }
    return true;
}

I would think that you would just want to drop the if statement and return the boolean

return t == index;