Win a copy of Programmer's Guide to Java SE 8 Oracle Certified Associate (OCA) this week in the OCAJP forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Advice on building HashMap

 
Sophie Sperner
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
In Java, I have a sequence of unique numbers 0,...,n. I use them as keys to keep arrays in a hashmap like this: HashMap<Integer, int[]> map. So map.get(key), 0 <= key <= n will give an array of ints.

Now I have a problem: create HashMap<Pair<Integer, Integer>, int[]> map2 where Pair<Integer, Integer> is ordered pair of key1 and key2 such that 0 <= key1 < key2 <= n and having this pair as a unique new key, we will store say a union of map.get(key1) and map.get(key2) arrays.

My problem is that I do not understand how HashMap works and how to create those keys for map2? Should keys as pairs in map2 be unique? If not, then the concept of buckets inside map2 is totally missing.. Could you please advise.

One idea is to use String keypair = key1.toString() + key2.toString(). But then all keys will be unique and will it be efficient to use such HashMap<String, int[]> ?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sophie Sperner wrote:
Now I have a problem: create HashMap<Pair<Integer, Integer>, int[]> map2 where Pair<Integer, Integer> is ordered pair of key1 and key2 such that 0 <= key1 < key2 <= n [/code]and having this pair as a unique new key, we will store say a union of map.get(key1) and map.get(key2) arrays.

My problem is that I do not understand how HashMap works and how to create those keys for map2?


You define your Pair class with its hashCode() and equals() method just like you would for any other class. If you're not sure how to write hashCode() and equals(), here's a good general-purpose approach: http://books.google.com/books?id=Ft8t0S4VjmwC&pg=PA33&source=gbs_toc_r&cad=4#v=onepage&q&f=false

Should keys as pairs in map2 be unique?


The keys of a Map are always unique, by definition. I'm not sure what you're really asking here.

If not, then the concept of buckets inside map2 is totally missing..


No clue what you're saying here.


 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Just as a guess, it might be that you're thinking that hashCodes are supposed to be unique. That's not a requirement, and in fact, by the pigeonhole principle, it's impossible. There will be collisions, but a good hashing algorithm will distribute the hashCode values evenly across the domain of possible (or likely) object states.
 
Sophie Sperner
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
So if I have a class


it will be fine for building a HashMap<Pair, int[]> map ?

And then since every Pair is unique ordered pair of two numbers, then keys for the map will be unique too, is everything correct here?
 
James Boswell
Bartender
Posts: 1051
5
Chrome Eclipse IDE Hibernate
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sophie

You haven't overridden the equals method here.

The signature of equals is above.
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sophie Sperner wrote:So if I have a class


it will be fine for building a HashMap<Pair, int[]> map ?


No. You have not overridden equals() and hashCode(). You have provided similar methods, but to override, they must have the same name and argument list, and it's also required that overriding methods return the same type or a subtype as the parent implementation.

So you need


If you add the @Override notation to declarations of methods you're intending to override, the compiler will give you and error if you're not actually overriding something:



You should probably read that link I provided, and/or google for java equals hashCode example.
 
James Boswell
Bartender
Posts: 1051
5
Chrome Eclipse IDE Hibernate
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sophie

Using the @Override annotation will help here. The compiler will complain if you do not specify the right method signature.
 
James Boswell
Bartender
Posts: 1051
5
Chrome Eclipse IDE Hibernate
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Doh, just posted before I saw your update Jeff!
 
Sophie Sperner
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


Now I changed equals() and hashCode() to have the proper signature.

If I do:


Let I have added all the ordered pairs like (1, 5) and (2, 4) above for some n = 10. Now, what I'm wondering, that pairs (1, 5) and (2, 4) have the same hashCode. Some said it is fine. Could you please explain me on this simple example how buckets will be formed and if I did everything correctly?
 
Jeff Verdegan
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sophie Sperner wrote:


1. Don't try to get fancy with stuff like caching your hashCode value. Computing a hashCode from 2 ints is very fast. And in the general case, -1 is a possible valid value, so using it as a "not yet computed" flag is a code smell.

2. Just adding the keys is a poor hash algorithm. Once again, I recommend you read Bloch's advice at the link I provided earlier.


Let I have added all the ordered pairs like (1, 5) and (2, 4) above for some n = 10. Now, what I'm wondering, that pairs (1, 5) and (2, 4) have the same hashCode. Some said it is fine. Could you please explain me on this simple example how buckets will be formed and if I did everything correctly?


Here.

I think Java's HashMap used closed addressing, where the hashCode is further hashed to produce a bucket, which is a List or array, and which is then linearly searched for the value in question using equals().

hashCode() finds the bucket, and equals() finds the object in that bucket.
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic