| 337 |
|
values = null; |
| 338 |
|
descendingEntrySet = null; |
| 339 |
|
descendingKeySet = null; |
| 340 |
< |
randomSeed = (int) System.nanoTime(); |
| 340 |
> |
randomSeed = ((int) System.nanoTime()) | 1; // ensure nonzero |
| 341 |
|
head = new HeadIndex<K,V>(new Node<K,V>(null, BASE_HEADER, null), |
| 342 |
|
null, null, 1); |
| 343 |
|
} |
| 893 |
|
* Returns a random level for inserting a new node. |
| 894 |
|
* Hardwired to k=1, p=0.5, max 31. |
| 895 |
|
* |
| 896 |
< |
* This uses a cheap pseudo-random function that according to |
| 897 |
< |
* http://home1.gte.net/deleyd/random/random4.html was used in |
| 898 |
< |
* Turbo Pascal. It seems the fastest usable one here. The low |
| 899 |
< |
* bits are apparently not very random (the original used only |
| 900 |
< |
* upper 16 bits) so we traverse from highest bit down (i.e., test |
| 901 |
< |
* sign), thus hardly ever use lower bits. |
| 896 |
> |
* This uses the simplest of the generators described in George |
| 897 |
> |
* Marsaglia's "Xorshift RNGs" paper. This is not a high-quality |
| 898 |
> |
* generator but is acceptable here. Note that bits are checked |
| 899 |
> |
* by testing sign, which is a little faster than testing low bit. |
| 900 |
|
*/ |
| 901 |
|
private int randomLevel() { |
| 902 |
|
int level = 0; |
| 903 |
|
int r = randomSeed; |
| 904 |
< |
randomSeed = r * 134775813 + 1; |
| 904 |
> |
int x = r ^ (r << 13); |
| 905 |
> |
x ^= x >>> 17; |
| 906 |
> |
randomSeed = x ^ (x << 5); |
| 907 |
|
if (r < 0) { |
| 908 |
|
while ((r <<= 1) > 0) |
| 909 |
|
++level; |
