CODEWITHSUNDEEP
javaperformancehashmap
Burak Kayabal
Burak Kayabal

Reputation: 19

HashMap based on a long value, get/put o(1)?

So I have a game where I put the player object into an array after them logging in, I don't have much trouble with it in regards of speeds since I also store the array index of the player but at some systems I do run into trouble, speed-wise.

E.G. One player wants to 'message' the other player, the client sends a packet with the name of the person like an unique long value which then loops over the whole player list array and compares the long value of the name and sends it to the found player afterwards.

My thought to speed this up was create a HashMap which uses Long value as the key to guarantee o(1) look-ups, although this was just a concept and I haven't tried it yet.

(I store the nameHash/long value of name upon login so calculating it wouldn't be a bottleneck)

Would this guarantee me o(1) lookups and is the long value of the string really unique?

The String to long(int64) method ->

public static long toLong(String s) {
    long l = 0L;
    for(int i = 0; i < s.length() && i < 12; i++) {
        char c = s.charAt(i);
        l *= 37L;
        if(c >= 'A' && c <= 'Z') l += (1 + c) - 65;
        else if(c >= 'a' && c <= 'z') l += (1 + c) - 97;
        else if(c >= '0' && c <= '9') l += (27 + c) - 48;
    }
    while(l % 37L == 0L && l != 0L) l /= 37L;
    return l;
}

The game ticks on 600ms and runs with 300/400 players so operations like this really are a bottleneck

Upvotes: 0

Views: 481

Answers (3)

Dhananjaya
Dhananjaya

Reputation: 1615

I agree with Necreaux

In case you want the answer anyway, without any collusion you can have O(1) time complexity, but in java to detect and rectify collisions HashMap also uses the Equals method, and asymptotically you can still say that it's of O(1)

This might help you to find more details

Upvotes: 0

Koshinae
Koshinae

Reputation: 2320

  1. Maps can use Strings as key, pretty fast, it uses the String's hashCode, I think. You also don't have to deal with hashcode collisions, as it handles that internally. There is no collection type that emits internal hash collision errors.
  2. A Map will be faster (O(1) if you use containsKey, opposed to an Array iteration, which can be between O(n) and O(n2) depending your code), but IMHO the more important question is the concurrency needed by your application. You could consider using ConcurrentHashMap if you use this collection from more than one thread.

A short description about how HashMap does work: https://stackoverflow.com/a/18030257/357403

Upvotes: 0

Necreaux
Necreaux

Reputation: 9776

Sounds like you are overthinking it. String already has a hashcode function, so why do you need to reinvent it as a long? You can just add the name as the key in a HashMap directly.

Upvotes: 3

Related Questions