美文网首页工作生活
String-hashcode疑问

String-hashcode疑问

作者: small瓜瓜 | 来源:发表于2019-07-05 20:12 被阅读0次

今天闲来没事看String的源码,在看到hashCode方法里的实现,总感觉有点问题,以前就是看看了实现并没有太在意效率,下面就是StringhashCode方法代码。h = 31 * h + val[i]要执行n次,时间复杂度为O(n)。时间复杂度上我们不能减少,但是为什么不把h = 31 * h + val[i]用位运算代替呢。比如:

int tmp = val[i] - h;
h <<= 5;
h += tmp;

本来以为可能是三行代码会导致代码的效率反而降低,但是通过测试后发现,位运算效率还是比较高些
下面是jdkStringhashCode源码:

public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

为了进行检验,编写下面的程序,初步估计等下面程序跑完,已经是我毕业了,所以放到服务器上去跑了,等我毕业再来重写这篇文章吧

import java.time.Duration;
import java.time.Instant;
import java.util.Random;

public class Main {
    public static void main(String[] args) {
        int one = 0;
        int two = 0;
        int balance = 0;
        System.out.println("开始计算");
        for (int i = 1; i < Integer.MAX_VALUE; i++) {
            int c = new Random().nextInt(128);
            int result = compareTest(i, (char) c);
            if (result == 0)
                balance++;
            else if (result < 0)
                one++;
            else
                two++;
        }
        System.out.printf("one耗时少的次数:%d\ntwo耗时少的次数:%d\nbalance平衡次数:%d", one, two, balance);
    }

    private static int compareTest(int n, char c) {
        Instant start01 = Instant.now();
        int oneTime = testOne(n, c);
        Instant end01 = Instant.now();
        int nano01 = Duration.between(end01, start01).getNano();

        Instant start02 = Instant.now();
        int twoTime = testTwo(n, c);
        Instant end02 = Instant.now();
        int nano02 = Duration.between(end02, start02).getNano();
        if (oneTime != twoTime) {
            throw new RuntimeException("当前n=" + n + ",c=" + c + ",oneTime=" + oneTime + ",twoTime=" + twoTime);
        }
        return nano01 - nano02;
    }

    private static int testOne(int n, char c) {
        char[] val = {c};
        int h = 0;
        for (int i = 0; i < n; i++) {
            h = h * 31 + val[0];
        }
        return h;
    }

    private static int testTwo(int n, char c) {
        char[] val = {c};
        int h = 0;
        for (int i = 0; i < n; i++) {
            int tmp = val[0] - h;
            h <<= 5;
            h += tmp;
        }
        return h;
    }
}

如果有大神知道,还望指导一二。

相关文章

  • String-hashcode疑问

    今天闲来没事看String的源码,在看到hashCode方法里的实现,总感觉有点问题,以前就是看看了实现并没有太在...

  • 疑问

    自私是不是人的本性?

  • 疑问

    时间是陪伴 你信不信 单片机可是设时 你的周时,你用什么控制

  • 疑问

    为什么中文的Unicode范围是u+4e00到u+9fa5? 20180315 20.33 https://my....

  • 疑问

    从发布招聘启事至今,接到过不少求职电话,其中有一个我印象特别深刻的,电话接通后,第一句:问我是不是招人?我说是。第...

  • 疑问

    你在急着什么,急着体验,急着玩,急着经历以致于其中的乐趣你也给急掉了,但那些不就是生命价值体现的一部分吗。这些不就...

  • 疑问

    为什么说话?我说话,说我的家乡话为什么说话?为了记住我的家乡话我是在想说的时候,说想说的话或许是今天,或许是以后我...

  • 疑问

    半个月前已经费心预约了,为什么还要排队?况且又是那么难约。那几天一直刷新,片刻不敢掉以轻心,可还是错过最佳时期,连...

  • 疑问

    你幸福吗? 你快乐吗? 你成熟吗?

  • 疑问

    我终日无所事事。 放空的状态很糟糕,也很安全。没有突如其来的惊吓 ,没有挣扎不得的拮据,也没有撕心裂肺的缠绵。 如...

网友评论

    本文标题:String-hashcode疑问

    本文链接:https://www.haomeiwen.com/subject/sbydhctx.html