Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (581)
games submitted by our members
Games in WIP (500)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Better HashMap keys  (Read 1791 times)
0 Members and 1 Guest are viewing this topic.
Offline Yemto

Junior Member


Exp: 3 years



« Posted 2013-09-27 17:09:31 »

I use to store much in hashmap since it's fast and easy to do. But my HashMap keys are really bad. Normally I have something like. String key = x + "." + y + "." + z; to make sure every object have it's own key.I have been thinking of using << and .hashCode() instead. But I have no idea if that's a good way to do it if I want unique keys.

Example
1  
2  
int locationKey = x << y << z;
int recoloredSpriteKey = img.hashCode() << color.hashCode();
Offline DrZoidberg

Senior Member


Medals: 10



« Reply #1 - Posted 2013-09-27 19:55:00 »

You could create a Point3D class and give it a hashCode method.

Here is the source code for java.awt.geom.Point2D.hashCode, maybe that will help you.
1  
2  
3  
4  
5  
public int hashCode() {
    long bits = java.lang.Double.doubleToLongBits(getX());
    bits ^= java.lang.Double.doubleToLongBits(getY()) * 31;
    return (((int) bits) ^ ((int) (bits >> 32)));
}
Offline Roquen
« Reply #2 - Posted 2013-09-27 21:51:29 »

Call me crazy...but maybe think about using a hashing function? Tongue

MurmurHash2 is a reasonable choice for speed vs. quality.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Yemto

Junior Member


Exp: 3 years



« Reply #3 - Posted 2013-09-28 00:15:51 »

Call me crazy...but maybe think about using a hashing function? Tongue

MurmurHash2 is a reasonable choice for speed vs. quality.

What do you mean "speed vs. quality" what I want is generate a unique number from x, y, z.
Offline Roquen
« Reply #4 - Posted 2013-09-28 19:30:55 »

You can't...you can only get close.  Read up on hashing.
Offline Yemto

Junior Member


Exp: 3 years



« Reply #5 - Posted 2013-09-29 19:51:14 »

Sorry. Maybe I don't simply get it or something... but it doesn't really make sense to me - what You want to do.
HashMap stores key - value pairs, where the key can be any type. So why do You create a String hash in order to use it as a key? It clearly seems that there You have x, y and z coordinates, so why not just use for example Vector3 class as the key type in HashMap? That's what the HashMap is designed for.

No you clearly don't get it, and it's so simple. I created this topic to get help with my keys in HashMap, since I knew I didn't need to use Strings as keys, but I didn't know how to create a good key with numbers, since x + y + z wouldn't work.

Also, The are no Vector3, Vector3d, or Vector3D in java2D, so I couldn't possibly know about it. Now when I do i need something that works in java2D
Offline Grunnt

JGO Wizard


Medals: 55
Projects: 9
Exp: 5 years


Complex != complicated


« Reply #6 - Posted 2013-09-29 20:17:37 »

How about making a custom key class, something like a Vector3?

There's an excellent example of this on StackOverflow:
http://stackoverflow.com/questions/15190074/container-with-xyz-key

Just use this as your key, doesn't get much more elegant.

Offline Roquen
« Reply #7 - Posted 2013-09-29 22:20:02 »

Trust me.  Use MurmurHash2.  Or if the number of entries is insured to be small, then use Bernsteins.  Call it a day and move on.

DO NOT MAKE UP YOUR OWN.  TOSSING FUNCTIONS OF PRIME NUMBERS TOGETHER WILL SUCK.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2013-09-30 01:31:55 »

persecutioncomplex

Cute girl wants to do groceries with car.
Cute girl has no car.
Cute girl goes to car dealer to purchase said car.
Car dealer chats about cilinder volume.
Car dealer warns about CO levels in city traffic.
Car dealer strongly suggests to buy a hybrid.
Cute girl points at pink car.
Car dealer BEGINS TO SHOUT MORE WARNINGS.
Cute girl walks off confused.
Cute girl is wondering how to get those groceries home.
Car dealer didn't make a sale - despite his expertise.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline opiop65

