Mapping arbitrary Int values to a linear index space

Question

This is part of a growing "primitive" tools collection here on github, and is the initial use-case for the IntArray for review here.

Often, when processing data, you encounter unique values that you need to use as keys in a lookup system. These keys could be anything from IP addresses, times, identifiers, etc. A standard operation would be to have a Map<Integer,....>.

What would be really nice is a Map<int,int> concept that kept the data as primitives, and used basic array systems to do the association between the key and value.

This question is a review for a class IntKeyIndex that does half of that, using the IntArray, and also a relatively traditional int array based hash-table.

The purpose of IntKeyIndex is to map an arbitrary int key value to an index in an array, and to allow the index in the array to be referenced back to the key it belongs to. Since arrays are indexed from index 0, it makes sense that the first key registered, perhaps the key value 5987682 is given the index 0, and the next key registered, perhaps -7799243 is given the index 1, and so on. Each time we subsequently ask for the index for key -7799243 it will always give back the index 1. Each time we ask for the key associated with index 1, it will give back -7799243.

IntKeyIndex performs this operation, and it additionally allows key values to be 'removed' from the mapping, which frees up the index which was asccociated with it, and they can subsequently be reused.

Conceptually, the IntKeyIndex class maps a wide range of arbitrary key values (from Integer.MIN_VALUE to Integer.MAX_VALUE inclusive) to a linear address space (from 0 to n-1), and also maps the address space back to the respective keys.

Major features of the class are:

1. it uses a hash system on the key which allows hash buckets to be re-hashed very fast, when the hash table becomes inefficient.
2. when adding a key, it hashes it, and buckets it. If this is the first time the value is indexed, it uses the next spot in the IntArray, and adds that index to the hash table.
3. it uses the IntArray to store the key, and the index of the key in the IntArray is index that the instance reports as the index for the key. There are only two int values stored per key, the key is stored in the IntArray, and the index is stored in the hash table.
4. it has a stream API that allows the keys, and indexes to be streamed in a parallel stream, if needed.

For Review

I am particularly interested in reviews of the IntKeyIndex with a focus on:

1. performance
2. memory efficiency
3. unexpected edge cases which may cause failures.
4. general usability

IntKIntV

Occasionally, it is useful to get an instance out that contains the actual key/index mapping in one place. A class is used to report this (but not to store it in the index):

package net.tuis.primutils;

/**
 * Simple container class containing a key/value mapping.
 * 
 * @author rolf
 *
 */
public class IntKIntVEntry {

    private final int key, value;

    /**
     * Create the container containing the key/value mapping.
     * @param key the key
     * @param value the value
     */
    public IntKIntVEntry(int key, int value) {
        super();
        this.key = key;
        this.value = value;
    }

    /**
     * Retrieve the mapped key
     * @return the key
     */
    public int getKey() {
        return key;
    }

    /**
     * Retrieve the value.
     * @return the value.
     */
    public int getValue() {
        return value;
    }

    @Override
    public int hashCode() {
        return Integer.rotateLeft(key, 13) ^ value;
    }

    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof IntKIntVEntry)) {
            return false;
        }
        if (obj == this) {
            return true;
        }
        return key == ((IntKIntVEntry)obj).key && value ==((IntKIntVEntry)obj).value;
    }

    @Override
    public String toString() {
        return String.format("(%d -> %d)", key, value);
    }

}

IntKeyIndex

package net.tuis.primutils;

import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Spliterator;
import java.util.Spliterators;
import java.util.function.Consumer;
import java.util.function.IntConsumer;
import java.util.stream.IntStream;
import java.util.stream.Stream;
import java.util.stream.StreamSupport;

import static net.tuis.primutils.ArrayOps.*;

