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

Question

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

score 3 · Answer 1 · answered Mar 06 '15 at 15:46

3

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.

answered Mar 06 '15 at 15:46

Necreaux

9,451
7
26
43

This is the right approach. Also, the hash code for the string is cached once it is calculated, so there's no extra cost to calling `hashcode()` multiple times for the same string. The only problem would be if OP is stuck with a protocol that requires using a `long` as an alias for the name. – Ted Hopp Mar 06 '15 at 17:15

score 0 · Answer 2 · edited May 23 '17 at 12:14

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.
A Map will be faster (O(1) if you use containsKey, opposed to an Array iteration, which can be between O(n) and O(n²) 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

score 0 · Answer 3 · edited May 23 '17 at 11:58

0

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

edited May 23 '17 at 11:58

Community

1
1

answered Mar 06 '15 at 15:56

Dhananjaya

1,510
2
14
19

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

3 Answers3