Python by bytearray//bit-manipulation//bit-hack  [ w/Explanation]
Tutorial video in Chinese \u4E2D\u6587\u89E3\u984C\u5F71\u7247\n\n\u4E2D\u6587\u8A73\u89E3 \u89E3\u984C\u6587\u7AE0\n\nPython sol. based on bucket, bit-manipula
[Tutorial video in Chinese \u4E2D\u6587\u89E3\u984C\u5F71\u7247](https://youtu.be/aNyztT8dYmA)\n\n[\u4E2D\u6587\u8A73\u89E3 \u89E3\u984C\u6587\u7AE0](https://vocus.cc/article/651cfe97fd89780001a7c8c3)\n\nPython sol. based on bucket, bit-manipulation, and bit-hack.\n\nWhat we need is hashset, \nthus any data structure that can **act as bucket**, and \nstore **True/False** for existence flag is good enough for us to implement.\n\n---\n\nMehotd_#1\nPython solution based on native **bytearray**, faster but need more (redundant )space.\n\nReference:\n[Python official docs about bytearray](https://docs.python.org/3/library/stdtypes.html?highlight=bytearray#bytearray)\n\n\n\n---\n\n```\nclass MyHashSet:\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.hash_set = bytearray(1000001)\n\n        \n    def add(self, key: int) -> None:\n        \n        if not self.hash_set[key]:\n\t\t\n\t\t\t# set to True for existence of incoming element\n            self.hash_set[key] = True\n\n            \n    def remove(self, key: int) -> None:\n        \n        if self.hash_set[key]:\n\t\t\n\t\t\t# clear to False for removal\n            self.hash_set[key] = False\n\n            \n    def contains(self, key: int) -> bool:\n        """\n        Returns true if this set contains the specified element\n        """\n        \n\t\t# check the flag for existence judgement\n        if self.hash_set[key]:\n            return True\n\t\t\t\n        else:\n            return False\n```\n\t\t\t\n---\n\nMehotd_#2\nPython solution based on native bytearray with **bit-manipulation**.\n\nThis looks like C/C++ register level (bit-flag) operation on hardware.\n\nCompared to Method_#1, this one is slower a little bit, but much more compact in space.\n\nReference:\n[Python official docs about divmod()](https://docs.python.org/3/library/functions.html?highlight=divmod#divmod)\n\n[Python official docs about bitwise operators](https://wiki.python.org/moin/BitwiseOperators)\n\n---\n\n```\nclass MyHashSet:\n\n    def __init__(self):\n        """\n        Initialize your data structure here.\n        """\n        self.hash_set = bytearray(125001)\n\n        \n    def add(self, key: int) -> None:\n        \n        quotient, remainder = divmod(key, 8)\n\t\t\n        if not self.hash_set[quotient] & (1 << remainder):\n\t\t\t\n\t\t\t# set to True for existence of incoming element\n            self.hash_set[quotient] |= (1 << remainder)\n\n            \n    def remove(self, key: int) -> None:\n        \n        quotient, remainder = divmod(key, 8)\n\t\t\n        if self.hash_set[quotient] & (1 << remainder):\n\t\t\n\t\t\t# clear to False for removal\n            self.hash_set[quotient] &= ~(1 << remainder)\n\n            \n    def contains(self, key: int) -> bool:\n        """\n        Returns true if this set contains the specified element\n        """\n\t\t\n        quotient, remainder = divmod(key, 8)\n\t\t\n\t\t# check the flag for existence judgement\n        if self.hash_set[quotient]& (1 << remainder):\n            return True\n\t\t\t\n        else:\n            return False\n```\n\n\n---\n\nMehotd_#3\n\nJust like Method_2, this time, we use single integer as hashpool.\nFor key k, we just carry out corresponding bit flag set/check/clear in hashpool, to implement set operation.\n\n```\nclass MyHashSet:\n\n    def __init__(self):\n        \n        # initialize hashpool with 0b 0000000...0\n        self.hashpool = 0\n\n    def add(self, key: int) -> None:\n        \n        # raise corresponding bit flag for k\n        self.hashpool |= (1<<key)\n        return \n    \n    def remove(self, key: int) -> None:\n        \n        # clear corresponding bit flag for k\n        self.hashpool &= ~(1<<key)    \n\t\treturn\n\n    def contains(self, key: int) -> bool:\n        \n        # check corresponding bit flag for k\n        return self.hashpool & (1<<key)\n```
['Hash Table', 'Math', 'Bit Manipulation', 'Python', 'Python3']