Homework 3: Hashing

CS61B

Simple Oomage

再一次在open project的时候遇到了java.lang.ClassNotFoundException这个异常，采用笨办法，自己建project,再一一建立新类解决了这个问题。有更好的办法吗？

A Perfect hashCode

这个不会写.
给的Hint：Try out every possible combination of red, green, and blue values and ensure that you never see the same value more than once.

最后还是用了O（N^3)的brute force, 不过一个小技巧值得留意。 要确定不同组合的red,green,blue不会返回相同的hashcode,就要确定所有组合返回的hashcode没有duplicate. 可以先用arraylist装这些int,再用hashset装这些int。 因为hashset不允许duplicate,所以只需要assertequal这个arraylist和hashset的size就能判断这些有没有duplicates了

public void testHashCodePerfect() {
        /* TODO: Write a test that ensures the hashCode is perfect,
         meaning no two SimpleOomages should EVER have the same
         hashCode!
         Hint: Try out every possible combination of red, green, and blue values and
         ensure that you never see the same value more than once.
        */
        ArrayList<Integer> hashList = new ArrayList<>();
        for(int i = 0; i < 256; i += 5){
            for(int j = 0; j <256; j += 5){
                for(int k = 0; k < 256; k += 5){
                    SimpleOomage soA = new SimpleOomage(i,j,k);
                    int hash = soA.hashCode();
                    hashList.add(hash);
                }
            }
        }
        HashSet<Integer> set = new HashSet(hashList);
        assertEquals(hashList.size(), set.size());
    }

Perfect HashCode不是很懂为何要那么些，但通过测试了。

@Override
    public int hashCode() {
        if (!USE_PERFECT_HASH) {
            return red + green + blue;
        } else {
            // TODO: Write a perfect hash function for Simple Oomages.
            return 256*256*red + 256*green + blue;
        }
    }