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

Question

Tôi cần biết: Độ phức tạp của HashMap.containsKey() trong java là bao nhiêu?

Answer 1

Từ API doc ofHashMap:

thực hiện này cung cấp hiệu suất không đổi theo thời gian cho thao tác cơ bản (get và put), giả sử hàm băm phân tán các phần tử đúng trong số các nhóm.

Kể từ containsKey() chỉ là một get() mà ném đi những giá trị lấy ra, đó là O (1) (giả sử các hàm băm hoạt động đúng, một lần nữa).

Answer 2

Đó là O(1) nói chung, tuy nhiên trong trường hợp xấu nhất đó là O(n)

public boolean containsKey(Object key) { 
    352   return getEntry(key) != null; 
    353  } 
    354 
    355  /** 
    356  * Returns the entry associated with the specified key in the 
    357  * HashMap. Returns null if the HashMap contains no mapping 
    358  * for the key. 
    359  */ 
    360  final Entry<K,V> getEntry(Object key) { 
    361   int hash = (key == null) ? 0 : hash(key.hashCode()); 
    362   for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
    363    e != null; 
    364    e = e.next) { 
    365    Object k; 
    366    if (e.hash == hash && 
    367     ((k = e.key) == key || (key != null && key.equals(k)))) 
    368     return e; 
    369   } 
    370   return null; 
    371  } 

Answer 3

Nói chung O (1), nhưng nếu chúng ta đang sử dụng hàm hashCode xấu, chúng ta cần thêm nhiều phần tử vào một nhóm để nó có thể là O (n) trong trường hợp xấu nhất.

Answer 4

Độ phức tạp thời gian của containsKey đã thay đổi trong JDK-1.8, như những người khác đã đề cập là O(1) trong trường hợp lý tưởng. Tuy nhiên, trong trường hợp va chạm nơi keys là Comparable, thùng chứa nguyên tố va chạm không tuyến tính nữa sau khi họ vượt quá một số ngưỡng gọi TREEIFY_THRESHOLD, tương đương với 8,

/** 
* The bin count threshold for using a tree rather than list for a 
* bin. Bins are converted to trees when adding an element to a 
* bin with at least this many nodes. The value must be greater 
* than 2 and should be at least 8 to mesh with assumptions in 
* tree removal about conversion back to plain bins upon 
* shrinkage. 
*/ 
static final int TREEIFY_THRESHOLD = 8; 

Nói một cách khác, TreeNodes sẽ được sử dụng (tương tự như trong TreeMap) để lưu trữ thùng, (tức là: một cấu trúc cây Đỏ-Đen) và điều này khiến chúng tôi có một sự phức tạp trong trường hợp va chạm O(lgn).

cũng áp dụng cho get(key) nơi mà cả hai phương pháp gọi getNode nội

Lưu ý: n đây là kích thước của bin và không phải là HashMap