 |
 | Home | Contact Us | FAQ | Search & Site Map | Link to Us |
 | Sign In | Join | Other 45 Sites in Network |
Java Forum / General / February 2006Arrays as key in a HashMap
-----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.  SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 9 lines] > 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. > 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 >> 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 [quoted text clipped - 15 lines] > 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.) >> public boolean equals(Object o) >> { [quoted text clipped - 5 lines] > 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. > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 9 lines] > 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 > 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 >> 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. Ah yes, of course. I forgot about the actual behaviour that the Map API enforces. Sorry. - Oliver > 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, [quoted text clipped - 3 lines] > 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 SignatureUnemployed English Java programmer http://jroller.com/page/tackline/ -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Thomas Hawtin schreef: >> 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, [quoted text clipped - 7 lines] > 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 3 lines] > > 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, [quoted text clipped - 5 lines] > > TIA, H. Signaturetrippy 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" >>I want to use arrays as keys in a HashMap. > > 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. SignatureJohn Bollinger jobollin@indiana.edu > >>I want to use arrays as keys in a HashMap. > > [quoted text clipped - 7 lines] > 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. Signaturetrippy 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" -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message trippy schreef: >>>> I want to use arrays as keys in a HashMap. >>> [quoted text clipped - 19 lines] > 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 28 lines] > 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? Actually, the difference would be between ArrayList and Map (probably HashMap) ArrayList wouldn't require the 1 key to 1 value like a map would. > Only for > reading, I see no point in using a List. > > H. Signaturetrippy 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" >> >>I want to use arrays as keys in a HashMap. >> > [quoted text clipped - 20 lines] > 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 Hendrik Maryns schrieb: > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 11 lines] > > 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; >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. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > You can't use arrays literally as keys. Sure you can. > You need sensible equals and > hashCode for them. Object provides equals() and hashCode() methods that meet all the technical requirements. > Absolute identity is probably not what you want. It is not uncommon for me to use Maps where object identity is exactly the right choice for my keys -- such a map associates values with specific key objects (object semantics). On the other hand, it may be more typical in general to use keys that have value semantics, such as Strings and Integers. In that case the map can be considered as associating values with whatever things the key objects /represent/; as a result, you can retrieve each value with any equivalent representation of the underlying word, number, or whatever that constitutes its logical key. Both uses have their places. > So you must embed you array in a class that lets you override those > two methods. If you want value semantics, then that's probably the most straightforward way to go about it. For what it's worth, it appears that the OP does want value semantics, and I agree that embedding his arrays in wrapper objects would be the approach I would consider first. SignatureJohn Bollinger jobollin@indiana.edu On Fri, 17 Feb 2006 21:44:41 -0500, "John C. Bollinger" <jobollin@indiana.edu> wrote, quoted or indirectly quoted someone who said : >It is not uncommon for me to use Maps where object identity is exactly >the right choice for my keys -- such a map associates values with >specific key objects (object semantics) If you index by identity, you need the object itself to feed in as the retrieval key. So what's the point of looking it up if you already have it? You would not use this to find the objects matched by identity themselves,, but to find other unrelated associated objects, that the key object does not link to, only by Map membership. It would be like insisting on canonical interned strings for all your HashMap lookup keys. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > On Fri, 17 Feb 2006 21:44:41 -0500, "John C. Bollinger" > <jobollin@indiana.edu> wrote, quoted or indirectly quoted someone who [quoted text clipped - 14 lines] > It would be like insisting on canonical interned strings for all your > HashMap lookup keys. One case where I've used object identity as a key for maps was for annotating trees for a compiler. The source code for the nodes of tree were generated, so I didn't want to edit their source code and add in attributes that way. So I make the nodes the keys in my map, and add annotations for symbol-table construction and type checking as values. Two nodes, representing the token "x" might be exactly equal in all their attributes, but may be conceptually considered different, due to their position in the tree. One such "x" may be a local variable, while another one is a method parameter. So in cases like these, you really want identity, and not just equality. - Oliver -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 NotDashEscaped: You need GnuPG to verify this message Finomosec schreef: > Hendrik Maryns schrieb: >> -----BEGIN PGP SIGNED MESSAGE----- [quoted text clipped - 18 lines] > > 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. SignatureHendrik Maryns ================== www.lieverleven.be http://aouw.org > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA1 [quoted text clipped - 9 lines] > 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 > 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 >> 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 [quoted text clipped - 5 lines] > > 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 > 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. [Warning: I'm going to make up terminology here -- strong identity, weak identity, and confused identity -- because I don't think there is widely accepted terminology in use throughout the Java programming language to describe these concepts.] A key should be a key. It ought to be just as complex as it needs to be for the application. If I need to look up records that match an array, then I ought to use an array for a key. The problem here, as I see it, is that HashMap doesn't work well (or at a minimum, is dangerous) with keys that have confused identities. An object with a confused identity is an object whose logical identity may change throughout its lifetime; loosely speaking, an object that overrides equals and hashCode in such a way that they may change through its lifetime. I advocate avoiding objects with confused identities whenever possible... but certain APIs such as the main Collections API interfaces require confused identity. Note that arrays themselves work just fine as keys. It's just necessary to first recognize that they have strong identity; changing the contents doesn't change who they are, and the same contents don't make two different arrays equal to each other. Similarly, objects with weak identity make fine HashMap keys, regardless of their complexity, so long as they represent the information that you really want to use as a key. Instances of the List or Map interfaces, though, do not work well as keys unless they are immutable, since mutable collections are required to have confused identities. Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation >> 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 [quoted text clipped - 5 lines] > The problem here, as I see it, is that HashMap doesn't work well (or at > a minimum, is dangerous) with keys that have confused identities. Well, it seems like you have a different view of it than I have. I prefer to keep things as minimalistic and as simple as possible, thats the way I have found to keep the bug count close to zero and a high degree of autonomy and maintainability on the servers I have created. If you have a different approach, please share. I would love to hear other ways of doing it. /tom > Well, it seems like you have a different view of it than I have. > [quoted text clipped - 3 lines] > you have a different approach, please share. I would love to hear other > ways of doing it. The point that any necessary complexity can be encapsulated behind the contract for Object.equals and Object.hashCode. Somewhat recently, for example, I wrote some code (I'm leaving out some details to prevent this post from getting too long) where I needed to keep a Map<Graph,Strategy> where Graph is a directed graph in the conventional sense, and Strategy encapsulates a series of transformations that may be performed on that graph. A user would look up a graph and be given certain options for transformation. The result of the transformation might then be looked up again, resulting in a few further options. Now, I don't think too many people would consider a digraph to be a minimalistic data structure... but it's what I needed to look up in the structure. The Graph class was immutable, and tied to Strategy so that graphs were manipulated by Strategy objects that return a different Graph as a result. Graph encapsulated the lookup simply by being able to calculate a consistent hash code for any graph, and being able to compare itself against another class for equality. Implementing those things wasn't exactly trivial (though not really hard, either), but once it was done, the HashMap data structure worked fine, of course. Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation > The point that any necessary complexity can be encapsulated behind the > contract for Object.equals and Object.hashCode. Just because you have a contract about an interface, and it can be kept constant, does not mean that the code behind it needs to be as complicated as you can manage, or want to, create it. Thats the key to low complexity/high maintainability code. > Somewhat recently, for > example, I wrote some code (I'm leaving out some details to prevent this > post from getting too long) where I needed to keep a Map<Graph,Strategy> > where Graph is a directed graph in the conventional sense, and Strategy > encapsulates a series of transformations that may be performed on that > graph. I am not in a position to say if that was the best way to do it. But of course, its an intriguing way of doing it. But does it solve the low complexity/high maintainability equation? Have you needed to change things because of bugs or any other unforeseen design-/problems? /tom > > The point that any necessary complexity can be encapsulated behind the > > contract for Object.equals and Object.hashCode. [quoted text clipped - 3 lines] > complicated as you can manage, or want to, create it. Thats the key to > low complexity/high maintainability code. Can you solve that problem with less complexity, or do you just move the complexity elsewhere? Somewhere, you've got to have code that compares two graphs for equality. The hash code is, of course, an optimization to avoid a linear search... but it's an even more welcome optimization when the graphs are so expensive to compare. > I am not in a position to say if that was the best way to do it. But of > course, its an intriguing way of doing it. But does it solve the low > complexity/high maintainability equation? Have you needed to change > things because of bugs or any other unforeseen design-/problems? Since I wrote the code two weeks ago and it's not used in production, it doesn't really mean much that I haven't seen any bugs. But no, I haven't seen any bugs. Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation >>> The point that any necessary complexity can be encapsulated behind the >>> contract for Object.equals and Object.hashCode. [quoted text clipped - 8 lines] > to avoid a linear search... but it's an even more welcome optimization > when the graphs are so expensive to compare. Of course somewhere you have to have the logic to perform the operations you need done. And using equals() to initiate a comparison of two graphs is as good as any. But, using a hash code of the graph as a unique identifier of the graph is not the way to go, as you then have to take into consideration many factors that are quite complex, such as - the complexity of the graph, - a correct algorithm to produce a representative hash code for the type and complexity of the graph, - accuracy of the representation, - collision rate of the hash code - distribution properties of the hash code, when considering the accuracy, collision rate etc I would try to look for another piece of simple information about a graph that can be used as a unique identifier. /tom > Similarly, objects with weak >identity make fine HashMap keys, regardless of their complexity, so long >as they represent the information that you really want to use as a key. That is a mindbending idea, using an array as an effectively immutable and unique key for HashMap lookup even though the values of the elements themselves change. If you do this, you had better write a paragraph of explanation with circles and arrows. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. On Sat, 18 Feb 2006 13:29:15 GMT, Roedy Green <my_email_is_posted_on_my_website@munged.invalid> wrote, quoted or indirectly quoted someone who said : >That is a mindbending idea, using an array as an effectively immutable >and unique key for HashMap lookup even though the values of the >elements themselves change. > >If you do this, you had better write a paragraph of explanation with >circles and arrows. If I were implementing that I think I would put the array in a wrapper object even if just to help maintenance programmers understand that the object itself has its own identity that is preserved even though the elements change. I would also put in the hashCode and equals methods even if they just called super with an explanation that was intentional. You DON'T want them looking at the individual array elements. Otherwise someone will be tempted to "fix" your code by adding a "proper" equals method. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > That is a mindbending idea, using an array as an effectively immutable > and unique key for HashMap lookup even though the values of the > elements themselves change. > > If you do this, you had better write a paragraph of explanation with > circles and arrows. It's definitely not a common way to use a plain array. The point is that it works fine, and the complexity of the object's state makes it no more likely to fail. Explanation is necessary, I agree... though I don't see the utility of circles or arrows. Signaturewww.designacourse.com The Easiest Way To Train Anyone... Anywhere. Chris Smith - Lead Software Developer/Technical Trainer MindIQ Corporation > though I >don't see the utility of circles or arrows. It was a reference to an Arlo Guthrie song, Alice's restaurant. SignatureCanadian Mind Products, Roedy Green. http://mindprod.com Java custom programming, consulting and coaching. > > though I > >don't see the utility of circles or arrows. > > It was a reference to an Arlo Guthrie song, Alice's restaurant. They are getting younger every day, Roedy. I feel your pain :-) >> > though I >> >don't see the utility of circles or arrows. >> >> It was a reference to an Arlo Guthrie song, Alice's restaurant. > > They are getting younger every day, Roedy. I feel your pain :-) I made a poster to display on the door of my office: A snarling Dick Cheney, captioned "Seven hunters, two game wardens, and a cow". Many people have complimented me on how funny it is, and then asked "Why a cow?" > That is a mindbending idea, using an array as an effectively immutable > and unique key for HashMap lookup even though the values of the > elements themselves change. > > If you do this, you had better write a paragraph of explanation with > circles and arrows. Or use an IdentityHashMap. Signature======================================================================== Ian Pilcher i.pilcher@comcast.net ======================================================================== Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
Reply to this Message
|
 Sign In
 Join
 My Latest Posts My Monitored Threads My Blog My Photo Gallery My Profile My Homepage Start New Thread Enable EMail Alerts Rate this Thread
|
©2009 Advenet LLC Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.