0

So I have to search if a key is present in dictionary or not. From this post: here

I can see that the intended way to check for this is using:

if key in dict

but my questions is, would it would be better to do this:

def appendToMyDict(key, value):
    try:
        old_value = dict[key]
        newValue = old_value + value
        dict[key] = newValue
    except KeyError:
        dict[key] = value

My intention is to optimize "getting the key" as much as I can, because my key space will be very large, around 1000 or above.

The way I see it is that dictionaries are hashmaps. So when I do dict[key], python would be hashing the key, and would have been getting its value in O(1) time. But while searching for the key using the "if key in dict" method, it will be take time O(n)[Because it will searching through the whole key space].

But if I throw error, it would take time of O(1) + time to throw and catch the error.

Am I correct ?

Community
  • 1
  • 1
Rash
  • 7,677
  • 1
  • 53
  • 74
  • Why would `if key in dict` be O(n)? Why can't it hash the key and see if there's a value in O(1), the same as `dict[key]`? – Kevin Nov 05 '14 at 19:26
  • if I do "if value in list", would python create a hashmap of list and then search it in O(1) time. Because if yes, creating a whole hashmap for that list would be a costly operation. So I thought that since "in" keyword is a generic keyword, it will just simply look through all the keyspace to check for the key. – Rash Nov 05 '14 at 19:30
  • Why not use `.setdefault`? eg: `value = your_dict.setdefault(key, 'some_value')` ? – Jon Clements Nov 05 '14 at 19:30
  • I don't understand how setting a default value will help, because its not a definite dictionary...any key coming to me is unknown and I cannot possibly know before time that the incoming key must have a default value. Am I understanding this correctly ? – Rash Nov 05 '14 at 19:33
  • @Rash you seem to assume you know what value to set it to by using `dict[key] = "some value"`... how is it different? – Jon Clements Nov 05 '14 at 19:34
  • oh sorry, dont mind that line. I just put it there..the value that I need to be inserted will also come at the same time as the key...so I get the key and the value to be entered in the dictionary, and if the key already is present, I want to append the new value to the old.. – Rash Nov 05 '14 at 19:35
  • @Rash then you need to make that clearer in your question, as your code example and body of the question certainly don't make that clear. Might be useful to provide sample input/output... – Jon Clements Nov 05 '14 at 19:37

1 Answers1

0

key in dict is O(1), assuming dict is actually a dictionary.

Kevin
  • 28,963
  • 9
  • 62
  • 81
  • So does python first check if the "object" it is going to iterate is a dict, or a list, and then searches for the key based on that? Can you provide some reference, where I can read and confirm this behaviour ? – Rash Nov 05 '14 at 19:41
  • 1
    @Rash a `dict` implements a `__getitem__` method (which is called when you use `dict[key]` which uses a hash and is effectively an O(1) lookup - definitely not O(N). – Jon Clements Nov 05 '14 at 19:44
  • Oh I see it now. I also found this post just now that confirms this behaviour. http://stackoverflow.com/questions/17539367/python-dictionary-keys-in-complexity – Rash Nov 05 '14 at 19:47
  • 1
    @Rash: [`collections.abc.Mapping`](https://docs.python.org/3/library/collections.abc.html) implements `__contains__()` in terms of `__getitem__()`. I can't imagine why Python wouldn't do the same for `dict`. – Kevin Nov 05 '14 at 19:47