Question: What is the time complexity of checking membership in dict.items()? According to the documentation:  Keys views are set-like since their entries are unique and hashable. If all values are hashable, so that (key, value) pairs are unique and hashable, then the items view is also set-like. (Values views are not treated as set-like since the entries are generally not unique.) For set-like views, all of the operations defined for the abstract base class collections.abc.Set are available (for example, ==, <, or ^).  So I did some testing with the following code: from timeit import timeit def membership(val, container): val in container r = range(100000) s = set(r) d = dict.fromkeys(r, 1) d2 = {k: [1] for k in r} items_list = list(d2.items()) print('set'.ljust(12), end='') print(timeit(lambda: membership(-1, s), number=1000)) print('dict'.ljust(12), end='') print(timeit(lambda: membership(-1, d), number=1000)) print('d_keys'.ljust(12), end='') print(timeit(lambda: membership(-1, d.keys()), number=1000)) print('d_values'.ljust(12), end='') print(timeit(lambda: membership(-1, d.values()), number=1000)) print('\n*With hashable dict.values') print('d_items'.ljust(12), end='') print(timeit(lambda: membership((-1, 1), d.items()), number=1000)) print('*With unhashable dict.values') print('d_items'.ljust(12), end='') print(timeit(lambda: membership((-1, 1), d2.items()), number=1000)) print('d_items'.ljust(12), end='') print(timeit(lambda: membership((-1, [1]), d2.items()), number=1000)) print('\nitems_list'.ljust(12), end='') print(timeit(lambda: membership((-1, [1]), items_list), number=1000))  With the output: set 0.00034419999999998896 dict 0.0003307000000000171 d_keys 0.0004200000000000037 d_values 2.4773092 *With hashable dict.values d_items 0.0004413000000003109 *With unhashable dict.values d_items 0.00042879999999989593 d_items 0.0005549000000000248 items_list 3.5529328  As you can see, when the dict.values are all hashable (int), the execution time for the membership is similar to that of a set or d_keys, because items view is set-like. The last two examples are on the dict.values with unhashable objects (list). So I assumed the execution time would be similar to that of a list. However, they are still similar to that of a set. Does this mean that even though dict.values are unhashable objects, the implementation of items view is still very efficient, resulting O(1) time complexity for checking the membership? Am I missing something here? EDITED per @chepner's comment: dict.fromkeys(r, [1]) -> {k: [1] for k in r} EDITED per @MarkRansom's comment: another test case list(d2.items())

Answer: Lookup in an instance of dict_items is an O(1) operation (though one with an arbitrarily large constant, related to the complexity of comparing values.)  dictitems_contains doesn't simply try to hash the tuple and look it up in a set-like collection of key/value pairs. (Note: all of the following links are just to different lines of dictitems_contain, if you don't want to click on them individually.) To evaluate (-1, [1]) in d2.items()  it first extracts the key from the tuple, then tries to find that key in the underlying dict. If that lookup fails, it immediately returns false. Only if the key is found does it then compare the value from the tuple to the value mapped to the key in the dict. At no point does dictitems_contains need to hash the second element of the tuple. It's not clear in what ways an instance of dict_items is not set-like when the values are non-hashable, as mentioned in the documentation.  A simplified, pure-Python implementation of dict_items.__contains__ might look something like class DictItems: def __init__(self, d): self.d = d def __contains__(self, t): key = t[0] value = t[1] try: dict_value = self.d[key] # O(1) lookup except KeyError: return False return value == dict_value # Arbitrarily expensive comparison ...  where d.items() returns DictItems(d).