有序集合（映射）容器一般基于平衡二叉搜素树实现，无序集合（映射）容器则一般基于哈希表实现。
哈希表，是数组基于某种映射规则（函数）的⼀种扩展：

• 外部表现为 hash_table['key'] = value，直接通过关键字（浮点数，字符串甚至结构体）索引
• 内部实现为 linear_list[hash(key)] = value，依靠哈希函数把复杂信息映射到一个较小的值域，并作为索引

哈希函数设计得越好，数据分布越均匀，碰撞概率越小。理想情况下，哈希表的插入、查询、删除时间复杂度均为\(O(1)\)。所以，当我们遇到了要快速判断一个元素是否出现集合里的问题，就可以考虑哈希法。

30. 串联所有单词的子串

暴力

class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> ans=new ArrayList<>();
        int tot=0;
        for(String word:words){
            tot+=word.length();
        }

        for(int i=0;i+tot<=s.length();i++){
            String str=s.substring(i,i+tot);
            if(validate(str,words)) ans.add(i);
        }

        return ans;
    }

    boolean validate(String str,  String[] words){
        int k=words[0].length();
        HashMap<String, Integer> splitWords=new HashMap<>();
        for(int i=0;i<str.length();i+=k){
            String key=str.substring(i,i+k);
            if(splitWords.get(key)!=null){
                splitWords.put(key,splitWords.get(key)+1);
            }
            else splitWords.put(key,1);
        }

        for(String word:words){
            Integer count=splitWords.get(word);
            if(count==null) return false;
            else splitWords.put(word,splitWords.get(word)-1);
        }

        for(String key:splitWords.keySet()){
            if(splitWords.get(key)!=0) return false;
        }

        return true;
    }
}

146. LRU 缓存