Python哈希表__contains__方法报错：'NoneType'对象不可下标访问

Hey there! The error you're seeing happens because you're trying to access the [0] index of a None value in your array. Let's break down the problem and fix it step by step.

The Root Cause #

In your original __contains__ method, you first check self.array[position][0] == key before verifying if self.array[position] is None. If that position is empty (i.e., None), trying to get [0] from it throws the TypeError you're seeing—since None doesn't support subscripting.

Fixed contains Method #

Here's the corrected version of your method, with the check order reversed:

def __contains__(self, key):
    position = self.hash_value(key)
    for _ in range(self.table_size):
        # First check if the position is empty
        if self.array[position] is None:
            return False
        # Then check if the key matches
        elif self.array[position][0] == key:
            return True
        # Move to the next position for linear probing
        position = (position + 1) % self.table_size
    return False

Why This Works #

• We first verify if the current position is None: In linear probing, once you hit a None slot, you know the key can't exist in the table (since we wouldn't have skipped over a None to insert a key later). So we can immediately return False.
• Only if the slot isn't None do we check if the key matches. This avoids trying to subscript a None value.
• If we loop through all slots without finding the key or a None, we return False (meaning the table is full and the key isn't present).

Testing the Fix #

With this corrected method, your existing unit test should run without errors:

def testContains(self):
    my_table = HashTableLinear(3)
    my_table["Julian"] = "FIT1008"
    my_table["Phillip"] = "FIT1045"
    self.assertEqual("a" in my_table, False)
    self.assertEqual("Julian" in my_table, True)

You might also want to add a test case for a key that would trigger linear probing (e.g., a key that has the same hash as an existing one) to ensure the probing logic works correctly!

内容的提问来源于stack exchange，提问作者Sook Lim