hashSet是很好用的，但是，如果key太长了，怎么优化呢？

---

187. Repeated DNA Sequences

题目

给出一个DNA字符串，里面仅包含字符'A','C',G','T'
要求超出 长度为10的，而且重复出现的子串

思考

每个大于10的子串都是一个HashSet Object?
滑动窗（窗长为10）的形式，从左滑到右
如果在HashSet里面没有出现过，put 进去
如果出现过，add 到 answer里面
如果出现两次以上，不就重复添加了吗？

思路

** 2 HashSet + sliding window **

• sliding window 的长度是10，每一次都把窗内的子串进行判断：
• 如果不在set1里面，就添加到set1
• set2用来记录符合“重复出现且长度为10”的条件，而且已经添加到了answer里面的子串。用来防止重复添加到answer中
• 如果在set1里面且不在set2里面，就添加到answer 和 set2里面

---

优化 HashSet

那么，题目给出'A','C','G','T'有什么意义呢？
10个字符串作为一个HashSet Object, 超时！
怎么才能更快、而且用更少的空间去记录这10个字符串呢？

解决方法 ： 编码

A : 0 (00)
C : 1 (01)
G : 2 (10)
T : 3 (11)
这样，10个长度的字符串就是一个 20位的二进制编码
我们可以使用
int hash_num = 0;
hash_num = (hash_num<<2) + ch.get('A')
的形式来构造20位的编码。
遍历的时候，先左移2位，或上新的字符，
因为这么操作，所以10个字符输入后，共22位，
我们只要处理一下，保留最低的20位作为hash_num即可。

---

具体代码：

    public List<String> findRepeatedDnaSequences(String s) {
        
        List<String> ans = new ArrayList<String>();
        if(s == null || s.length()<=10)
            return ans;
        
        HashMap<Character, Integer> ch = new HashMap<Character, Integer>();
        ch.put('A', 0);
        ch.put('C', 1);
        ch.put('G', 2);
        ch.put('T', 3);
        
        HashSet<Integer> set = new HashSet<Integer>();
        HashSet<Integer> set2 = new HashSet<Integer>();  // 防止符合条件的字串重复添加到ans里面
        
        int hash_num = 0;
        for(int i=0; i<s.length(); i++)
        {
            if(i<9)
            {
                hash_num <<= 2;
                hash_num |= ch.get(s.charAt(i));
            }
            else
            {
                hash_num <<= 2;
                hash_num |= ch.get(s.charAt(i));
                int mask = (1<<20)-1; // 10000...00(21bits) --> 0111..111(20bits of 1)
                hash_num &= mask;
                if(set.contains(hash_num) && !set2.contains(hash_num))
                {
                    ans.add(s.substring(i-9, i+1));
                    set2.add(hash_num);
                }
                else
                    set.add(hash_num);
            }
        }
        return ans;
    }

小收获

1. 不管是HashSet 还是 HastMap， 如果能够发现输入的规律，适当进行编码，可以压缩空间，而且用Integer替换String可以提高速度。

---