Re: Using char[] as key in a HashMap

Avinash Lakshman wrote:
> Hi All
>
> In the application that we are building we have the need to maintain
> some objects in memory in a HashMap keyed by a String. But it seems that
> the overhead of the String is such that the overhead is more than the
> length of the characters in the String. I was thinking of reducing the
> memory footprint significantly by replacing the key with a char[] of the
> String. How can I achieve this? How can I implement the hashCode() and
> equals() of char[]? Do I have to do it with a class that wraps the char[]?
>

The overhead shouldn't be _that_ heavy, though..

     /** The value is used for character storage. */
     private final char value[];

     /** The offset is the first index of the storage that is used. */
     private final int offset;

     /** The count is the number of characters in the String. */
     private final int count;

     /** Cache the hash code for the string */
     private int hash; // Default to 0

However, if you've ended up with the key Strings by using
substring(begin[, end]) on some longer String, you'll carry the original
length of the value-array with you.

I've thought about how sql drivers work this - when you do
rs.getString(x), does it allocate a fresh string (which is should, in my
opinion), or does it substring the result out (which, in a common case
of retaining the result, maybe forever in a cache, would waste lots of
bytes)? I haven't tested/checked it on any driver, though.

Anyway, you can trim off the extras by doing "new String(oldString)":

     public String(String original) {
        int size = original.count;
        char[] originalValue = original.value;
        char[] v;
        if (originalValue.length > size) {
            // The array representing the String is bigger than the new
            // String itself.  Perhaps this constructor is being called
            // in order to trim the baggage, so make a copy of the array.
             int off = original.offset;
             v = Arrays.copyOfRange(originalValue, off, off+size);
        } else {
            // The array representing the String is the same
            // size as the String, so no point in making a copy.
            v = originalValue;
        }
        this.offset = 0;
        this.count = size;
        this.value = v;
     }

And btw: regarding the new ideas: you'll end up trading in memory for
performance. If you don't want to hold an object that holds a cached
hash along with the value-array, you'll probably end up doing more hash
computations (like if using Bob's CharBuffer suggestion, btw note
javadoc hashCode() on CharBuffer), or more elaborate computations in the
comparator (if using Neil's TreeMap suggestion).

Regarding the CharBuffer:
     final char[] hb;     // Non-null only for heap buffers
     final int offset;
     boolean isReadOnly;  // Valid only for heap buffers

... and it extends Buffer:

     private int mark = -1;
     private int position = 0;
     private int limit;
     private int capacity;

     // Used only by direct buffers
     // NOTE: hoisted here for speed in JNI GetDirectBufferAddress
     long address;

Can't seem to get why that would give so much less overhead than String.

Indeed, the TreeMap suggestion with external Comparator seems very good
if it is paramount to get the memory down, by sacrificing a bit (maybe
quite a bit) of CPU. On the other hand, you could make your own
"StringX" char[] wrapper, which didn't had offset nor count, only the
value-array and the (precomputed) hash int. You could possibly even
"fake" the equals and hashcode, so that they hashed the same, and your
StringX wrapper equalled to a String with the same value.

BTW: on a somewhat related and interesting note, have you read this one?
   http://www.javaspecialists.co.za/archive/Issue014.html

Endre.

===================================
This list is hosted by DevelopMentor®  http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com