勇敢牛牛_ 2018-02-02 07:26 采纳率: 50%
浏览 2531
已采纳

Java Hash Map containsValue的时间复杂度是多少呢

这是它的源码:

 public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

是在遍历数组里先得到头节点,然后再遍历链表得到value,,时间复杂度是O(n)还是O(n²)

  • 写回答

6条回答 默认 最新

  • james_zhg 2018-02-03 08:53
    关注

    介于O(n)和O(n²)之间,更接近于O(n),取决于key的hash重合度,如果所有的value都分布于单独的key,则复杂度就是O(n)。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(5条)

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名