List index out of range

Question

I'm trying to create my own Hash data structure in python. In __init__ I initialize a list (m_list) of size m and in another function I add hashes to it from my hash function.

I'm now trying to search through the list, looking for value k. I'm getting a list index out of range error on the if self.m_list[i] == k: line.

class Hash:
    def __init__ (self, n, m, m_list=None):
        self.n = n
        self.m = m
        self.a = choice(range(1, n))
        self.b = choice(range(n))

        if m_list is None:
            m_list = []
        self.m_list = m_list * m

    def search(self, k):
        found = False
        for i in self.m_list:
            if i is not None and found is False:
                if self.m_list[i] == k:
                    found = True
        if found:
            print True
        else:
            print False

I created m_list using guidelines from Create an empty list in python with certain size

zstewart · Accepted Answer · 2015-02-09T22:17:36.483

There are multiple problems with this code:

1) Indexing a list with its own contents.

for i in self.m_list:

when you loop on a list in python using this syntax, the value in the variable (i) is the value from in the list, not the index for that iteration.

There are two choices of ways to solve this. If you, for some reason need to have the index, you can loop by using the range function to create the indices and loop over them, like so:

for i in range(len(self.m_list)):
    if not found and self.m_list[i] == k:
        found = True

Or you can just use python's native iteration over the contents of the list:

for item in self.m_list:
    if not found and item == k:
        found = True

Another option, if you want easy access to both the index and the value is to use enumerate. enumerate returns tuples containing the index of the value and the value itself, so you can use python's multi-assignment to have access to both:

for i, val in enumerate(self.m_list):
    if val == k:
        ...
    if i == some_index
        ...

The original code will only ever return true if m_list[i] == i == k, so if you indented to check that this condition held, you could just check m_list[k] == k.

2) As noted in Peter's answer, [] * m always gives [], so no matter what the indexes being provided are, the list will have zero length and therefore any index will be out of range. To get a list with length m, you need to have one element in the list to duplicate. You can use None or 0 as that value: [0] * m gives a list of m zeroes, and [None] * m gives a list of m none values.

I'd use `enumerate` for the version of the search method where you need the index for something - `for i, val in enumerate(self.m_list):` — Peter DeGlopper, Feb 09 '15 at 22:13

Peter DeGlopper · Answer 2 · 2015-02-09T22:04:31.423

You are not creating a list of size m. [] * m gives you [], as you can see in an interactive shell. The linked answers show how multiplying a list will shallow copy the contents of the list m times, but of course [] has no contents to copy. Try if m_list is None: m_list = [None] * m or something similar.

Your search method makes no sense to me (there are better ways to store just the existence of integers) but that's a separate problem.

List index out of range

2 Answers2