# Complexity of len(hash_table)

This is complexity O(N), where N is max_size of hash_table:
def len(self):
return len([x for x in self])

and this should be with complexity O(1):
def len(self):
return MAX_HASH_TABLE_SIZE

But how about the size of has_table when counting only used indices?

#Get rid of indices with None, complexity O(N)
def shrink_hash_table(self):
return [x for x in self if x is not None]

#Hash_table size without None indices, complexity O(N) depends on size N of hashed dict
def len_dense_hash_table(self):
return len([x for x in shrink_hash_table(self)])

Am I right?

That makes sense, but I think you could turn:

`#Get rid of indices with None, complexity O(N)`
`def shrink_hash_table(self):`
`return [x for x in self if x is not None]`

`#Hash_table size without None indices, complexity O(N) depends on size N of hashed dict`
`def len_dense_hash_table(self):`
`return len([x for x in shrink_hash_table(self)])`

And just do:

`def __len__(self):`
`return len([x for x in self.data_list if x is not None])`

Although I am not sure this is the right answer. In the best case scenario, the length of the list will not grow too large and the time taken to represent it wonâ€™t grow too much, but in the worst case scenario, the list is full and it will have a time complexity of O(n).

So, I tryed changing to:

`def __len__(self):`
`return len([x for x in self if x is not None])`

and when I call the method, (`len(table)`) it is just the same length of the table as when I define `__len__` as:

`def __len__(self):`
`return len([x for x in self])`

So I guess I donâ€™t knowâ€¦

What I did was I declared a variable â€ślengthâ€ť when initiating list in init and whenever we are adding a tuple to the hashtable I increment the length by 1. In the len function, without iterating over the list, I just returned self.length and I think complexity is reduced to O(1). Let me know if you have any comments about it.

1 Like

Very good idea, I have tried it myself and I think itâ€™s working, also donâ€™t forget to decrement it by 1 as well whenever you are deleting an element.