[Python] Easy Multiplicative Hash, explained
The goal of this problem is to create simple hash function, not using build-in methods. One of the simplest, but classical hashes are so-called Multiplicative h
The goal of this problem is to create simple hash function, not using build-in methods. One of the simplest, but classical hashes are so-called **Multiplicative hashing**: https://en.wikipedia.org/wiki/Hash_function#Multiplicative_hashing.\nThe idea is to have hash function in the following form.\n![image](https://assets.leetcode.com/users/images/f1711e74-6a61-4569-bf5c-7c5bb8cbb6b2_1596358162.4602873.png)\n\nHere we use the following notations:\n1. `K` is our number (key), we want to hash.\n2. `a` is some big odd number (sometimes good idea to use prime number) I choose `a = 1031237` without any special reason, it is just random odd number.\n3. `m` is length in bits of output we wan to have. We are given, that we have no more than `10000` operations overall, so we can choose such `m`, so that `2^m > 10000`. I chose `m = 15`, so in this case we have less collistions.\n4. if you go to wikipedia, you can read that `w` is size of machine word. Here we do not really matter, what is this size, we can choose any `w > m`. I chose `m = 20`.\n\nSo, everything is ready for function `eval_hash(key)`: `((key*1031237) & (1<<20) - 1)>>5`. Here I also used trick for fast bit operation modulo `2^t`:  for any `s`: `s % (2^t) = s & (1<<t) - 1`.\n\nHow our `HashSet` will look and work like:\n1. We create list of empty lists `self.arr = [[] for _ in range(1<<15)]`. \n2. If we want to `add(key)`, then we evaluate hash of this key and then add this `key` to the place `self.arr[t]`. However first we need to check if this element not it the list. Ideally, if we do not have collisions, length of all `self.arr[i]` will be `1`. \n3. If we want to `remove(key)` element, we first evaluate it hash, check corresponding list, and if we found element in this list, we remove it from this list.\n4. Similar with `contains(key)`, just check if it is in list.\n\n**Complexity**: easy question is about space complexity: it is `O(2^15)`, because this is the size of our list. We have a lot of empty places in this list, but we still need memory to allocate this list of lists. Time complexity is a bit tricky. If we assume, that probability of collision is small, than it will be in average `O(1)`. However it really depends on the size of our `self.arr`. If it is very big, probability is very small. If it is quite tight, it will increase. For example if we choose size `1000000`, there will be no collisions at all, but you need a lot of memory. So, there will always be trade-off between memory and time complexity.\n\n```\nclass MyHashSet: \n    def eval_hash(self, key):\n        return ((key*1031237) & (1<<20) - 1)>>5\n\n    def __init__(self):\n        self.arr = [[] for _ in range(1<<15)]\n\n    def add(self, key: int) -> None:\n        t = self.eval_hash(key)\n        if key not in self.arr[t]:\n            self.arr[t].append(key)\n\n    def remove(self, key: int) -> None:\n        t = self.eval_hash(key)\n        if key in self.arr[t]:\n            self.arr[t].remove(key)\n\n    def contains(self, key: int) -> bool:\n        t = self.eval_hash(key)\n        return key in self.arr[t]\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]