Citron__ 2018-09-27 12:15 采纳率: 33.3%
浏览 3253

位运算比取模运算快?应该怎么体现

Java 位运算和模运算到底哪个快?修改
之前在看 HashMap 的源代码和相关博客。

看到了HashMap中有关HashMap容器大小和indexFor()中的方法。

按照我的理解来看,之所以要是2的n次方,是为了能使indexFor中的位运算代替取模运算。

有些人2^n-1 正好二进制位全是1,类似这种1111111,这样与运算hash冲突才能降到到最低,但是直接取模不是一样的能均匀分布么?

这里关键的问题就在于究竟是不是位运算比取模运算快很多了:


 public static void test2() {
        int capacity = 1024;
        int val = 13;
        int count = 100000;
        long t1 = System.nanoTime();
        for (int i = 0; i < count; i++) {
            indexFor1(val,capacity);
        }
        long t2 = System.nanoTime();

        System.out.println("& time:"+(t2-t1));


        long t3 = System.nanoTime();
        for (int i = 0; i < count; i++) {
            indexFor2(val,capacity);
        }
        long t4 = System.nanoTime();

        System.out.println("% time:"+(t4-t3));


    }
        static int indexFor1(int h, int length) {
        return h & (length-1);
    }
    static int indexFor2(int h, int length) {
        return h % (length);
    }

这段测试代码在我的电脑上,相差结果并不大。。。

突然就迷惘了。。

楼主之前学过计组,操作系统等学过,也知道取模是肯定比直接位运算慢。但是为什么执行起来相差不多。

1.难道是因为现在cpu发展已经有了很大的优化,所以相差不打,但是在HashMap刚出现的时候,位运算和取模效率相差很大,所以用了位运算,而现在JDK 1.8 还是位运算是为了兼容以前的程序。

是这样么?只是我的猜想,或者是我理解不对?测试方法写的不对?

望解惑,要是是我理解不多,以后这种设计方法可以借鉴啊。

  • 写回答

2条回答 默认 最新

  • zhangpan_soft 2018-09-28 10:32
    关注

    这个差别其实是很大的,有一句话,千里之堤毁于蚁穴,说一个假如假如效率只是相差千分之一毫秒,1000次hash就相差1毫秒,1000*1000次hash相差1秒,往后不用说了吧?
    不要觉得我说的数字很大,其实并不大,1个外网项目,很容易就达到如此量级,比如淘宝.一台的访问量该有多大,该有多少次hash?上亿次都是保守的,慢了多少秒,1天慢10分钟,10天就慢了100分钟,我特别不喜欢一些程序员觉得貌似两个方法没差别,殊不知,很多时候,很多线上问题,就是这些小如蚂蚁的错误,而毁了整个项目.
    楼主可以追一下ArrayList,ArrayList的扩容1.5之前用的普通乘法,1.5之后改为位运算,为什么要改?一样的道理,哪怕慢一点点,也会造成致命的错误,所以,做程序,一定要严禁,不要认为一个问题很小,要认真对待每一个问题

    评论

报告相同问题?

悬赏问题

  • ¥15 miniconda安装不了
  • ¥20 python代码编写
  • ¥20 使用MPI广播数据遇到阻塞
  • ¥15 TinyMCE如何去掉自动弹出的“链接…”工具?
  • ¥15 微信支付转账凭证,如何解决
  • ¥15 在win10下使用指纹登录时,界面上的文字最后一个字产生换行现象
  • ¥20 使用AT89C51微控制器和MAX7219驱动器来实现0到99秒的秒表计数,有开始和暂停以及复位功能,下面有仿真图,请根据仿真图来设计c语言程序
  • ¥15 51单片机 双路ad同步采样
  • ¥15 使用xdocreport 生成word
  • ¥15 请教怎么用MATLAB求坐标