FULL PRODUCT VERSION :
java version "1.6.0_17"
Java(TM) SE Runtime Environment (build 1.6.0_17-b04)
Java HotSpot(TM) Server VM (build 14.3-b01, mixed mode)

ADDITIONAL OS VERSION INFORMATION :
Fedora 12 Linux

A DESCRIPTION OF THE PROBLEM :
The randomLevel method:

    /**
     * Returns a random level for inserting a new node.
     * Hardwired to k=1, p=0.5, max 31 (see above and
     * Pugh's "Skip List Cookbook", sec 3.4).
     *
     * This uses the simplest of the generators described in George
     * Marsaglia's "Xorshift RNGs" paper. This is not a high-quality
     * generator but is acceptable here.
     */
    private int randomLevel() {
        int x = randomSeed;
        x ^= x << 13;
        x ^= x >>> 17;
        randomSeed = x ^= x << 5;
        if ((x & 0x8001) != 0) // test highest and lowest bits
            return 0;
        int level = 1;
        while (((x >>>= 1) & 1) != 0) ++level;
        return level;
    }

uses "if ((x & 0x8001) != 0) // test highest and lowest bits" to short cut testing the bits, however it is using a short instead of an integer for the bitwise and, which will cause the max return value to be 15 and not 31.

It should be using 0x800000001

If a large number of values are inserted into the map, this bug can reduce performance.


REPRODUCIBILITY :
This bug can be reproduced always.