/**
 * Relate unique key values to an int index.
 * <p>
 * The first added key will be index 0, and so on. The order and value of the
 * keys is arbitrary, and can be any value from Integer.MIN_VALUE to
 * Integer.MAX_VALUE inclusive. There is a hard limit of at most
 * Integer.MAX_VALUE key mappings though. Further, there is no guarantee on the
 * order of keys returned in any streams or other multi-value return structures.
 * While the value and order of the keys is arbitrary, the sequence of any index
 * values returned by the {@link #add(int)} method is not. The system has the
 * following guarantees:
 * <ol>
 * <li>index values will always start from 0
 * <li>adding new values will always return a value 1 larger than the previous
 * add, unless there are deleted keys.
 * <li>deleting a key will create a 'hole' in the index sequence
 * <li>adding a new key when there are currently 'holes' in the index sequence
 * (after a delete), will reuse one of the previously deleted indexes.
 * <li>as a consequence, there is no guarantee that index values will be
 * strictly sequential, but that no two keys will ever return the same index
 * value
 * </ol>
 * <p>
 * Memory footprint overhead is relatively small for instances of the
 * IntKeyIndex class. There is a requirement for an indexing system and a key
 * storage system. These storage systems have an initial space allocated for
 * each instance. An empty, minimal instance will consume in the order of 4KB,
 * but, that same instance, with millions of entries will have less than 1% of
 * overhead wasted. What this means is that the system, like many other
 * collections, is not useful for many (thousands of) small instances. On the
 * other hand, a few small instances are fine, and a few huge instances are
 * great.
 * <p>
 * In addition to an int[] array for each of the keys, there is an int[]-based
 * array structure used to hash-index the location of the keys too. In other
 * words, there are two int values stored for each key indexed, and a very small
 * overhead after that. there's another array cell in an indexing system.
 * <p>
 * The memory used by this class, then, is about 2 ints per entry * 4 bytes per
 * int, a 1000 member map will use 8000 bytes. Compare that with a
 * Map&lt;Integer,Integer&gt; which would consume about....100 bytes per entry.
 * <p>
 * Due to odd Java implementations, you cannot create arrays with as many as
 * Integer.MAX_VALUE entries, but this class, can support up to that amount.
 * 
 * @author rolf
 *
 */
public final class IntKeyIndex {

    private static final int IDEAL_BUCKET_SIZE = 64;
    private static final int INITIAL_BUCKET_SIZE = 8;
    private static final int MIN_BUCKET_COUNT = 16;

    private int[][] bucketData;
    private int[] bucketSize;
    private int size;
    private int mask;
    private int[] deletedIndices = null;
    private int deletedCount = 0;
    private int modCount = 0;

    private final IntArray keys = new IntArray();

    /**
     * Create an IntKeyMap with the specified initial capacity.
     * 
     * @param capacity
     *            the initial capacity to budget for.
     */
    public IntKeyIndex(final int capacity) {

        int nxtp2 = nextPowerOf2(capacity / IDEAL_BUCKET_SIZE);
        int bCount = Math.max(MIN_BUCKET_COUNT, nxtp2);
        bucketData = new int[bCount][];
        bucketSize = new int[bCount];
        mask = bCount - 1;
    }

    /**
     * Get the number of key/value pairs that are stored in this Map
     * 
     * @return the Map size
     */
    public int size() {
        return size - deletedCount;
    }

    /**
     * Determine whether there are any mappings in the Map
     * 
     * @return true if there are no mappings.
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Identify whether a key is mapped to a value.
     * 
     * @param key
     *            the key to check the mapping for.
     * @return true if the key was previously mapped.
     */
    public boolean containsKey(final int key) {
        return getIndex(key) >= 0;
    }

    /**
     * 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;
    }

    /**
     * Include a key in to the Map
     * 
     * @param key
     *            the key to add
     * @return the existing index associated with the key, or the new key in an
     *         insertion-point form (- key - 1)
     */
    public int add(final int key) {
        final int bucket = bucketId(key);
        final int bucketPos = locate(bucketData[bucket], bucketSize[bucket], key);
        if (bucketPos >= 0) {
            // existing index
            return bucketData[bucket][bucketPos];
        }
        // only changes to the actual key values make a difference on the
        // iteration.
        // addKeyValue is the only place where max size is actually checked.
        int keyIndex = addKeyValue(key);
        modCount++;
        insertBucketIndex(bucket, -bucketPos - 1, keyIndex);
        return -keyIndex - 1;
    }

    /**
     * Return the index associated with the specified key (if any).
     * 
     * @param key
     *            the key to get the value for.
     * @return the index associated with the key, or -1 if the key is not
     *         mapped.
     */
    public int getIndex(final int key) {
        final int bucket = bucketId(key);
        final int pos = locate(bucketData[bucket], bucketSize[bucket], key);
        return pos < 0 ? -1 : bucketData[bucket][pos];
    }

