testhashstructures.java

hsql是很有名的嵌入式数据库

/* Copyright (c) 2001-2005, The HSQL Development Group
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * Neither the name of the HSQL Development Group nor the names of its
 * contributors may be used to endorse or promote products derived from this
 * software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL HSQL DEVELOPMENT GROUP, HSQLDB.ORG,
 * OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */


package org.hsqldb.test;

import java.util.Random;

import org.hsqldb.lib.DoubleIntIndex;
import org.hsqldb.lib.StopWatch;

import junit.framework.TestCase;

/**
 * @author fredt@users
 */
public class TestHashStructures extends TestCase {

    public TestHashStructures(String s) {
        super(s);
    }

    Random randomgen = new java.util.Random();

    public void testHashMap() throws Exception {

        boolean                failed   = false;
        int                    testSize = 33;
        org.hsqldb.lib.HashMap hMap     = new org.hsqldb.lib.HashMap();
        org.hsqldb.lib.IntKeyHashMap hIntMap =
            new org.hsqldb.lib.IntKeyHashMap();
        java.util.HashMap uMap = new java.util.HashMap();

        try {
            populateBySerialIntKeys(uMap, hMap, testSize);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);

            // -
            populateByRandomIntKeys(uMap, hMap, testSize);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);

            //
            depopulateRandomly(uMap, hMap, 20);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);

            // -
            populateBySerialIntKeys(uMap, hMap, testSize);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);

            //
            depopulateByIterator(uMap, hMap, 20);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);
        } catch (Exception e) {
            failed = true;
        }

        assertTrue(!failed);
    }

    public void testIntKeyHashMap() throws Exception {

        boolean failed   = false;
        int     testSize = 33;
        org.hsqldb.lib.IntKeyHashMap hIntMap =
            new org.hsqldb.lib.IntKeyHashMap();
        java.util.HashMap uMap = new java.util.HashMap();

        try {
            populateBySerialIntKeysInt(uMap, hIntMap, testSize);
            compareByUIteratorInt(uMap, hIntMap);
            populateByRandomIntKeysInt(uMap, hIntMap, testSize);
            compareByUIteratorInt(uMap, hIntMap);
            compareByHIteratorInt(uMap, hIntMap);

            //
            depopulateByIntIterator(uMap, hIntMap, 20);
            compareByUIteratorInt(uMap, hIntMap);
            compareByHIteratorInt(uMap, hIntMap);

            //
            clearByIntIterator(uMap, hIntMap);
            compareByUIteratorInt(uMap, hIntMap);
            compareByHIteratorInt(uMap, hIntMap);

            // -
            populateBySerialIntKeysInt(uMap, hIntMap, testSize);
            compareByUIteratorInt(uMap, hIntMap);
            compareByHIteratorInt(uMap, hIntMap);

            //
            clearByIntIterator(uMap, hIntMap);
            compareByUIteratorInt(uMap, hIntMap);
            compareByHIteratorInt(uMap, hIntMap);
        } catch (Exception e) {
            failed = true;
        }

        assertTrue(!failed);
    }

    public void testHashMappedList() throws Exception {

        boolean failed   = false;
        int     testSize = 33;
        org.hsqldb.lib.HashMappedList hMap =
            new org.hsqldb.lib.HashMappedList();
        java.util.HashMap uMap = new java.util.HashMap();

        try {
            populateBySerialIntKeys(uMap, hMap, testSize);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);
            populateByRandomIntKeys(uMap, hMap, testSize);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);
            depopulateRandomly(uMap, hMap, 20);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);
            populateByRandomIntKeys(uMap, hMap, testSize);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);
            depopulateRandomly(uMap, hMap, 20);
            populateBySerialIntKeys(uMap, hMap, testSize);
            compareByUIterator(uMap, hMap);
            compareByHIterator(uMap, hMap);
        } catch (Exception e) {
            failed = true;
        }

        assertTrue(!failed);
    }

    public void testDoubleIntLookup() throws Exception {

        boolean failed   = false;
        int     testSize = 512;
        org.hsqldb.lib.IntKeyHashMap hIntMap =
            new org.hsqldb.lib.IntKeyHashMap();
        DoubleIntIndex intLookup = new DoubleIntIndex(12, false);

        try {
            intLookup.setKeysSearchTarget();
            populateBySerialIntKeysInt(intLookup, hIntMap, testSize);
            compareByHIteratorInt(intLookup, hIntMap);
            populateByRandomIntKeysInt(intLookup, hIntMap, testSize);
            compareByHIteratorInt(intLookup, hIntMap);
        } catch (Exception e) {
            failed = true;
        }

        assertTrue(!failed);
    }

    public void testDoubleIntSpeed() throws Exception {

        boolean failed   = false;
        int     testSize = 500;
        org.hsqldb.lib.IntKeyHashMap hIntMap =
            new org.hsqldb.lib.IntKeyHashMap();
        DoubleIntIndex intLookup = new DoubleIntIndex(testSize, false);

        intLookup.setKeysSearchTarget();
        populateByRandomIntKeysInt(intLookup, hIntMap, testSize);
        compareByHIteratorInt(intLookup, hIntMap);

        int[]     sample     = getSampleIntArray(intLookup, 100);
        int[]     sampleVals = new int[sample.length];
        int       i          = 0;
        int       j          = 0;
        StopWatch sw         = new StopWatch();

        try {
            for (j = 0; j < 10000; j++) {
                for (i = 0; i < sample.length; i++) {
                    int pos = intLookup.findFirstEqualKeyIndex(sample[i]);

                    sampleVals[i] = intLookup.getValue(pos);

                    intLookup.remove(pos);
                }

                for (i = 0; i < sample.length; i++) {
                    intLookup.addUnique(sample[i], sampleVals[i]);
                }
            }

            System.out.println(
                sw.elapsedTimeToMessage("Double int table times"));
            intLookup.findFirstEqualKeyIndex(0);    // sort
            compareByHIteratorInt(intLookup, hIntMap);
        } catch (Exception e) {
            System.out.println(
                sw.elapsedTimeToMessage("Double int table error: i =" + i));

            failed = true;
        }

        assertTrue(!failed);
    }

    int[] getSampleIntArray(org.hsqldb.lib.DoubleIntIndex index, int size) {

        int[]                        array = new int[size];
        org.hsqldb.lib.IntKeyHashMap map = new org.hsqldb.lib.IntKeyHashMap();

        for (; map.size() < size; ) {
            int pos = nextIntRandom(randomgen, index.size());

            map.put(pos, null);
        }

        org.hsqldb.lib.Iterator it = map.keySet().iterator();

        for (int i = 0; i < size; i++) {
            int pos = it.nextInt();

            array[i] = index.getKey(pos);
        }

        return array;
    }

    void populateBySerialIntKeys(java.util.HashMap uMap,
                                 org.hsqldb.lib.HashMap hMap,
                                 int testSize) throws Exception {

        for (int i = 0; i < testSize; i++) {
            int intValue = randomgen.nextInt();

            uMap.put(new Integer(i), new Integer(intValue));
            hMap.put(new Integer(i), new Integer(intValue));

            if (uMap.size() != hMap.size()) {
                throw new Exception("HashMap size mismatch");
            }
        }
    }

    void populateBySerialIntKeysInt(java.util.HashMap uMap,
                                    org.hsqldb.lib.IntKeyHashMap hMap,
                                    int testSize) throws Exception {

        for (int i = 0; i < testSize; i++) {
            int intValue = randomgen.nextInt();

            uMap.put(new Integer(i), new Integer(intValue));
            hMap.put(i, new Integer(intValue));

            if (uMap.size() != hMap.size()) {