Độ phức tạp của HashMap.containsValue() trong java là bao nhiêu?

Question

Tôi đã được đưa ra một vấn đề để giải quyết trong O(n) độ phức tạp về thời gian:

"Cho danh sách số và số x. Tìm xem có 2 số nào trong danh sách thêm vào x không?"

Và đây là giải pháp của tôi:

public class SumMatchResult { 

    public static void main(String[] args){ 
    int[] numberList = {6,1,8,7,4,6}; 
    int requiredSum = 8; 
    boolean isSumPresent = checkSumPresentHash(numberList,requiredSum); 
    if(isSumPresent) { 
     System.out.println("Numbers exist"); 
    }else { 
     System.out.println("Numbers donot exist"); 
    } 
    } 

    private static boolean checkSumPresentHash(int[] numberList, int requiredSum) { 
    Map<Integer, Integer> m = new HashMap<Integer,Integer>(); 
    int count = 0; 
    for(int i=0;i<numberList.length;i++){ 
     m.put(i, numberList[i]); 
    } 
    for(int i=0;i<numberList.length;i++){ 
     if(m.containsValue(requiredSum - numberList[i])){ 
     count++; 
     } 
    } 
    if(count>1){ 
     return true; 
    } 
    return false; 
    } 

} 

Tôi đang sử dụng HashMap.containsValue() thay vì sử dụng một HashSet.contains() mà chắc chắn có độ phức tạp của O(1) vì, tôi phải giải thích cho các kịch bản mà đầu vào của tôi có thể chứa các giá trị giống hệt nhau. Ví dụ, trong trường hợp trên, tôi có thể có một tập hợp các giá trị đầu vào {3,6,4,4,7} để khớp với sum 8, sẽ trả về true.

Độ phức tạp về thời gian của giải pháp trên tùy thuộc vào độ phức tạp của phương pháp HashMap.containsValue(). Vui lòng giải thích một chút về độ phức tạp của phương pháp containsValue() và đề xuất cho tôi nếu có giải pháp nào tốt hơn cho vấn đề trên về độ phức tạp của thời gian. Cảm ơn bạn.

Answer 1

để trả lời câu hỏi trong tiêu đề - như đã đề cập bởi những người khác, containsValue là O (n), bởi vì không có chìa khóa nó không biết nó ở đâu và các thuật toán đã đi khắp nơi trên giá trị được lưu trữ trong bản đồ.

Để trả lời câu hỏi trong phần câu hỏi của bạn - hãy xem xét xem bạn thực sự cần một bản đồ chung có thể đếm số lượng trường hợp bạn đã xem của từng số. Ý tôi là, chỉ chỉ thời gian bạn quan tâm nếu có nhiều hơn một lần xuất hiện của một số khi nó là x/2, phải không? Điều đó có mùi giống như một trường hợp góc với tôi. Chỉ cần thêm kiểm tra để kiểm tra trường hợp góc đó - chẳng hạn như nhúng if (numberList[i] == requiredSum/2) half++ trong vòng lặp thiết lập của bạn, sau đó if (requiredSum % 2 == 0 && half == 2) return true sau nó (xem biến thể khác bên dưới).

Sau đó, bạn chỉ có thể lặp qua tập hợp và cho mỗi mục, kiểm tra xem requiredSum-item cũng xuất hiện trong bộ này hay chưa.

Để tóm tắt (với lối ra sớm khi có thể):

Set<Integer> seen = new HashSet<Integer>(); 
boolean halfSeen = false; 
for (int num : numberList) { 
    if (num == requiredSum/2 && requiredSum % 2 == 0) { 
     if (halfSeen) return true; 
     halfSeen = true; 
    } else { 
     seen.add(num); 
    } 
} 
for (int num : seen) { 
    if (seen.contains(requiredSum - num)) return true; 
} 
return false; 

Answer 2

HashMap về bản chất là một kho khóa-giá trị, có thể truy cập các khóa của nó với độ phức tạp của O (1). Kiểm tra một giá trị, tuy nhiên, không có gì HashMap có thể làm nhưng kiểm tra tất cả các giá trị và xem chúng có bằng với giá trị bạn đang tìm kiếm hay không. Do đó, độ phức tạp là O (n) với n là số phần tử trong HashMap.

Lưu ý khác: Bạn đang tìm kiếm các giá trị nguyên thủy (int) trong tập hợp loại được đóng hộp (Số nguyên). Điều này có nghĩa mỗi khi bạn đang gọi một phương thức trên HashMap, Java cần phải hộp cho bạn các giá trị nguyên thủy: http://docs.oracle.com/javase/1.5.0/docs/guide/language/autoboxing.html

Answer 3

HashMap.containsValue complexity là O (n). Nhưng n không chính xác kích thước bản đồ nhưng thay vì kích thước bảng băm bởi vì containsValue chuyển qua tất cả các phần tử bảng nếu ngay cả kích thước bản đồ = 0. Giả sử chúng ta tạo một bản đồ trống với dung lượng ban đầu = 1024. containsValue sẽ phải chuyển qua bảng băm thành phần 1024 mảng:

public boolean containsValue(Object value) { 
    if (value == null) 
     return containsNullValue(); 

    Entry[] tab = table; 
    for (int i = 0; i < tab.length ; i++) 
     for (Entry e = tab[i] ; e != null ; e = e.next) 
      if (value.equals(e.value)) 
       return true; 
    return false; 
}