    /**
     * Return the key value that maps to the specified index, if any.
     * 
     * @param index
     *            The index to lookup
     * @param notThere
     *            the value to return if the index is not associated to a key.
     * @return the key mapping to this index, or notThere if the index is not
     *         associated. Use {@link #containsIndex(int)} to check.
     */
    public int getKey(final int index, final int notThere) {
        return containsIndex(index) ? keys.get(index) : notThere;
    }

    /**
     * Remove a key mapping from the map, if it exists.
     * 
     * @param key
     *            the key to remove
     * @return the index previously associated with the key, or -1 if the key is
     *         not mapped.
     */
    public int remove(final int key) {
        final int bucket = bucketId(key);
        final int pos = locate(bucketData[bucket], bucketSize[bucket], key);
        if (pos < 0) {
            return -1;
        }
        // only changes to the actual key values make a difference on the
        // iteration.
        modCount++;
        final int index = bucketData[bucket][pos];
        deleteIndex(index);
        bucketSize[bucket]--;
        System.arraycopy(bucketData[bucket], pos + 1, bucketData[bucket], pos, bucketSize[bucket] - pos);
        return index;
    }

    /**
     * Remove all key/value mappings from the Map. Capacity and other space
     * reservations will not be affected.
     */
    public void clear() {
        if (size == 0) {
            return;
        }
        modCount++;
        Arrays.fill(bucketSize, 0);
        size = 0;
        deletedCount = 0;
    }

    /**
     * Get all the keys that are mapped in this Map.
     * <p>
     * There is no guarantee or specification about the order of the keys in the
     * results.
     * 
     * @return the mapped keys.
     */
    public int[] getKeys() {
        return streamKeys().toArray();
    }

    /**
     * Get all indices that are mapped in this Map (the order of the indices is
     * not sequential).
     * <p>
     * There is a guarantee that the values represented in this array have a
     * 1-to-1 positional mapping to their respective keys returned from
     * {@link #getKeys()} if no modifications to the map have been made
     * between the calls
     * 
     * @return all values in the map in the matching order as
     *         {@link #getKeys()}
     */
    public int[] getIndices() {
        return streamIndices().toArray();
    }

    /**
     * Stream all the keys that are mapped in this Map.
     * <p>
     * There is no guarantee or specification about the order of the keys in the
     * results.
     * 
     * @return the mapped keys.
     */
    public IntStream streamKeys() {
        return liveIndices().map(i -> keys.get(i));
    }

    /**
     * Stream all indices that are mapped in this Map.
     * <p>
     * There is a guarantee that the values represented in this array have a
     * 1-to-1 positional mapping to their respective keys returned from
     * {@link #streamKeys()} if no modifications to the map have been made
     * between the calls
     * 
     * @return all values in the map in the matching order as
     *         {@link #getKeys()}
     */
    public IntStream streamIndices() {
        return liveIndices();
    }

    /**
     * Stream all entries in an Entry container.
     * @return a stream of all Key to Index mappings.
     */
    public Stream<IntKIntVEntry> streamEntries() {
        return liveIndices().mapToObj(i -> new IntKIntVEntry(keys.get(i), i));
    }

    /**
     * Create a string representation of the state of the KeyIndex instance.
     * 
     * @return a string useful for toString() methods.
     */
    public String report() {
        long allocated = Stream.of(bucketData).filter(b -> b != null).mapToLong(b -> b.length).sum();
        long max = IntStream.of(bucketSize).max().getAsInt();
        long vals = Stream.of(keys).filter(vs -> vs != null).count() * KVEXTENT;
        return String.format("IntIntMap size %s (used %d, deleted %d) buckets %d hashspace %d longest %d valspace %d",
                size(), size, deletedCount, bucketSize.length, allocated, max, vals);
    }

    /**
     * Compute a hashCode using just the key values in this map. The resulting
     * hash is the same regardless of the insertion order of the keys.
     * 
     * @return a useful hash of just the keys in this map.
     */
    public int getKeyHashCode() {
        if (size() == 0) {
            return 0;
        }
        return liveIndices().map(i -> keys.get(i)).map(k -> Integer.rotateLeft(k, k)).reduce((x, p) -> x ^ p)
                .getAsInt();
    }

