Arrays as key in a HashMap

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi,

I want to use arrays as keys in a HashMap. Now, this does not seem to
be a good idea, as it will use the hashCode implementation of Object,
which discriminate every array.

So basically, I want a hash map that uses Arrays.hashCode instead. Does
such an implementation exist? Alternatively, I could wrap the arrays in
a list, or write my own ArrayHashMap, which would be best?

TIA, H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD9KvDe+7xMGD3itQRAmmaAJ405AUCbAysAhCDZUOV+JBDaqSO6ACeIKFf
tpcA0PZPTJM7Q10GzNQV7Vw=
=HCOv
-----END PGP SIGNATURE-----

 

[Mike Schilling]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi,

I want to use arrays as keys in a HashMap. Now, this does not seem to
be a good idea, as it will use the hashCode implementation of Object,
which discriminate every array.

So basically, I want a hash map that uses Arrays.hashCode instead. Does
such an implementation exist? Alternatively, I could wrap the arrays in
a list, or write my own ArrayHashMap, which would be best?

Something I've wanted on occasion is a HashMap where I can specify an object
used to construct the hashes, much as I can specify the Comparator to be
used in a TreeMap. No such luck, so far.

The simplest thing you can do is create a wrapper object for the arrays,
something like (not compiled or tested, so please ignore any typos)

public class ArrayWrapper()
{
private Object[] array;

public ArrayWrapper(Object[] arr)
{
array = arr;
}

public boolean equals(Object o)
{
return (o instanceof ArrayWrapper) &&
((ArrayWrapper)o).array == array);
}

public int hashCode()
{
return Arrays.hashCode(array);
}
}

and use this wrapper for the key.

This assumes your arrays' members are Objects, of course. If they're a
fixed type of scalar (say, all arrays of ints) make that adjustment. If
they're of mixed types, it's more complicated.

And, of course, you can't allow the arrays or their members to change once
they're used as keys, because that would foul up the has calculation.

 

[Oliver Wong]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi,

I want to use arrays as keys in a HashMap. Now, this does not seem to
be a good idea, as it will use the hashCode implementation of Object,
which discriminate every array.

So basically, I want a hash map that uses Arrays.hashCode instead. Does
such an implementation exist? Alternatively, I could wrap the arrays in
a list, or write my own ArrayHashMap, which would be best?

Rather than using the arrays as keys, why not use the return value of
Arrays.hashCode() as the key?

E.g. instead of

<pseudocode>
myHash.put(myArray, myValue);
if (myHash.containsKey(myArray)) {
doSomething();
}
</pseudocode>

do this:

<pseudocode>
myHash.put(Arrays.hashCode(myArray), myValue);
if (myHash.containsKey(Arrays.hashCode(myArray))) {
doSomething();
}
</pseudocode>

- Oliver

 

[Chris Uppal]

Something I've wanted on occasion is a HashMap where I can specify an
object used to construct the hashes, much as I can specify the
Comparator to be used in a TreeMap.

I don't understand why they aren't provided either. It seems such an obvious
requirement. (And Apache Commons didn't have one either last time I looked).

The simplest thing you can do is create a wrapper object for the arrays,
something like [...]

Since the only purpose of the wrappers is to compute hash values (and mediate
the corresponding equality test), and since hashing an array can be a pricey
business, I'd recommend computing the hash value once and then storing it in
the wrapper object.

public boolean equals(Object o)
{
return (o instanceof ArrayWrapper) &&
((ArrayWrapper)o).array == array);
}

I think you must have been a trifle hurried there, the test should be:
return (o instanceof ArrayWrapper)
&& Arrays.equals(array, ((ArrayWrapper)o).array);

-- chris

 

[Chris Uppal]

Rather than using the arrays as keys, why not use the return value of
Arrays.hashCode() as the key?

Because the value returned from Arrays.hashCode() cannot be expected to
identify the array's contents uniquely.

-- chris

 

[Oliver Wong]

Because the value returned from Arrays.hashCode() cannot be expected to
identify the array's contents uniquely.

Ah yes, of course. I forgot about the actual behaviour that the Map API
enforces. Sorry.

- Oliver

 

[Mike Schilling]

Something I've wanted on occasion is a HashMap where I can specify an
object used to construct the hashes, much as I can specify the
Comparator to be used in a TreeMap.

I don't understand why they aren't provided either. It seems such an
obvious
requirement. (And Apache Commons didn't have one either last time I
looked).

The simplest thing you can do is create a wrapper object for the arrays,
something like [...]

Since the only purpose of the wrappers is to compute hash values (and
mediate
the corresponding equality test), and since hashing an array can be a
pricey
business, I'd recommend computing the hash value once and then storing it
in
the wrapper object.

Yes, that's a good point. (Though I think HashMap already stores the key's
values in the associated Entry object, and the wrappers used to do lookups
are likely to be use-once anyway, e.g.

