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…