    /**
     * Compute a hashCode using just the indexes mapped in this map. The
     * resulting hash is the same regardless of the insertion order of the keys.
     * Two maps which have the same indexes provisioned will have the same
     * resulting hashCode.
     * 
     * @return a useful hash of just the keys in this map.
     */
    public int getIndexHashCode() {
        if (size() == 0) {
            return 0;
        }
        return liveIndices().map(k -> Integer.rotateLeft(k, k)).reduce((x, p) -> x ^ p).getAsInt();
    }

    /**
     * Return true if this instance has the exact same key/index mappings.
     * 
     * @param obj
     *            the other IntKeyIndex to check.
     * @return true if this instance has the exact same key/index mappings.
     */
    @Override
    public boolean equals(Object obj) {
        if (!(obj instanceof IntKeyIndex)) {
            return false;
        }
        if (obj == this) {
            return true;
        }
        IntKeyIndex other = (IntKeyIndex)obj;
        if (other.size() != size()) {
            return false;
        }

        return liveIndices().allMatch(i -> same(other, i));
    }

    @Override
    public int hashCode() {
        return Integer.rotateLeft(getKeyHashCode(), 13) ^ getIndexHashCode();
    }

    @Override
    public String toString() {
        return report();
    }

    /* *****************************************************************
     * Support methods for implementing the public interface.
     * *****************************************************************
     */

    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;
    }

    private static int nextPowerOf2(final int value) {
        return Integer.highestOneBit((value - 1) * 2);
    }

    private static final int hashShift(final int key) {
        /**
         * This hash is a way of shifting 4-bit blocks, nibbles in a way that
         * the resulting nibbles are the XOR value of itself and all nibbles to
         * the left. Start with key (each letter represents a nibble, each line
         * represents an XOR)
         * 
         * <pre>
         *    A B C D E F G H
         * </pre>
         */
        final int four = key ^ (key >>> 16);

        /**
         * four is now:
         * 
         * <pre>
         *    A B C D E F G H
         *            A B C D
         * </pre>
         */
        final int two = four ^ (four >>> 8);
        /**
         * Two is now
         * 
         * <pre>
         *    A B C D E F G H
         *            A B C D
         *        A B C D E F
         *                A B
         * </pre>
         */
        final int one = two ^ (two >>> 4);
        /**
         * One is now:
         * 
         * <pre>
         *     A B C D E F G H
         *             A B C D
         *         A B C D E F
         *                 A B
         *       A B C D E F G
         *               A B C
         *           A B C D E
         *                   A
         * </pre>
         */
        return one;
    }

    private void deleteIndex(final int index) {
        if (deletedCount == 0 && deletedIndices == null) {
            deletedIndices = new int[INITIAL_BUCKET_SIZE];
        }
        if (deletedCount == deletedIndices.length) {
            deletedIndices = Arrays.copyOf(deletedIndices, extendSize(deletedIndices.length));
        }
        deletedIndices[deletedCount++] = index;
        keys.set(index, -1); // make the delete visible in the keys.
    }

    private int bucketId(final int key) {
        return mask & hashShift(key);
    }

    private int locate(final int[] bucket, final int bsize, final int key) {
        // keep buckets in sorted order, by the key value. Unfortunately, the
        // bucket contents are the index to the key, not the actual key,
        // otherwise Arrays.binarySearch would work.
        // Instead, re-implement binary search with the indirection.
        int left = 0;
        int right = bsize - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            int k = keys.get(bucket[mid]);
            if (k == key) {
                return mid;
            } else if (k < key) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -left - 1;
    }

    private int addKeyValue(final int key) {
        if (deletedCount > 0) {
            // There's a previously deleted spot, reuse it.
            deletedCount--;
            final int pos = deletedIndices[deletedCount];
            keys.set(pos, key);
            return pos;
        }
        keys.set(size, key);
        return size++;
    }

    private void insertBucketIndex(final int bucket, final int bucketPos, final int keyIndex) {
        if (bucketSize[bucket] == 0 && bucketData[bucket] == null) {
            bucketData[bucket] = new int[INITIAL_BUCKET_SIZE];
        } else if (bucketSize[bucket] == bucketData[bucket].length) {
            bucketData[bucket] = Arrays.copyOf(bucketData[bucket], extendSize(bucketData[bucket].length));
        }
        if (bucketPos < bucketSize[bucket]) {
            System.arraycopy(bucketData[bucket], bucketPos, bucketData[bucket], bucketPos + 1, bucketSize[bucket]
                    - bucketPos);
        }
        bucketData[bucket][bucketPos] = keyIndex;
        bucketSize[bucket]++;
        if (bucketSize[bucket] > IDEAL_BUCKET_SIZE) {
            rebucket();
        }
    }

    private void rebucket() {
        // because of the "clever" hashing system used, we go from a X-bit to an
        // X+2-bit bucket count.
        // in effect, what this means, is that each bucket in the source is
        // split in to 4 buckets in the destination.
        // There is no overlap in the new bucket allocations, and the order of
        // the results in the new buckets will be the same relative order as the
        // source. This makes for a very fast rehash.... no sorting, searching,
        // or funny stuff needed. O(n).
        int[][] buckets = new int[bucketData.length * 4][];
        int[] sizes = new int[buckets.length];
        int msk = buckets.length - 1;
        for (int b = 0; b < bucketData.length; b++) {
            for (int p = 0; p < bucketSize[b]; p++) {
                addNewBucket(bucketData[b][p], buckets, sizes, msk);
            }
            // clear out crap as soon as we can,
            bucketData[b] = null;
        }
        bucketData = buckets;
        bucketSize = sizes;
        mask = msk;
    }

    private void addNewBucket(final int index, final int[][] buckets, final int[] sizes, final int msk) {
        int b = msk & hashShift(keys.get(index));
        if (sizes[b] == 0) {
            buckets[b] = new int[INITIAL_BUCKET_SIZE];
        } else if (sizes[b] == buckets[b].length) {
            buckets[b] = Arrays.copyOf(buckets[b], extendSize(buckets[b].length));
        }
        buckets[b][sizes[b]++] = index;
    }

    /* *****************************************************************
     * Implement streams over the indices of non-deleted keys in the Map
     * *****************************************************************
     */

    private IntStream liveIndices() {
        return StreamSupport.intStream(new IndexSpliterator(modCount, size(), 0, bucketData.length), false);
    }

    private class IndexSpliterator extends Spliterators.AbstractIntSpliterator {

        private int lastBucket;
        private int bucket;
        private int pos = 0;
        private final int gotModCount;

        public IndexSpliterator(int gotModCount, int expect, int from, int limit) {
            // index values are unique, so DISTINCT
            // we throw concurrentmod on change, so assume IMMUTABLE
            super(expect, Spliterator.IMMUTABLE + Spliterator.DISTINCT + Spliterator.SIZED + Spliterator.SUBSIZED);
            this.gotModCount = gotModCount;
            bucket = from;
            lastBucket = limit;
        }

        private void checkConcurrent() {
            if (modCount != gotModCount) {
                throw new ConcurrentModificationException(
                        "Map was modified between creation of the Spliterator, and the advancement");
            }
        }

        private int advance() {
            checkConcurrent();
            while (bucket < lastBucket && pos >= bucketSize[bucket]) {
                bucket++;
                pos = 0;
            }
            return bucket < lastBucket ? bucketData[bucket][pos++] : -1;
        }

        @Override
        public boolean tryAdvance(final IntConsumer action) {
            final int index = advance();
            if (index >= 0) {
                action.accept(index);
            }
            return index >= 0;
        }

        @Override
        public boolean tryAdvance(final Consumer<? super Integer> action) {
            final int index = advance();
            if (index >= 0) {
                action.accept(index);
            }
            return index >= 0;
        }

        @Override
        public Spliterator.OfInt trySplit() {
            checkConcurrent();
            int half = Arrays.stream(bucketSize, bucket + 1, lastBucket).sum() / 2;
            if (half < 8) {
                return null;
            }
            int sum = 0;
            for (int i = lastBucket - 1; i > bucket; i--) {
                sum += bucketSize[i];
                if (sum > half) {
                    IndexSpliterator remaining = new IndexSpliterator(gotModCount, sum, i, lastBucket);
                    lastBucket = i;
                    return remaining;
                }
            }
            return null;
        }

        @Override
        public void forEachRemaining(final IntConsumer action) {
            checkConcurrent();
            if (bucket >= lastBucket) {
                return;
            }
            while (bucket < lastBucket) {
                while (pos < bucketSize[bucket]) {
                    action.accept(bucketData[bucket][pos]);
                    pos++;
                }
                bucket++;
                pos = 0;
            }
        }

        @Override
        public void forEachRemaining(final Consumer<? super Integer> action) {
            checkConcurrent();
            if (bucket >= lastBucket) {
                return;
            }
            while (bucket < lastBucket) {
                while (pos < bucketSize[bucket]) {
                    action.accept(bucketData[bucket][pos]);
                    pos++;
                }
                bucket++;
                pos = 0;
            }
        }

    }

}