result = map.get(new ArrayWrapper(array));

Still, a good point.)

I think you must have been a trifle hurried there, the test should be:
return (o instanceof ArrayWrapper)
&& Arrays.equals(array, ((ArrayWrapper)o).array);

Probably so, since it's unlikely that the arrays have identity, but the OP
didn't say one way or the other.

 

[Thomas Hawtin]

I want to use arrays as keys in a HashMap. Now, this does not seem to
be a good idea, as it will use the hashCode implementation of Object,
which discriminate every array.

So basically, I want a hash map that uses Arrays.hashCode instead. Does
such an implementation exist? Alternatively, I could wrap the arrays in
a list, or write my own ArrayHashMap, which would be best?

Arrays.asList should do you (at least for arrays of references). On the
other hand, if you are using Java 1.5+, you might as well use Lists
instead of arrays of references.

Tom Hawtin

 

[trippy]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi,

I want to use arrays as keys in a HashMap.

But a key has to be unique.

1 key to 1 value

Now, this does not seem to
be a good idea, as it will use the hashCode implementation of Object,
which discriminate every array.

So basically, I want a hash map that uses Arrays.hashCode instead. Does
such an implementation exist? Alternatively, I could wrap the arrays in
a list, or write my own ArrayHashMap, which would be best?

TIA, H.

--
trippy
mhm31x9 Smeeter#29 WSD#30
sTaRShInE_mOOnBeAm aT HoTmAil dOt CoM

NP: "I Am The Law" -- Anthrax

"Now, technology's getting better all the time and that's fine,
but most of the time all you need is a stick of gum, a pocketknife,
and a smile."

-- Robert Redford "Spy Game"

 

[Finomosec]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi,

I want to use arrays as keys in a HashMap. Now, this does not seem to
be a good idea, as it will use the hashCode implementation of Object,
which discriminate every array.

So basically, I want a hash map that uses Arrays.hashCode instead. Does
such an implementation exist? Alternatively, I could wrap the arrays in
a list, or write my own ArrayHashMap, which would be best?

TIA, H.

Why do you need arrays as as keys anyway?

Maybe you should change the alorithm ...

Maybe its possible to switch key and value of your hashmap.
Or you may think about not using hashmap at all and instead storing your
hash-value in the wrapper-object or somewhere else ...

Maybe you can use 2 parallel lists, to store the arrays and keys ...

Greetigs Finomosec;

 

[Roedy Green]

Why do you need arrays as as keys anyway?

You can't use arrays literally as keys. You need sensible equals and
hashCode for them. Absolute identity is probably not what you want.

So you must embed you array in a class that lets you override those
two methods.

 

[John C. Bollinger]

But a key has to be unique.

1 key to 1 value

And your point is?

There is nothing inherently unworkable with arrays being map keys;
arrays are objects, after all. You might as well argue that Strings
cannot be used as keys because they (often) contain multiple characters.

 

[trippy]

And your point is?

There is nothing inherently unworkable with arrays being map keys;
arrays are objects, after all. You might as well argue that Strings
cannot be used as keys because they (often) contain multiple characters.

But arrays have more than one thing in them by definition.

Okay, say using this idea, you keep a list of users and their
information. Now, you have multiple people accessing the same user's
information because thisguy[0] will give you the same value as thisguy
[4].

I guess that's my point. 1 key to 1 value. With the arrays you'll have
multiple keys to values.

I guess if you want that, whatever but I think it's a bad idea. Why
don't you keep things in a plain old ArrayList if you're gonna do that.

--
trippy
mhm31x9 Smeeter#29 WSD#30
sTaRShInE_mOOnBeAm aT HoTmAil dOt CoM

NP: "I Am The Law" -- Anthrax

"Now, technology's getting better all the time and that's fine,
but most of the time all you need is a stick of gum, a pocketknife,
and a smile."

-- Robert Redford "Spy Game"

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Thomas Hawtin schreef:

Arrays.asList should do you (at least for arrays of references). On the
other hand, if you are using Java 1.5+, you might as well use Lists
instead of arrays of references.

Why? I use the hash map to keep track of instances, in combination with
a factory method. The class to be instantiated is already a wrapper,
around a Symbol and some States (both classes of my program), so I
thought to put the States in an array to keep it simple. That way, I
can use varargs in the factory method, and get an array of States. But
of course I could use Arrays.asList. The objects (InputTuple), are
immutable, in fact, their main purpose is to serve as input to a hash
map themselves. But to limit the number of instantiations, I thought it
would be useful to make the factory method. (One that does not inherit,
so with some characteristics of Singleton, i.e. one wrapper for every
possible content).

So the arrays are indeed not going to change.

Hm, then again, maybe it is semantically more meaningful to use a List
(as they are an argument tuple to a function).

