a better hash function for ChunkCoordIntPair

[AartBluestoke]

at the moment the hash code is

ChunkCoordIntPair.java line 27 public int hashCode() { long var1 = func_77272_a(this.field_77276_a, this.field_77275_b); int var3 = (int)var1; int var4 = (int)(var1 >> 32); return var3 ^ var4; } which is equal to the xcoord ^ ycoord, because func_77272_a simply bitshifts the int up to make it a long, in an inefficient way (the &'s do nothing). public static long func_77272_a(int p_772720, int p_772721) { return (long)p_772720 & 4294967295L | ((long)p_772721 & 4294967295L) << 32; } the problem with this hash is if both x and y are even, and you add 1 to each, you end up with the same hash. This makes the hashmap for fetching chunks very inefficient.

this should be replaced with public int hashCode() { return 32767 (func_77272_a^(func_77272_a>>>16))+field_77275_b^(field_77275_b>>>16); } which mostly places the xcoord in the upper 16 bits, while placing the zcoord in the lower 16 bits, for a much more pseudo random hash. (32767 = 2^16-1 ; this means that adjacent chunks will be well distributed over all any power-of-2 sided array )

[AbrarSyed]

if implemented.. this may have the effect of breaking MC chunkloading dontcha think?

[cpw]

Why do you think Abrar?

[AbrarSyed]

I guess I misread it a bit.. it doesn't change the way the hascodes are calculated.. just a more efficient way of doing the same thing.. I was under the impression that after this PR, the hascodes would be diferent.

:) ignore me.

[AartBluestoke]

this patch doesn't modify how chunks are saved or loaded, just the place in the internal hashmap that they are stored once loaded (before my initial post i implemented this in my mcp install, and a world created pre-hash-update loaded correctly with this patch).

at the moment the hashcode function is x xor z, which means from an even x and y, increasing both x,z+1 and x+1,z creates the same hash, so all chunks have a hash collision with a chunk diagonal to them, in some direction. Hash collisions make hashmaps slow.

the hashcode for row x roughly picks numbers every x apart, with y being sequential - this means that any square block will have a roughly even distribution over the entire area of the hash table. with a hashtable of 2(power)n, no chunks closer than n will have a collision, and i think that every chunk +- x,z 2(power)14 has a unique hash.

because of the *2(power)16-1, this don't behave in the same way as x(xor)z, because 2(power)16-1 isn't a multiple of the hash table size.

edit: confusion between ^ being power and bit-wise xor.

[AbrarSyed]

ah.. so fixing this would fix the farlands and stuff :)

[AartBluestoke]

sorry, no, again, the only thing this does is increase the cpu efficiency of the in memory storage of chunks - it doesn't change any game-play.

world.getBlock() will probably run a fair bit quicker with this patch -

return 32767 * func_77272_a+field_77275_b;

would probably work just as well, except that chunks near at 32k would cause extra hash collisions with those near 0. (either way this is better than the current solution where every chunk has a hash collision nearby)

[AbrarSyed]

/me will just keep his mouth shut about things he doesn't understand now.

[cpw]

I think an optimization like this is going into forge. tentatively closing this.