java - 同构字符串的时间复杂度

Question

HashMap.containsValue()和因此的代码的时间复杂度是多少？是它O(n2)还是if条件将HashMap.containsValue()'s 的复杂性降低到O(1)?

public static boolean isIsomorphic (String s1 , String s2){

    if (s1 == null || s2 == null){
        throw new IllegalArgumentException();
    }

    if (s1.length() != s2.length()){
        return false;
    }

    HashMap<Character, Character> map = new HashMap<>();

    for (int i = 0 ; i < s1.length(); i++){

        if (!map.containsKey(s1.charAt(i))){

            if(map.containsValue(s2.charAt(i))){

                return false;
            }           

            else{
                map.put(s1.charAt(i), s2.charAt(i));
            }           
        }
        else{
            if( map.get(s1.charAt(i)) != s2.charAt(i)){
                return false;                   
            }               
        }           
    }
    return true;        
}

Answer 1

containsValue() 时间复杂度将为 O(n+k)[n 为否。的值和 k 为否。键]。由于每个值都存在于存储桶中，因此控件会转到每个存储桶，然后在存储桶内遍历，直到找到该值。