Answer 1

Note: I didn't have the willpower to go through and make all the edits and test your code with them like I normally do. Apologies. It should still work the same, but you'll want to double-check and call me out on any mistakes.

IntKIntVEntry

In your class Javadoc comment, you need to explain better what it does. Just

Simple container class containing a key/value mapping.

sure is accurate, but something like

<p>Key/value pair of two <code>int</code>s.</p>
<p>Note: This is solely to report data, not to actually store it.</p>

Note the sly application of HTML formatting to made it look pretty. This is (approximately) what it'll look like:

Key/value pair of two ints.

Note: This is solely to report data, not to actually store it.

The same thing goes for all of your Javadoc comments: Sure, they work, but they could be better. Yes, I know this isn't a 'serious' class. Good documentation is always important. No, I don't know why I'm writing this like we're having a conversation. Yes, I know talking to myself is a sign of madness. I'm gonna move on.

In your constructor:

super();

You never need to do this. If you would call a superconstructor without any arguments, it's already implied, so don't. You didn't do it in IntKeyIndex, and I'm not sure why you did it here.

In equals():

return key == ((IntKIntVEntry)obj).key && value ==((IntKIntVEntry)obj).value;

This line bugs me, and not just because of the odd spacing around your operators. Sure, it's all fancy and compact and totes cools, but so is this:

!function(e){location="http://codereview.stackexchange.com/search?tab=votes&q="+(e[0]?e.reduce(function(e,n){return e+(~n.indexOf("-")?"-%5B"+n.substring(1):"%5B"+n)+"%5D+"},""):e)+"created%3A60d+‌​answers%3A0+closed%3Ano"}(prompt("Tags: (leave blank for none)").trim().split(/\s+/));

^{Credit where it's due to Ismael Miguel for helping me golf that down.}

Can you read that? I can't. But hey, it looks cool and it's just one line!

Make it more readable by casting first:

IntKIntVEntry casted = (IntKIntVEntry) obj;
return key == casted.key && value == casted.value;

It takes either just as much or less memory, is either just as fast or faster, and is more readable. I haven't

Anyway, on to nitpicking the next class:

IntKeyIndex

I can't figure out why, but you keep referring to an IntIntMap in documentation (see the docs for the constructor) when the class is called IntKeyIndex; personally, I like IntIntMap better.

Oh my gosh the documentation here is beautiful. Why didn't you document IntKIntVEntry like that?! You're awfully inconsistent.

You do have some awfully shady HTML in them, though:

1. You use <p> as a paragraph break, rather than a paragraph element. It's usage is like this:

   <p>Some text!</p>
   <p>A second paragraph.</p>
   

   If you want an HTML tag to use in its place (for Find/Replace convenience) use <br>. However, I'd recommend going through and using <p> properly. It looks nicer than <br>.

   See <p> and <br> for more information.

2. You intermittently use and don't use <code></code>. Use it like you do backticks: Around everything that's code, or would be in context. For example:

   In order to support setting the value at index Integer.MAX_VALUE (which would require an array of size Integer.MAX_VALUE + 1),
   

   should probably be

   In order to support setting the value at index <code>Integer.MAX_VALUE</code> (which would require an array of <code>Integer.MAX_VALUE + 1</code>),
   

   Same thing applies for every bit of code you embed in the descriptions, even if it's embedded in prose.

3. In your @annotations, you always start your sentence with a lowercase letter. Remember that

   @param name your text here
   

   renders as

   name your text here

   It looks much nicer if you use a capital first letter:

   @param name Your text here
   

   name Your text here

   Or, to keep ripping off the official Javadocs, put - at the beginning of your text:

   @param name - Your text here
   

   name - Your text here

private int[] deletedIndices = null;
private int deletedCount = 0;
private int modCount = 0;

When declared as class-scoped variables (i.e. static or instance fields) Objects default to null when first created, and ints default to 0. You don't need to explicitly state that.

Spliterator.IMMUTABLE + Spliterator.DISTINCT + Spliterator.SIZED + Spliterator.SUBSIZED

Another case of "It works, but ewwww." Use | instead. It doesn't really matter in this case, but it's a good habit to build, so if you use a library that has fields that could reasonably be typo'd for one another, you won't get screwed. Plus, it has the benefit of being conventionally used to combine int-based flags, so it's clearer what it's doing.

In hashShift(), you could probably give the variables better names, though with the extensive comments it doesn't matter much.

In at least one method, you do something like this:

Arrays.stream(deletedIndices, 0, deletedCount).anyMatch(i -> i == index)

when you could instead make a method that takes the same arguments called include or the like in one of your utility classes that doesn't make an extra, one-off object.

You should have a version of getKey that doesn't take a notThere and throws an exception if it can't find that key.

public IntStream streamIndices() {
    return liveIndices();
}

This stinks, to me. Why not merge the two, rather than having one that return exactly and only the unmodified result of the other without doing anything else?

long allocated = Stream.of(bucketData).filter(b -> b != null).mapToLong(b -> b.length).sum();
long max = IntStream.of(bucketSize).max().getAsInt();

Is there any particular reason you're weighing down your program with more one-off objects and expensive calculations instead of using an uglier -- but more efficient -- for loop? It could be rewritten like this:

long allocated = 0;
long max = 0;
long vals = 0;
for (int[] bucket : buckedData) {
    if (bucketData != null) {
        allocated += bucketData.length;
    }
}
for (int size : bucketSize) {
    if (masx < size) {
        max = size;
    }
}
long vals = Stream.of(keys).filter(vs -> vs != null).count() * KVEXTENT;

Note that I would highly recommend implementing Iterable in some way in IntArray; you'll also want to see PrimitiveIterator.OfInt

I'm also ignoring the fact that the maximum of an int[] can only ever be an int so there's no reason to autocast it to long, because I'm too tired to think about what your reasoning is.

IndexSpliterator

I'd comment about the sudden lack of documentation, but it's not a factor in this case because it's just another ? extends Spliterator, so it doesn't much matter.

In your constructor definition, you declare an int expect, then call the superconstructor with it, when the superconstructor takes a long.

In tryAdvance() (both versions):

if (index >= 0) {
    action.accept(index);
}
return index >= 0;

Why? Why not the much clearer

if (index >= 0) {
    action.accept(index);
    return true;
} else {
    return false;
}

It takes much less time to figure out what you're doing, and any performance lost is utterly negligible.

Everywhere

You've got a few oddly-placed newlines -- after a line that ends in {, you should immediately start with code, rather than having a newline to separate. This includes method headers, if statements, class declarations, etc. Whenever it looks better to you, feel free to break this specific rule, but in general, try to avoid it.

You've got a couple of minor English errors in some of your comments, but nothing that impacts readability. If you'd like I can give a more detailed list outside of this already-too-long list.

I like how you've had most of your methods use other methods; it makes it much more readable. For example:

public boolean isEmpty() {
    return size() == 0;
}

What I've seen and done a lot is something more like this:

public boolean isEmpty() {
    //      Map's actual size
    return size - deletedCount == 0;
}

Good on you for not.

Also, congrats on being the first person I've seen yet who uses things like Integer.rotateLeft instead of writing their own function to do it. Note that I support that in this case because it doesn't use extra memory, which building a throwaway stream does.

Apologies for not covering very much about efficiency, but I decided to work on this for two whole days, and in the end, most of my tips either turned out to be wrong, useless, or got buried under the flood of other things. All in all, a very well-written program; I couldn't find many obvious ways to reduce memory consumption in the algorithm itself. You need to focus as much on public methods as you do on private ones -- if those are slow/inefficient, your whole library is slow. Don't do cool but less efficient things just because they're public.

Answer 2

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;

---

EDIT:

@Rolfl pointed out that logically these 2 sets of conditions do not check the same thing, so logically they should not be linked in an else if statement, because they have nothing to do with each other. This makes complete sense to me.

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.