Does it have any conventional naming?
It looks like I've reinvented the wheel or something, but I have no idea how to google this thing, so I had to write it from scratch (probably not in the most efficient way).
I've been working on a Leetcode task (link), and I found it quite handy to use a hash function with the following features:
- Working on mutable sequances of hashable (and immutable) objects:
hash = MyHash(["cat", "dog", "pig"])
- Adding a new element to a sequance in O(1):
hash.add("rat")
- Removing the element in O(1):
hash.sub("pig")
- It should be order insensitive:
assert MyHash(["cat", "dog", "rat"]) == MyHash(["rat", "dog", "cat"])
The idea reminds me of the rolling hash concept, but then order insensitivity is not fulfilled.
The implementation is something like:
class MyHash:
MOD = int("1" * 19) # - prime, just in case
def __init__(self, sequence=[]):
self._hash_val = 0
self._len = 0
if sequence:
for element in sequence:
self.add(element)
def add(self, element):
self._len += 1
self._hash_val += abs(hash(element))
self._hash_val %= MyHash.MOD
def sub(self, element):
self._len -= 1
self._hash_val -= abs(hash(element))
self._hash_val %= MyHash.MOD
def __eq__(self, __o: object) -> bool:
return self._hash_val == __o._hash_val
def __len__(self):
return self._len