Representing sets with constant time equality testing

Abstract

Most data structures for sets minimize the time spent on the operations insert, delete, and member. Using a tree-based representation scheme, a sequence of N operations has complexity O(logN) per operation. However, if we also allow the operation equal(Si,Sj), where Si and Sj are two different sets, the complexity can be O(N) per operation, since set equality testing can require linear time. In this paper we present two tree-based representation schemes that support the operation equal(Si,Sj) in constant time. The first scheme is very simple and establishes an upper bound of O(logN + k) per operation for a sequence of N operations, where k is the number of sets. A variation on this scheme uses hashing and gives an expected complexity of O(k) per operation. Our second set representation achieves O(logN) amortized complexity per operation.