usage
(1)
x = {}
y = 1
x[y] = "a" (1)
y = [1, 2]
x[y] = "a" (2)
The (2) in the above code is definitely wrong since list is an unhashable type. I googled why list is unhashable? It seems that the logic is that if you were to look something up in a dictionary, you would except the entries' names not to change. Since list is mutable we cannot hash it. Keys must be immutable.
Here comes my question! The (1) in the above code is totally Okay. But actually, y in (1) is also mutable.
(2)
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
x = {}
y = TreeNode(1)
x[y] = "a"
For the above code, how does the Python compute the hash code for the TreeNode object? I've checked the document. TreeNode inherits from Object which means it also inherits the __hash__ function. But I failed to find the description about default calculation of hash code. I thought the compiler may use each object's id?
Detail Implementation
Based on this article, Cpython adopts open addressing to solve the collision instead of using linked list. The reason is that using a linked list to store the pairs having the same hash but it would increase the lookup time e.g. not O(1) anymore. I can understand this part. But it seems that using open addressing also increase the lookup time since you need to prob an available slot. The author in the article said: "adding a key/value pair might take more time because of the probing but the lookup will be O(1) and this is the desired behavior."
Can anyone explain why open addressing make the lookup still O(1)? Or we can change this question a little bit. What's the prons and cons of comparing open addressing and linked list used for solving collisions?
