Python哈希表程序存疑且报List index out of range错误，求解决

Hey there, let's break down why you're hitting that List index out of range error and get your hash table working properly.

What's Causing the Error? #

The core issue is in how you initialize your hash table. In your __init__ method, you set self.table = []—this creates an empty list with no pre-allocated slots. When you calculate a hash index and try to access self.table[hashing], the list doesn't have that index yet (since it's empty), hence the out-of-range error.

Additionally, your isFull method checks len(self.table) == self.max, which won't work once we fix the initialization (because the table's length will always equal self.max). We'll need to adjust that too.

Corrected Code with Explanations #

Here's the fixed version of your code, with key changes highlighted:

class Hash(): 
    def __init__(self, user): 
        self.max = user 
        # 1. Pre-allocate the hash table with self.max slots, all set to None
        self.table = [None] * self.max 

    def isFull(self): 
        # 2. Check if there are no empty slots left (instead of checking list length)
        return all(slot is not None for slot in self.table)

    def insert(self, item): 
        if self.isFull(): 
            print('Hash table is full')
            return self.table 
        
        hashing = self.index(item) 
        # Now self.table[hashing] is safe to access because we pre-allocated slots
        if self.table[hashing] is None: 
            self.table[hashing] = item 
        else: 
            # Linear probing: find the next available empty slot
            for a in range(self.max):
                # Start from the next slot after hashing, wrap around if needed
                probe_index = (hashing + a) % self.max
                if self.table[probe_index] is None:
                    self.table[probe_index] = item
                    break
        return self.table 

    def index(self, item): 
        hashval = int(item) % self.max 
        return hashval 

    def searching(self, item): 
        # Bonus: Basic search implementation using linear probing
        hashing = self.index(item)
        for a in range(self.max):
            probe_index = (hashing + a) % self.max
            if self.table[probe_index] == item:
                return f"Found {item} at index {probe_index}"
            if self.table[probe_index] is None:
                return f"{item} not found in the hash table"
        return f"{item} not found in the hash table"

user = int(input('Enter a number for the maximum number of items that can be stored in the hash table: '))
hash_table = Hash(user)

Key Changes: #

• Pre-allocated Table: self.table = [None] * self.max creates a list with exactly self.max slots, each initialized to None. This ensures any valid hash index (0 to self.max-1) exists in the list, eliminating the index error.
• Fixed isFull Check: Instead of checking list length, we use all(slot is not None for slot in self.table) to verify if every slot is filled.
• Improved Linear Probing: The original conflict handling looped through the entire table from the start, which could miss slots or be inefficient. The new code starts probing from the hashed index and wraps around using modulo, which is the standard linear probing approach.
• Added Basic Search: I included a simple searching method that uses linear probing to find items, to complete the hash table functionality.

Testing the Fix #

Let's test it with a quick example:

# If user enters 5 as max
hash_table.insert("10")  # Hash: 10 %5 =0 → slot 0 filled
hash_table.insert("7")   # Hash:7%5=2 → slot2 filled
hash_table.insert("15")  # Hash:15%5=0 (conflict) → finds next empty slot (1)
print(hash_table.table)  # Output: ['10', '15', '7', None, None]
print(hash_table.searching("15"))  # Output: Found 15 at index 1

This should run without any index errors, and the hash table will handle collisions properly.

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