Using an Array as table in custom generic Hashtable to store entries

Question

I am experimenting with making my own custom Hashtable as a way of understanding the data structure, and have run into what many other people seem to have run into; that you cannot create a generic array the same way you would make another array. I understand the reasons for this, but also know that Java's HashMap itself uses an array to store Entry items. If my understanding is correct, Java's HashMap creates an object[] and then casts each element of the object to the Entry class each time the put or get method is called. Is this correct?

I have read answers about generic arrays saying it is possible to instead do something like having Entry[] table as a class variable and then using table = (Entry[]) new Object[size]; in the constructor as a way of avoiding having to do the casting in both the put and get methods, but this does leads to a ClassCastException, which is understandable since it would have to check each element of the Object array anyway in order to make sure they are the Entry class. Does this mean I cannot use this method in my custom Hashtable?

Finally, another way of creating the Entry array seems to be checking the class type in the constructor and using Entry[] table = (Entry[]) Array.newInstance(c, s); Is this method perhaps more suitable?

Below is a snippet of my own code relevant to this question. I am wondering if my interpretation of everything above is correct, and if this is an acceptable way of going about my own Hashtable. I also understand my method of using determining the index for the given hashCode may be incorrect, but that is outside the scope of my question :), and my put and get methods are definitely incomplete!

public class HashTable<K, V> {
Object[] buckets;

HashTable(int size) {
    buckets = new Object[size];
    this.size = size;
}

void put(K key, V value) {
    int i = key.hashCode()%size;
    buckets[i] = (Entry) new Entry(key, value, (Entry) buckets[i]);
}

K get(K key) {
    int i = key.hashCode()%size;
    Entry entry = (Entry) buckets[i];
    return entry.key;
}
}

Answer 1

If my understanding is correct, Java's HashMap creates an object[] and then casts each element of the object to the Entry class each time the put or get method is called. Is this correct?

The standard library's source is available. You could check it for yourself. If you did, you would find that no, that's not quite what java.util.HashMap does.

I have read answers about generic arrays saying it is possible to instead do something like having Entry[] table as a class variable and then using table = (Entry[]) new Object[size];

To the extent that such answers recommended exactly what you describe, they are wrong. I suspect, however, that your "something like" does not capture the key elements of the answers you saw.

There are two potential issues

1. Creating an array whose element type is drawn from a type parameter:

class MyClass<T> {
    // CAN'T DO THIS:
    T[] array = new T[2];

    // can do this:
    T[] array = (T[]) new Object[2];

    // or this:
    Object[] array = new Object[2];  // (and cast later)
}

2. Creating an array whose element type is parameterized

class MyOtherClass<T> {
    // CAN'T DO THIS, EITHER:
    SomeType<T>[] array = new SomeType<T>[2];

    // can do this:
    SomeType<T>[] array = (SomeType<T>) new SomeType[2];

    // or this:
    SomeType[] array = new SomeType[2];  // (and cast later)
}

As you will have seen in the JDK source (you did follow the above link, right?), HashMap's issue is of the second type, and what it does is create an array of the appropriate raw type, and then cast that to the desired parameterized type -- which will trip the compiler's type safety warnings, but is in fact perfectly type safe as long as no other, raw or differently parameterized, reference escapes.

in the constructor as a way of avoiding having to do the casting in both the put and get methods, but this does leads to a ClassCastException [...]. Does this mean I cannot use this method in my custom Hashtable?

Yes, of course it does. The method you describe and demonstrate is invalid, as the exception tells you. An Object[] is not an Entry[]. But that's not what the answers you reviewed were suggesting you do.

Finally, another way of creating the Entry array seems to be checking the class type in the constructor and using Entry[] table = (Entry[]) Array.newInstance(c, s); Is this method perhaps more suitable?

Rarely is reflection a better answer for anything. It only makes sense when you don't have all the type information you need at compile time, and that is not your case.

Answer 2

It looks like your Entry class is an inner class, which I'd recommend against because it makes things more complicated. First, let's just assume that we don't have an inner class.

For the illustration, we have a simple generic class:

class Foo<T> {}

There's a difference between these two generic array types:

class Container<T> {
    //              creating an array with erasure of T[]
    //                    vvvvvvvvvvvvv
    T[]      arrA = (T[]) new Object[N];
    //              creating an array with erasure of Foo<T>[]
    //                         vvvvvvvvvv
    Foo<T>[] arrB = (Foo<T>[]) new Foo[N];
    // Note that the following would be slightly
    // better because it doesn't use a raw type,
    // but it doesn't work for this illustration
    // because it's not the erasure of Foo[]:
    //              (Foo<T>[]) new Foo<?>[N];
}

Casting checks the erasure of type, so suppose we create a new container and assign those arrays to something in the outside world:

Container<String> c = new Container<String>();
String[]      arrA1 = c.arrA;
Foo<String>[] arrB1 = c.arrB;
// After erasure these assignments become:
String[]      arrA1 = (String[]) arrA;
Foo[]         arrB1 =            arrB;

The first assignment, arrA1 = c.arrA throws a ClassCastException, but the second assignment, arrB1 = c.arrB does not. This is because in the first case the conversion is from Object[] to String[] whereas in the second case there is no checked cast because all parameterizations of Foo<T> just become Foo after erasure.

This is all to explain my next point which is that creating an array of a parameterized type is more acceptable than creating an array of a type variable. In the case of the type variable array we have an Object[] masquerading as a T[] but in the case of the parameterized type we actually do have an array of Foo[], it's just that there is no checking for the type arguments to Foo. In other words:

Container<String> c = new Container<String>();
// Recall that this assignment doesn't throw a ClassCastException
Foo<String>   arrB = c.arrB;
Object[] arrBAsOBj =   arrB;
// This assignment throws an ArrayStoreException
arrBAsObj[0] = new StringBuilder();
// This assignment does not throw an ArrayStoreException
arrBAsObj[0] = new Foo<Integer>();

Although, I'd like to note that you should never expose a generic array to the outside world. I'm just doing that to illustrate the explanation.

Anyway, if you're writing something like a hash table, it's acceptable to create an unchecked array of a parameterized type. I usually write a helper method like this:

private static <K, V> Map.Entry<K, V>[] createUncheckedArray(int length) {
    @SuppressWarnings("unchecked")
    final Map.Entry<K, V>[] unchecked =
        (Map.Entry<K, V>[]) new Map.Entry<?, ?>[length];
    return unchecked;
}

Just don't return it to the outside world, because we still don't actually have a generic array, just an array of Map.Entry with unchecked type arguments.

Really Java should just have a simple class like Array<T> for this sort of case when we actually need a fixed-length container.

For an inner class you have to use a parameterized type as a qualifier, something like this:

private Entry[] createUncheckedArray(int length) {
    @SuppressWarnings("unchecked")
    final Entry[] unchecked =
        (Entry[]) new HashTable<?, ?>.Entry[length];
    return unchecked;
}