wxgxgp
石头剪刀布_
2018-02-02 07:26
采纳率: 100%
浏览 2.3k
已采纳

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
    james_zhg 2018-02-03 08:53
    已采纳

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

    点赞 评论
  • lin595052817
    林 先森 2018-02-02 07:47

    肯定是O(n²),因为需要先循环出key 才能得到key封装的值。

    点赞 评论
  • guotext
    guotext 2018-02-02 08:15

    O(n²),先循环key,在取的value,底层也是用equals比较!

    点赞 评论
  • oschina_39814655
    oschina_39814655 2018-02-02 12:12

    楼主可以先去读hashmap的put方法的源码 了解一下HashMap的数据结构

    点赞 评论
  • guoqi4022290
    guoqi4022290 2018-02-05 02:24

    james_zhg 正解

    点赞 评论
  • w597265467
    w597265467 2018-02-24 09:20

    你得看这个数据长啥样
    这样的话
    0 1 2数组长3每个位置链表长3
    0 0 0
    1 1 1
    2 2 2
    是O(n²)

    或者数组长9每个位置链表长1
    0 1 2 3 4 5 6 7 8 9
    是O(n)

    因为是要key的hash值一样的数据才回放到链表中
    所有一般O(n²)是不会出现的,比较接近O(n)

    点赞 评论

相关推荐