How to hash a ring buffer of integers?

I am using Python. I have some lists containing integers, but they are actually ring buffers.

The following are rules by examples:

• We do not add new elements or modify any elements. These rings are immutable.

• No repetitive elements in a ring.

• If two lists have different lengths, they are not the same ring.

• Between two lists of the same length, if one list, after arbitrary times of ring shift or reversion, can be identical to the other, the two rings are equal. For example, [1, 7, 9, 2, 5] and [7, 9, 2, 5, 1](ring shifted) are equal, [1, 7, 9, 2, 5] and [1, 5, 2, 9, 7](ring shifted and reversed) are equal, but [1, 7, 9, 2, 5] and [7, 1, 9, 2, 5] are not equal.

I want to quickly identify whether two rings are equal.

One method is to compare their elements, another method is to find a good hashing method. I tried shifting two lists to their normal state and compare if their elements are identical (or identical after reversed), but it's too slow.

I think hashing is a better choice. So what hashing method is good for this kind of ring buffers?

The following is what I currently have:

import random
from time import perf_counter
from typing import List, Tuple
class Ring:
def __init__(self, ids:List[int]) -> None:
self.ids = ids
def get_shifted(self, n:int) -> 'Ring':
result_list = self.ids.copy()
for i in range(n):
head = result_list[0]
result_list.remove(head)
result_list.append(head)
return Ring(result_list)
def get_normalized(self) -> 'Ring':
min_i = self.ids.index(min(self.ids))
shifted = self.get_shifted(min_i)
return shifted
def get_reversed(self) -> 'Ring':
result_list = self.ids.copy()
result_list.reverse()
return Ring(result_list)
def __eq__(self, other: 'Ring') -> bool:
if len(self.ids) != len(other.ids):
return False
normalized1 = tuple(self.get_normalized().ids)
normalized2 = tuple(self.get_reversed().get_normalized().ids)
normalized_other = tuple(other.get_normalized().ids)
return normalized1 == normalized_other or normalized2 == normalized_other
@staticmethod
def Random() -> 'Ring':
unduplicated = set()
while len(unduplicated) < ring_capacity:
unduplicated.add(random.randint(0, 20))
return Ring(list(unduplicated))
if __name__ == '__main__':
random.seed(1)
ring_capacity = 5
num_rings = 2000
ring_set = []
random_rings = [Ring.Random() for _ in range(num_rings)]
start = perf_counter()
for ring in random_rings:
if ring not in ring_set:
ring_set.append(ring)
end = perf_counter()
print(end - start)
print(f'{len(ring_set)} out of {num_rings} unduplicated rings')

Instead of coming up with a special hash that would provide the same hash code for equivalent lists, it is probably simpler to convert each ring to a canonical form.

Of all the possible shifts/reversions, for example, you can select the one that is lexically smallest.

After conversion to canonical form, equivalent rings are identical, so if you want to hash, then you can use whatever hash you want, and if you need to compare, you can just do a simple linear comparison.

It's faster and simpler to just compute a normalized form at construction:

class Ring:
def __init__(self, ids:List[int]) -> None:
self.ids = ids
i = ids.index(min(ids))
self.normed = min(
ids[i:] + ids[:i],
ids[i::-1] + ids[:i:-1]
)
def __eq__(self, other: 'Ring') -> bool:
return self.normed == other.normed

Output with yours:

15.41106627508998
1896 out of 2000 unduplicated rings

Output with mine:

0.38525977171957493
1896 out of 2000 unduplicated rings

Output with the below (Attempt This Online!):

0.0007639830000698566
1896 out of 2000 unduplicated rings

(Hmm, I just realized that by moving the normalization into construction, I moved it out of the timing. But if I include the random_rings = [Ring.Random() for _ in range(num_rings)] in the timing, the whole thing still only takes ~0.03 seconds.)

The last is modifying your using code to make your ring_set an actual set instead of a misnamed list:

    start = perf_counter()
ring_set = set(random_rings)
end = perf_counter()

With the Ring class providing meaningful hashes:

class Ring:
def __init__(self, ids:List[int]) -> None:
self.ids = ids
i = ids.index(min(ids))
self.normed = min(
ids[i:] + ids[:i],
ids[i::-1] + ids[:i:-1]
)
self.hash = hash(tuple(self.normed))
def __eq__(self, other: 'Ring') -> bool:
return self.normed == other.normed
def __hash__(self):
return self.hash

Your question is rather broad so any recommendation will probably be rather vague, too. It sounds like you are processing gigantic amounts of data - otherwise comparison would certainly be faster than hashing.
You cannot use the standard cryptographic hash functions as they are not location independent. Rather look for location preserving hash functions (LP Hashes) like the Nilsimsa Hash. The idea is to have similar input create similar output where similar here means, that the starting point is arbitrary and still the set would create the same hash. Btw., a very simple hash for finding candidates would be the conventional (SAE J1708) checksum.