Functional data structure fast to add and unorded deletion
My recommendation is a straightforward hash map. If you have a good hash function for your distribution of keys, the time complexity for adding and removing (with an arbitrary key) is amortized $O(1)$.

EDIT: Hash maps can be purely functional if you want (example), they just become a whole lot less efficient. I don't think it's theoretically possible to get lower than $O(\log n)$, which is what you get from using a red-black tree as the backend. The linked HAMT implementation is also $O(\log n)$, just with a significantly smaller hidden constant.