分治+映射：快速的从100w个无序元素中准确判断是否存在某元素

如何从100w无序元素中快速找出某元素是否存在呢?

看到这种题，我会想到一下一种方式来实现

• 遍历
        肯定行，简单粗暴，但是不会这么简单吧。。
• 二分查找
       是一个无序集合， 首先淘汰二分查找， 二分查找的前提是链表必须是有序的， 才能从中间比较是大是小， 从而缩小查找空间。
• bitmap
       bitmap(位图)，是由一组0000100100111 组成， 当元素经过hashcode会找到其存在的位置，将0变成 1， 布隆过滤器其实底层就是一个比较长的位图，它在查找元素的位置时， 不止进行一次hashcode（我记得是两次）， 多次hashcode可以避免发生碰撞。当然，也会避免不了hashcode的重复，布隆过滤器：存在的一定存在，不存在的可能存在。所以，与精准的找出也不太合适。
  布隆过滤器
• 分治 映射
       分治：分治我理解的意思就是说把集合或链表拆分开，映射，就是每个元素通过hash算法，精确地找到元素所在分治后的小集合中，从而大大的缩短了查找时间 （类似于hashMap）

 又到了刺激的时刻了。。。

举栗：给你100w个无序元素，快速的找到其中某个元素是否精准的存在

public static void main(String[] args) {
        ArrayList<List<String>> lists = new ArrayList<>();
        // 初始化数组 100w个元素
        ArrayList<String> elements = new ArrayList<>();
        for (int i = 0; i < 1000000; i++) {
            elements.add("dugt" + i); // 就当他是无序的
        }
        // 分治成1000个
        final int listNumber = 1000;
        for (int i = 0; i < listNumber; i++) {
            lists.add(new ArrayList<String>());
        }
        // 找到每个元素的位置 分别存储到1000个集合中
        elements.forEach(ele -> {
            // 找到元素所在的位置
            int index = ele.hashCode() % listNumber;
            for (int i = 0; i < listNumber; i++) {
                if (index == i) {
                    lists.get(i).add(ele);
                }
            }
        });
        // 判断 dugt99999 在不在集合elements内
        // 1 传统遍历的方式
        int start = (int) new Date().getTime();
        elements.forEach(ele -> {
            if ("dugt999999".equals(ele)) {
                System.out.println("方式1元素存在");
            }
        });
        int end = (int) new Date().getTime();
        System.out.println(end - start + " - 遍历消耗的时间");
        // 2 分治 + 映射
        String dugt = "dugt999999";
        int starts = (int) new Date().getTime();
        int index = dugt.hashCode() % listNumber ; 
        lists.get(index).forEach(ele -> {
            if (dugt.equals(ele)) {
                System.out.println("方式2元素存在");
            }
        });
        int ends = (int) new Date().getTime();
        System.out.println(ends - starts + " - 分治 + 映射消耗的时间");
    }

运行结果 （这是差了多少倍！！！）虽然差的也不是很多，但一些复杂的场景下，可以有效地提高系统的并发性

有什么不对的地方，请留下你的留言 ~