harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Evgeniya Maenkova (JIRA)" <j...@apache.org>
Subject [jira] Created: (HARMONY-3086) [math] poor hashCode in java.math.BigDecimal and java.math.BigDecimal
Date Tue, 30 Jan 2007 13:42:33 GMT
[math] poor hashCode in java.math.BigDecimal and java.math.BigDecimal
---------------------------------------------------------------------

                 Key: HARMONY-3086
                 URL: https://issues.apache.org/jira/browse/HARMONY-3086
             Project: Harmony
          Issue Type: Improvement
          Components: Classlib
         Environment: Platform independent
            Reporter: Evgeniya Maenkova


As BigDecimal/BigInteger.hashCode isn't specified I belive we can do some improvements in
this arrea.

1)BigInteger.hashCode computes a hash code accordingly to the latest digit only. We could
take all digits into account.
2)BigDecimal.hashCode uses shift, so BigInteger's hashCode has pretty small influence on BigDecimal's
hashCode.
 public int hashCode() {
        /* Take the 24 trailing bits of BigInteger hashcode
         * and the 8 trailing bits of scale. */
        return ((getUnscaledValue().hashCode() << 24) | (0xFF & scale));
    }
3) when we are dealing with "small" BigDecimal I believe it's possible to compute hash code
more effectively without redudant objects creation (I mean BigInteger).
4) I've written minimal test case with "big" BigDecimal as keys in some hashMap(to be attached,
and see please below) and there the results (my laptop :), pretty approximately, of course):
RI:
--
different hash coodes: 45000
time6173
--
current java.math:
different hash coodes: 906
time82239

--patched java.math:
different hash coodes: 45000
time6344

(This test shows so big difference in time and hash code distribution.
5)I get 1 failed test with this patch:org.apache.harmony.tests.java.math.BigIntegerHashCodeTest.
Test is looking doubtful as (a) hash code isn;t specified so we shouldn't require this behavior;
(b) It fails on RI also. So I would propose to remove this test at all.

-    public void testUnequalObjectsEqual() {
-        byte aBytes[] = {56, 100, -2, -76, 98, 54, 19, 3, -15, 45, 89, -111, 69, 103, 8,
-9};
-        byte bBytes[] = {56, 100, -2, -76, 89, 45, 91, 3, -15, 45, 89, -111, 69, 103, 8,
-9};
-        int aSign = 1;
-        BigInteger aNumber = new BigInteger(aSign, aBytes);
-        BigInteger bNumber = new BigInteger(aSign, bBytes);
-        int code1 = aNumber.hashCode();
-        int code2 = bNumber.hashCode();
-        if (!aNumber.equals(bNumber)) {
-            assertTrue("hash codes for these unequal objects should be equal", code1 == code2);
-        }
-    }
+    }      


Test  case mentioned above:
----
import java.math.BigDecimal;
import java.text.NumberFormat;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

public class HashMapTest {
	static class MyBigDecimal extends BigDecimal {
		public MyBigDecimal(String s) {
			super(s);
		}
		static long hashCodeCallsCounter;
		static long equalsCallsCounter;
		@Override
		public int hashCode() {
			hashCodeCallsCounter ++;
			return super.hashCode();
		}
		
		@Override
		public boolean equals(Object arg0) {
			equalsCallsCounter ++;
			return super.equals(arg0);
		}
		
		static void reset() {
			equalsCallsCounter = 0;
			hashCodeCallsCounter = 0;
		}
	}
	
	
	static MyBigDecimal[][][] keys;
	static int[] hashcodes;
	public static HashMap createRatesMap(int dim1, int dim2,
            int dim3, BigDecimal value1) {
        HashMap map = new HashMap();
        keys = new MyBigDecimal[dim1][dim2][dim3];
        StringBuffer sb = new StringBuffer();
        NumberFormat nf = NumberFormat.getNumberInstance();
        nf.setMinimumIntegerDigits(3);
        hashcodes = new int[dim1 * dim2 * dim3];
        int ind = 0;
        for (int i = 0; i < dim1; i ++){
            for (int j = 0; j < dim2; j ++) {
                for (int k = 0; k < dim3; k ++) {
                    long res = i * 10000 + j * 100 + k;
                    int scale = 3 + ((i + j + k) % 5);
                    MyBigDecimal key = new MyBigDecimal(res + "." + res);
                    keys[i][j][k] = key;
                    hashcodes[ind ++] = key.hashCode();
                    map.put(key, value1.setScale(scale, BigDecimal.ROUND_DOWN));
                }
            }
        }
        return map;
    }	
	
	public static void main(String[] args) {
		HashMap map = createRatesMap(300, 10, 15, BigDecimal.ONE);
		Arrays.sort(hashcodes);
		int currentValue = 0;
		int currentIndex = 0;
		int curLength = 0;
		int[] value = new int[hashcodes.length];
		int[] counters = new int[hashcodes.length];
		
		for (int i = 0; i < hashcodes.length; i ++) {
			if (hashcodes[i] == currentValue) {
				currentIndex++;
				counters[curLength - 1] = currentIndex;				
			} else {				
				currentIndex = 1;
				currentValue = hashcodes[i];
				value[curLength] = currentValue;
				counters[curLength] = 1;
				curLength++;
			}
		}		
		
		MyBigDecimal.reset();		
		Random random = new Random();	
		long start = System.currentTimeMillis();
		for (int i = 0; i < 10000000; i ++) {
		    map.get(keys[random.nextInt(300)][random.nextInt(10)][random.nextInt(15)]);
		}
		System.out.println("different hash coodes: " + curLength);
		System.out.println("time" + (System.currentTimeMillis() - start));		
		
	}
}





-- 
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.


Mime
View raw message