hash_table initialisation, what is happening?

Question

I have a quick question about the below code regarding hash tables. For line 5- what is happening? So we initialised 'hash_table' to be a dictionary. Then for each element 'i' in nums we do hash_table[i]?? But the hash_table is empty- since just initialised it? This is where I am confused. Is it correct to say that we are defining the keys by doing hash_table['i']? If this is the case, why +=1? (P.S. nums is a list of integers shall we say)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hash_table = defaultdict(int)
        for i in nums:
            hash_table[i] += 1

        for i in hash_table:
            if hash_table[i] == 1:
               return i

Does this answer your question? [How does collections.defaultdict work?](https://stackoverflow.com/questions/5900578/how-does-collections-defaultdict-work) — costaparas, Jan 06 '21 at 10:48
Who chose that name? It's not really a `hash_table`, rather a simple counter... — Tomerikoo, Jan 06 '21 at 11:28
Be aware that ``collections.Counter`` might be more suitable for this use-case. — MisterMiyagi, Jan 06 '21 at 11:36

Booboo · Accepted Answer · 2021-01-06T11:38:40.540

0

I think your understanding of the defaultdict is correct: If the key is not present, then the key will be added with a default value. In the case of a defaultdict(int), that default value will be 0. But what are you passing as nums? If nums is not empty then hash_table will not be empty after the first for loop. However, method singleNumber just returns a single value, which will be the first key of hash_table that appeared in the nums list only once. As Tomericlo pointed out, your hash_table is acting more like a set of counters counting the number of times that each distinct integer in nums appears. I have modified your code to insert a print statement (and missing import statements) and added a test case.

Note that if no integer in nums appears only once, then your code never finds a match and never issues a return statement, which is equivalent to returning the value None.

from collections import defaultdict
from typing import List


class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hash_table = defaultdict(int)
        for i in nums:
            hash_table[i] += 1

        print(hash_table) # added statement

        for i in hash_table:
            if hash_table[i] == 1:
               return i

# test case:  
solution = Solution()
print(solution.singleNumber([7, 6, 7, 12]))

Prints:

defaultdict(<class 'int'>, {7: 2, 6: 1, 12: 1})
6

edited Jan 06 '21 at 11:38

answered Jan 06 '21 at 11:22

Booboo

38,656
3
37
60

I think you missed the point of the question which is how come we can do `hash_table[i] += 1` if at that point in time `hash_table` is still empty and doesn't have a key `i`... – Tomerikoo Jan 06 '21 at 11:26
Also it doesn't return the first key, it returns the first number that appeared only once in the list – Tomerikoo Jan 06 '21 at 11:28
@Tomerikoo Perhaps. But the OP's code seems to be looking for a value of `1` after doing `hash_table[i] += 1`, from which I infer they expected a default value of 0 to have been added. Moreover, the OP asks, 'Why is my hash_table empty?", which I take to be the actual question. I have updated my answer anyway, – Booboo Jan 06 '21 at 11:29
The dict acts as a simple counter... Each number in the list does `+= 1` to the corresponding key. In the end, doing `if hash_table[i] == 1:` means that key appeared only once in the original list. Try as input `[7, 7, 6, 6, 12]` – Tomerikoo Jan 06 '21 at 11:30
@Tomericlo You are correct. I was assuming that each number in `nums` was distinct. Thanks. – Booboo Jan 06 '21 at 11:30

hash_table initialisation, what is happening?

1 Answers1