JGO Kernel


Medals: 124
Projects: 7
Exp: 3 years


Team Alluminum


« Reply #9 - Posted 2013-09-30 01:46:55 »

That... That was very clever.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Grunnt

JGO Wizard


Medals: 55
Projects: 9
Exp: 5 years


Complex != complicated


« Reply #10 - Posted 2013-09-30 08:49:34 »

I am curious why the solution I proposed "sucks". Of course making the class immutable would be (much) better, i.e. see below:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
public class Vector3Key {
    private final int x, y, z;

    public void Vertex(int x, int y, int z){
        this.x = x;
        this.y = y;
        this.z = z;
    }

    public boolean equals(Object o){
        if(this == o) return true;
        if(!(o instanceof Vertex)) return false;
        Vertex v = (Vertex)o;
        return x == v.x && y == v.y && z == v.z;
    }

    public int hashCode(){
        //  Use whatever prime numbers you like
       return x ^ y * 137 ^ z * 11317;
    }
}


I can also imagine that the hashCode generated would be sub-optimal with regards to some mathematical properties, e.g. distribution or the number of collisions (had to read up on this). Are these mathematical properties the reason to use a hash library such as Murmur?

Also, I kind of see how the function above might not solve the OP's problem as I can imagine the positions of objects would change, which may result in undefined behaviour for Java Hash collections.

Offline cylab

JGO Knight


Medals: 34



« Reply #11 - Posted 2013-09-30 10:13:19 »

Normally I have something like. String key = x + "." + y + "." + z; to make sure every object have it's own key.

Actually I would call it good enough, if it doesn't create a problem for you. You may use a StringBuilder to reduce created temporary Strings when doing String concatenation with +
1  
2  
3  
StringBuilder keyBuilder=new StringBuilder();
keyBuilder.append(x).append('.').append(y).append('.').append(z);
String key=keyBuilder.toString();


If you are sure you are using the StringBuilder from the same thread only, then you can even cache and reuse it when calling setLength(0) before:
1  
2  
3  
4  
5  
static final StringBuilder keyBuilder=new StringBuilder();
(...)
keyBuilder.setLength(0);
keyBuilder.append(x).append('.').append(y).append('.').append(z);
String key=keyBuilder.toString();


1  
2  
int locationKey = x << y << z;
int recoloredSpriteKey = img.hashCode() << color.hashCode();


Using primitives as keys is a bad idea, because it will lead to a lot of autoboxing while using the hashmap (the java buildin Map implemtations need Objects as keys, so they will convert ints to Integers and back as needed, causing a lot of short lived objects and therefore garbage collection runs)

Other than that, the << operator shifts the left argument bitwise by the value of the right argument wrapping around, so what you listed above probably won't work, since e.g 64 shifted by 40 would result in the same key like 128 shifted by 39 etc.

So if you want to use this approachm you would need to go for something like
1  
2  
int locationKey = x*MAXIMUM_Y + y*MAXIMUM_Z + z;
int recoloredSpriteKey = img.someId * (256^3) + color.r*(256^2) + color.g*256 + color.b;


As you can see, your img-ids are limited to 256 values now and if you want to get the alpha value into the key, you are screwed anyway (or need to switch to long).

Now here comes, why lukasz1985 don't get your question. You didn't explain the use-case for which you need this key and the hashmap. If you want them for managing your objects, then you will probably be better of by just using names to identify them, because using the coordinates would mean the keys will constantly change when you move your object around the screen. If you don't need the keys for fast retrieval, then there is no point in storing the objects in a HashMap at all...

If you really need to and you want to avoid String keys, then a custom key object like Grunnt posted above would do the trick.

EDIT: And actually overriding the built in Object.hashCode() is a very bad idea - that solution will require that the elements stored is HashSet for example will have to immutable. Actually it's really evil idea....

Maybe this statement is out of context, but overriding the built in Object.hashCode() method (along with the equals() method) is exactly what you need to do when creating custom keys...

