int index = insertNewKey(key, keyHash);                    values[index] = oldValues[i];                    --remaining;                }            }        }    }// Ensure key index creating one if necessary    private int ensureIndex(Object key) {        int hash = key.hashCode();        int index = -1;        int firstDeleted = -1;        if (keys != null) {            int fraction = hash * A;            index = fraction >>> (32 - power);            Object test = keys[index];            if (test != null) {                int N = 1 << power;                if (test == key                    || (values[N + index] == hash && test.equals(key)))                {                    return index;                }                if (test == DELETED) {                    firstDeleted = index;                }                // Search in table after first failed attempt                int mask = N - 1;                int step = tableLookupStep(fraction, mask, power);                int n = 0;                for (;;) {                    if (check) {                        if (n >= occupiedCount) Kit.codeBug();                        ++n;                    }                    index = (index + step) & mask;                    test = keys[index];                    if (test == null) {                        break;                    }                    if (test == key                        || (values[N + index] == hash && test.equals(key)))                    {                        return index;                    }                    if (test == DELETED && firstDeleted < 0) {                        firstDeleted = index;                    }                }            }        }        // Inserting of new key        if (check && keys != null && keys[index] != null)            Kit.codeBug();        if (firstDeleted >= 0) {            index = firstDeleted;        }        else {            // Need to consume empty entry: check occupation level            if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {                // Too litle unused entries: rehash                rehashTable();                return insertNewKey(key, hash);            }            ++occupiedCount;        }        keys[index] = key;        values[(1 << power) + index] = hash;        ++keyCount;        return index;    }    private void writeObject(ObjectOutputStream out)        throws IOException    {        out.defaultWriteObject();        int count = keyCount;        for (int i = 0; count != 0; ++i) {            Object key = keys[i];            if (key != null && key != DELETED) {                --count;                out.writeObject(key);                out.writeInt(values[i]);            }        }    }    private void readObject(ObjectInputStream in)        throws IOException, ClassNotFoundException    {        in.defaultReadObject();        int writtenKeyCount = keyCount;        if (writtenKeyCount != 0) {            keyCount = 0;            int N = 1 << power;            keys = new Object[N];            values = new int[2 * N];            for (int i = 0; i != writtenKeyCount; ++i) {                Object key = in.readObject();                int hash = key.hashCode();                int index = insertNewKey(key, hash);                values[index] = in.readInt();            }        }    }// A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)// See Knuth etc.    private static final int A = 0x9e3779b9;    private static final Object DELETED = new Object();// Structure of kyes and values arrays (N == 1 << power):// keys[0 <= i < N]: key value or null or DELETED mark// values[0 <= i < N]: value of key at keys[i]// values[N <= i < 2*N]: hash code of key at keys[i-N]    private transient Object[] keys;    private transient int[] values;    private int power;    private int keyCount;    private transient int occupiedCount; // == keyCount + deleted_count// If true, enables consitency checks    private static final boolean check = false;/* TEST START    public static void main(String[] args) {        if (!check) {            System.err.println("Set check to true and re-run");            throw new RuntimeException("Set check to true and re-run");        }        ObjToIntMap map;        map = new ObjToIntMap(0);        testHash(map, 3);        map = new ObjToIntMap(0);        testHash(map, 10 * 1000);        map = new ObjToIntMap();        testHash(map, 10 * 1000);        map = new ObjToIntMap(30 * 1000);        testHash(map, 10 * 100);        map.clear();        testHash(map, 4);        map = new ObjToIntMap(0);        testHash(map, 10 * 100);    }    private static void testHash(ObjToIntMap map, int N) {        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i);            check(-1 == map.get(key, -1));            map.put(key, i);            check(i == map.get(key, -1));        }        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i);            map.put(key, i);            check(i == map.get(key, -1));        }        check(map.size() == N);        System.out.print("."); System.out.flush();        Object[] keys = map.getKeys();        check(keys.length == N);        for (int i = 0; i != N; ++i) {            Object key = keys[i];            check(map.has(key));        }        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i);            check(i == map.get(key, -1));        }        int Nsqrt = -1;        for (int i = 0; ; ++i) {            if (i * i >= N) {                Nsqrt = i;                break;            }        }        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i * i);            map.put(key, i);            check(i == map.get(key, -1));        }        check(map.size() == 2 * N - Nsqrt);        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i * i);            check(i == map.get(key, -1));        }        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(-1 - i * i);            map.put(key, i);            check(i == map.get(key, -1));        }        check(map.size() == 3 * N - Nsqrt);        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(-1 - i * i);            map.remove(key);            check(!map.has(key));        }        check(map.size() == 2 * N - Nsqrt);        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i * i);            check(i == map.get(key, -1));        }        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i);            int j = intSqrt(i);            if (j * j == i) {                check(j == map.get(key, -1));            }else {                check(i == map.get(key, -1));            }        }        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i * i);            map.remove(key);            check(-2 == map.get(key, -2));        }        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i);            map.put(key, i);            check(i == map.get(key, -2));        }        check(map.size() == N);        System.out.print("."); System.out.flush();        for (int i = 0; i != N; ++i) {            Object key = testKey(i);            check(i == map.get(key, -1));        }        System.out.print("."); System.out.flush();        ObjToIntMap copy = (ObjToIntMap)writeAndRead(map);        check(copy.size() == N);        for (int i = 0; i != N; ++i) {            Object key = testKey(i);            check(i == copy.get(key, -1));        }        System.out.print("."); System.out.flush();        checkSameMaps(copy, map);        System.out.println(); System.out.flush();    }    private static void checkSameMaps(ObjToIntMap map1, ObjToIntMap map2) {        check(map1.size() == map2.size());        Object[] keys = map1.getKeys();        check(keys.length == map1.size());        for (int i = 0; i != keys.length; ++i) {            check(map1.get(keys[i], -1) == map2.get(keys[i], -1));        }    }    private static void check(boolean condition) {        if (!condition) Kit.codeBug();    }    private static Object[] testPool;    private static Object testKey(int i) {        int MAX_POOL = 100;        if (0 <= i && i < MAX_POOL) {            if (testPool != null && testPool[i] != null) {                return testPool[i];            }        }        Object x = new Double(i + 0.5);        if (0 <= i && i < MAX_POOL) {            if (testPool == null) {                testPool = new Object[MAX_POOL];            }            testPool[i] = x;        }        return x;    }    private static int intSqrt(int i) {        int approx = (int)Math.sqrt(i) + 1;        while (approx * approx > i) {            --approx;        }        return approx;    }    private static Object writeAndRead(Object obj) {        try {            java.io.ByteArrayOutputStream                bos = new java.io.ByteArrayOutputStream();            java.io.ObjectOutputStream                out = new java.io.ObjectOutputStream(bos);            out.writeObject(obj);            out.close();            byte[] data = bos.toByteArray();            java.io.ByteArrayInputStream                bis = new java.io.ByteArrayInputStream(data);            java.io.ObjectInputStream                in = new java.io.ObjectInputStream(bis);            Object result = in.readObject();            in.close();            return result;        }catch (Exception ex) {            throw new RuntimeException("Unexpected");        }    }// TEST END */}