0

So I am trying to make a hash function that put an element k into a 2D array based on it's mod. For this example the size of the outer array is 4. So to start out the hash table I want it to be a 2D array that has the size of the outer array to be 4. Then there will be 4 empty arrays inside the outer array. Like so...

n = 4
A = [[]]* n

Which is [ [], [], [], [] ] So when I use the hash function like this hash(A, 2) it should output this [ [], [], [2], [] ] based on this code below...

def hash(A, k):
    idx = k % 4

    for i in range(len(A)):
        for j in range(len(A[i])):
            if i == idx:
                print(A[i][j])
                A[i][j] = A[i][j].append(k)

So the problem is that it outputs this [ [], [], [], [] ] and not this [ [], [], [2], [] ].

I have tried...

def hash(A, k):
    idx = k % 4
    A[idx].append(k)

but this only outputs [[2], [2], [2], [2]] which is not what I want.

How do I make my hash function give me this output [ [], [], [2], [] ]?

(P.S. I know it's a lot better to simply just make an array of linked lists. I am doing this for a better understanding of hash table if they were implemented with arrays and to get a better understanding of 2D arrays.)

Ezrelle
  • 19
  • 3
  • `len(A[i])` is always 0, so nothing ends up happening. If you change to `A = [[] for i in range(n)]` then the second function should work. – alec Mar 04 '20 at 00:06
  • @blhsing why would you close my comment it's not the same as [link](https://stackoverflow.com/questions/240178/list-of-lists-changes-reflected-across-sublists-unexpectedly)? I need empty arrays and I need to append values to the end of the array based on the outer index's value. A simple "This is not possible in Python would have been a lot more useful." – Ezrelle Mar 04 '20 at 00:15
  • Note, python `list` objects are not arrays. – juanpa.arrivillaga Mar 04 '20 at 00:16

1 Answers1

1

The second solution doesn't work because of the behavior of the multiplication operator for lists. When someone writes A = [[]]*n, all of the n inner lists are, in fact, the same list (the same location in memory), so changing one of them changes every one of them. If A is created as A = [[] for _ in range(n)] instead, these inner lists aren't the same object anymore, and they'll work as you intended.

The first solution doesn't work for several reasons; the most immediate one is that len(A[i]) equals 0 at the start of the loop for every i, so the function will skip past it every time (and never increment it).

Even if you correct it, A[i][j] is not a list, so it would give you an error when you call .append() on it. The lists are A[i], and you'll want to append to them.

Not only that, but the first solution is subject to the same problem as the second one.

(Source:https://docs.python.org/3/library/stdtypes.html#common-sequence-operations, notes 2 and 3)

FernandoAMB
  • 46
  • 4