1

Hey guys so I was trying to implement a simple hash table in Python and was just curious about why this doesn't work so when I initialize my map variable I first use this. 

class HashMap:
    def __init__(self):
        self.size = 10
        self.map = [[] for _ in range(10)] #What to focus on 

    def getHash(self, key):
        return key % self.size

    def add(self,key, value):
        #Get hashed bucket index
        bucket = self.getHash(key)
        self.map[bucket].append(value)


#To test my function. 
h = HashMap()

h.add(1, "Swag")

print(h.map)

When I do this my hash-map works perfectly fine getting the desired result:

[[], ['Swag'], [], [], [], [], [], [], [], []]

However, when I do this: 

self.map = [[]] * 10 #What to focus on

I then get this output:

[['Swag'], ['Swag'], ['Swag'], ['Swag'], ['Swag'], ['Swag'], ['Swag'], ['Swag'], ['Swag'], ['Swag']]

Does anyone know why this occurs? I'm a python newbie so anything would be nice Thanks!

Michael Gee
  • 252
  • 1
  • 4
  • 16

3 Answers3

1

Because you're not calling the list constructor, you haven't made any new list objects. List multiplication just duplicates the references to the same elements, (in this case, a single list).

The list comprehension that works,

self.map = [[] for _ in range(10)]

is equivalent to

self.map = []
for _ in range(10):
    self.map.append([])

But [[]]*10 is roughly equivalent to

self.map = []
ls = [[]]
for _ in range(10):
    self.map.extend(ls)
gilch
  • 10,813
  • 1
  • 23
  • 28
0

When you do * 10 you aren't making copies of the object, you're taking 10 references to the same object. If the object is mutable then changing one changes all of them. Your objects are lists which are definitely mutable.

Mark Ransom
  • 299,747
  • 42
  • 398
  • 622
0

Using repetition operator * to create a list of lists creates a list with elements where each list item references the same memory location.

Note: if you will modify any of these 5 items (in the below code example). It indirectly means to update the value of other items (with the same value) as well.

You can print the id of list elements in both the cases using id() function. It's clear in below code example with output.

# First case
list1 = [[67]] * 5
print(list1);
print(id(list1[0]))
print(id(list1[1]))
print(id(list1[2]))
print(id(list1[3]))
print(id(list1[4]))

"""
[[67], [67], [67], [67], [67]]
140366629136392
140366629136392
140366629136392
140366629136392
140366629136392
"""

List comprehension is a great way to deal with above problem in a best (Pythonic) way.

Note: Unlike above, we can easily create a list of lists where each list item references different memory locations.

We can use id() function print the ids of items and see if it's like in the previous code example.

# Second case
list2 = [[68] for i in range(5)]
print(list2);
print(id(list2[0]))
print(id(list2[1]))
print(id(list2[2]))
print(id(list2[3]))
print(id(list2[4]))

"""
[[68], [68], [68], [68], [68]]
140390813841224
140390813841032
140390813841480
140390813842056
140390813842120
"""

References: List of lists changes reflected across sublists unexpectedly

Thanks.

hygull
  • 8,464
  • 2
  • 43
  • 52