What about returning another dict_items instead of a set? As in (using the convention `d.items().mapping is d`):


    dict_items = type({}.items())

    def __xor__(self: dict_items, other):
        if isinstance(other, dict_items):
            new = self.mapping.copy()
            MISSING = object()
            for key, value in other:
                existing = new.get(key, MISSING)
                if existing is MISSING:
                    # (key, value) in (other - self)
                    new[key] = value
                elif existing == value:
                    # (key, value) in (self & other)
                    del new[key]
                else:
                    # (key, value) in (self - other)
                    new[key] = value
            return new.items()
        else:
            return set(self) ^ set(other)

I believe this wouldn't require any re-hashing. It would also allow for non-hashable values.