DO NOT MAKE UP YOUR OWN.  TOSSING FUNCTIONS OF PRIME NUMBERS TOGETHER WILL SUCK.

Actually I would think it doesn't matter at all, because the amount of objects will be so small in the end that using an array and a brute-force search would be good enough anyway Wink

Mathias - I Know What [you] Did Last Summer!
Offline Roquen
« Reply #12 - Posted 2013-09-30 14:52:47 »

@Riven: The thing is: I don't have any vested interest in anyone listening to me.  If someone does great.

Anyone tempted to toss together their own hashing function I suggest you do the following.  Do a web search for: survey, non-cryptograhic hash...or something similar...grab a research paper and count the number of functions they talk about.  It'll be a really really small number and ask yourself:  With so many programmers and researcher over some many years of computing...why are there so few functions being talked about?  There's a story about Knuth (if you don't know who that it...please go look it up now...thanks) attempting to create a random number generator and it being a massive failure.  This stuff is hard and specialized.

There's no margin is goofying around with it.  Pick an accepted "reasonable" hashing function, use it and call it a day (at least for a 5 years or so) unless you have some specific reason to rethink that choice.

I am curious why the solution I proposed "sucks".

{snip snip}

I can also imagine that the hashCode generated would be sub-optimal with regards to some mathematical properties, e.g. distribution or the number of collisions (had to read up on this). Are these mathematical properties the reason to use a hash library such as Murmur?

Actually I had no clue that anyone here wrote that code.  I glanced at it for less than 2s and closed the window.  Most homebrew hash function look somewhat like this. 

But I think you've answered your own question.  Oddly enough the "mathematical properties" of a hashing function are rather (read: all) important. 

Bob Jenkin's (wrote these hashes) has a good overview:  http://burtleburtle.net/bob/hash/evahash.html (you have to click around a bit)
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #13 - Posted 2013-09-30 15:09:29 »

@Riven: The thing is: I don't have any vested interest in anyone listening to me.  If someone does great.
In my opinion it's of no use to throw expertise at newbies. It both confuses them and actually hurts their learning capability, as they are suddenly confronted with details they can't correctly interpret and will most likely misinterpret as a result, only adding to their confusing.

In this case, the OP doesn't seem to understand hashing and hash maps in the first place, because if your key contains all the information that is stored in the value, you don't need the value, and/or you don't need to lookup anything to start with, because you already have the information you are about to lookup. It's much more expensive (in CPU terms) to generate the key through string concatenation, than it is to create a new Vec3 object, which is even GC friendlier because it only creates one instance, instead of almost half a dozen, for string concat.

So, as always, maybe one shouldn't try to strictly answer the question, but to unravel the problem, which might lead to a much better fitting solution. If the question is wrong, a highly detailed answer, showing your expertise to the world - hoping somebody else entirely will learn from it - won't help anybody.


Having said all that - what is the problem the original poster (Yemto) is trying to solve? I'm sure it has very little, if anything, to do with hashing, let alone picking the best hashing algorithm.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #14 - Posted 2013-09-30 15:29:29 »

@Riven - that indeed is a good point.  I wholeheartedly endorse your post.
Offline Grunnt

JGO Wizard


Medals: 55
Projects: 9
Exp: 5 years


Complex != complicated


« Reply #15 - Posted 2013-09-30 18:23:31 »

Having said all that - what is the problem the original poster (Yemto) is trying to solve? I'm sure it has very little, if anything, to do with hashing, let along picking the best hashing algorithm.

Haha, Riven, I'm impressed by your wisdom Grin I'm even quite serious. You sound like Yoda.

It's one of the things I find hardest to do: take good time to look at the problem, instead of starting to thing in solutions right away.. This thread may be a good example... So what IS Yemto trying to achieve with his/her HashMap? I have no clue really... To make it easy to locate objects by location? Just for shits and giggles? Heh. I'm curious though, so maybe Yemto can enlighten us.

Offline Grunnt

JGO Wizard


Medals: 55
Projects: 9
Exp: 5 years


Complex != complicated


« Reply #16 - Posted 2013-09-30 18:24:43 »

Actually I had no clue that anyone here wrote that code.

Ah, sorry, I didnt actually write the code, I just linked to it as a proposed solution.

Offline xsvenson
« Reply #17 - Posted 2013-09-30 18:40:40 »

@Riven: The thing is: I don't have any vested interest in anyone listening to me.  If someone does great.
In my opinion it's of no use to throw expertise at newbies. It both confuses them and actually hurts their learning capability, as they are suddenly confronted with details they can't correctly interpret and will most likely misinterpret as a result, only adding to their confusing.

...

Having said all that - what is the problem the original poster (Yemto) is trying to solve? I'm sure it has very little, if anything, to do with hashing, let along picking the best hashing algorithm.

This is very interesting perspective. It's once again the question of giving a fish or teaching to fish, but I have never thought about adding to the confusion with too much, too complex information. When You think about it, it's logical, You need some basic understanding before moving up to the advanced setup.

I bow to Your wisdom, mr Riven.

Anyway, back to the topic, indeed noone has yet asked what the poster is trying to do. Given that he has 'x', 'y' and 'z' even a simple
1  
Object[][][]
might be a better solution than a hashmap.

“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.” - Michael A. Jackson
Offline xsvenson
« Reply #18 - Posted 2013-09-30 19:15:12 »

If You read carefully You will see that most people here asked OP about what he want to achieve. Also - clearly speculating - using a multidimensional array would be very not effective here as HashMap implements many optimization techniques, for example in order to search elements  it uses binary trees - as far as I remember, not mentioning that arrays aren't dynamic.


You asked and Riven asked.
Arrays vs HashMap is irrelevant as the extend of the usage is not defined here. There are different tools for different tasks.

“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.” - Michael A. Jackson
Offline Grunnt

JGO Wizard


Medals: 55
Projects: 9
Exp: 5 years


Complex != complicated


« Reply #19 - Posted 2013-09-30 19:19:40 »

using a multidimensional array would be very not effective here as HashMap implements many optimization techniques

Depends on how you are locating the object. The hashmap mentioned in the OP can basically only be used to locate objects based on their X,Y and Z values. Locating an object in a threedimensional array is actually quite a bit faster in this case (at least I think so, didnt test it but I assume its basically a single instruction directly fetching the value/object) than locating it in a HashMap (which would involve some searching and invoking of hash functions at least). Anyway, this is all TheoryCraft..

Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #20 - Posted 2013-09-30 19:21:52 »

as HashMap implements many optimization techniques, for example in order to search elements  it uses binary trees - as far as I remember.
A HashMap is basically an array of LinkedLists. There is no binary tree, maybe you're confused with TreeMap.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #21 - Posted 2013-09-30 19:25:26 »

O(1)

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Online Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #22 - Posted 2013-09-30 19:32:12 »

The duration of searching a node in a tree, increases with the depth of the tree, therefore you can't have binary trees, or binary searches in general, with constant time performance. Trees generally have O(log n) performance characteristics.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Spasi
« Reply #23 - Posted 2013-09-30 20:07:30 »

As of the latest JDK 8 snapshot, HashMaps now have a "bin of TreeNodes" fallback. It's used when the hash codes are poorly distributed and you end up with too many nodes in a bin.
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (55 views)
2014-04-15 18:08:23

BurntPizza (53 views)
2014-04-15 03:46:01

UprightPath (66 views)
2014-04-14 17:39:50

UprightPath (49 views)
2014-04-14 17:35:47

Porlus (66 views)
2014-04-14 15:48:38

tom_mai78101 (90 views)
2014-04-10 04:04:31

BurntPizza (151 views)
2014-04-08 23:06:04

tom_mai78101 (247 views)
2014-04-05 13:34:39

trollwarrior1 (204 views)
2014-04-04 12:06:45

CJLetsGame (211 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!