H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD9a4Ke+7xMGD3itQRArFUAJ9gACsdoYJjGrTe784NYqTFjyRXdwCfe0Lr
LmlXRAACEQMBfdsHA8CWleQ=
=Kodf
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

trippy schreef:

And your point is?

There is nothing inherently unworkable with arrays being map keys;
arrays are objects, after all. You might as well argue that Strings
cannot be used as keys because they (often) contain multiple characters.

But arrays have more than one thing in them by definition.

Okay, say using this idea, you keep a list of users and their
information. Now, you have multiple people accessing the same user's
information because thisguy[0] will give you the same value as thisguy
[4].

I guess that's my point. 1 key to 1 value. With the arrays you'll have
multiple keys to values.

I guess if you want that, whatever but I think it's a bad idea. Why
don't you keep things in a plain old ArrayList if you're gonna do that.

Still don?t see your point. What?s the difference if I only want some
objects to be stored as a list, between ArrayList and array? Only for
reading, I see no point in using a List.

H.

--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD9a4je+7xMGD3itQRAqvSAJ9vk1FFbS7HHdGR4cJpYLunSXgUOQCfSqWd
7qeAeupwslCJnDbE5T52TLk=
=Tjj/
-----END PGP SIGNATURE-----

 

[Hendrik Maryns]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Finomosec schreef:

Why do you need arrays as as keys anyway?

Maybe you should change the alorithm ...

Maybe its possible to switch key and value of your hashmap.

No. The elements of the array are not the values of some function, but
rather, their ordering specifies the object I want to retrieve.

Or you may think about not using hashmap at all and instead storing your
hash-value in the wrapper-object or somewhere else ...

I don?t see what you mean. Or perhaps I do, but then, it is not usable
for my purpose.

Maybe you can use 2 parallel lists, to store the arrays and keys ...

Hm. Yes, this could work. But more work than I would want to spend. I
like to use the canned methods where possible, makes my code less
error-prone.

Thanks anyway, H.
--
Hendrik Maryns

==================
www.lieverleven.be
http://aouw.org
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)

iD8DBQFD9a9Ce+7xMGD3itQRAl+TAJ46bQOXDWnRrpX8Vnek95wv3hibgQCdFBmV
vXLKNGRQF9+RNLLF16cEd3U=
=xSvT
-----END PGP SIGNATURE-----

 

[tom fredriksen]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1
NotDashEscaped: You need GnuPG to verify this message

Hi,

I want to use arrays as keys in a HashMap. Now, this does not seem to
be a good idea, as it will use the hashCode implementation of Object,
which discriminate every array.

So basically, I want a hash map that uses Arrays.hashCode instead. Does
such an implementation exist? Alternatively, I could wrap the arrays in
a list, or write my own ArrayHashMap, which would be best?

Why in the world do you want to use an array as a key. This goes against
the entire concept of a hashtable. A key should be a single context
value, not a sum of many disparate, but similar, values/objects.

In any case a key must be immutable, and an array is seldom used for
immutable storage.

In my opinion you are breaking the common idioms of the language by
doing it that way. You should really find something else to use as the key.

/tom

 

[Chris Uppal]

Why in the world do you want to use an array as a key. This goes against
the entire concept of a hashtable. A key should be a single context
value, not a sum of many disparate, but similar, values/objects.

/You/ may think of arrays like that, but there's nothing to say that Hendrik
has to. An array is just an object with a compound value, like any other
object.

And they're only mutable if you change 'em...

-- chris

 

[tom fredriksen]

/You/ may think of arrays like that, but there's nothing to say that Hendrik
has to. An array is just an object with a compound value, like any other
object.

And they're only mutable if you change 'em...

And /You/ obviously think otherwise.

My point is to advise about possible dangers and mystical bugs by doing
it that way. A complex key like that is just begging for trouble along
the way. KISS.
Not to mention the idiomatic breakdown.

/tom

 

[Oliver Wong]

And your point is?

There is nothing inherently unworkable with arrays being map keys;
arrays are objects, after all. You might as well argue that Strings
cannot be used as keys because they (often) contain multiple characters.

But arrays have more than one thing in them by definition.

Okay, say using this idea, you keep a list of users and their
information. Now, you have multiple people accessing the same user's
information because thisguy[0] will give you the same value as thisguy
[4].

I guess that's my point. 1 key to 1 value. With the arrays you'll have
multiple keys to values.

I guess if you want that, whatever but I think it's a bad idea. Why
don't you keep things in a plain old ArrayList if you're gonna do that.

The single array is the singke key to the single value. John's analogy
to strings is an excellent one. Someone could protest "But a string has
multiple characters! thisString.getCharAt(0) will you the same value as
thisString.getCharAt(4)", etc. but the point is that we're not using each
character as a multitude of keys; rather we're using the whole String as one
big key.

Similarly, we're not using the individual items in the array as multiple
keys, but we're using the whole array as one big key.

- Oliver