欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-15 22:22:18
...

如何从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 + " - 分治 + 映射消耗的时间");
    }

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

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

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