File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Performance and the fly likes Advice on building HashMap Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Performance
Bookmark "Advice on building HashMap" Watch "Advice on building HashMap" New topic
Author

Advice on building HashMap

Sophie Sperner
Greenhorn

Joined: Sep 04, 2011
Posts: 3
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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: Sep 04, 2011
Posts: 3
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

Joined: Nov 09, 2011
Posts: 973
    
    5

Sophie

You haven't overridden the equals method here.

The signature of equals is above.
Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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

Joined: Nov 09, 2011
Posts: 973
    
    5

Sophie

Using the @Override annotation will help here. The compiler will complain if you do not specify the right method signature.
James Boswell
Bartender

Joined: Nov 09, 2011
Posts: 973
    
    5

Doh, just posted before I saw your update Jeff!
Sophie Sperner
Greenhorn

Joined: Sep 04, 2011
Posts: 3


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

Joined: Jan 03, 2004
Posts: 6109
    
    6

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.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Advice on building HashMap
 
Similar Threads
Hibernate mapping HashMap to row
Copy tree element from left pane to right pane
determine the input type of the value of the function parameter map
Adding scroll bar
How to remove duplicates values from HashMap