Mapping arbitrary Int values to a linear index space

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.

What would be really nice is a Map 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:

• it uses a hash system on the key which allows hash buckets to be re-hashed very fast, when the hash table becomes inefficient.

• 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

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


Key/value pair of two ints.

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

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:

-
You use
as a paragraph break, rather than a paragraph element. It's usage is like this:


Some text!

A second paragraph.


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

See
and
for more information.

-
You intermittently use and don't use `. 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 Integer.MAX_VALUE (which would require an array of Integer.MAX_VALUE + 1),

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

-
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

StackExchange Code Review Q#82983, answer score: 13