Ah, I found my answer. Sets are stored in both a skip list and a hash table. So the overhead is indeed high.