Functional data structure fast to add and unorded deletion I am looking for a functional data structure that would work in this role.

Adding items to the struct happens often. Removing items from the struct happens as often as adding them but I have no way of knowing what order the deletion happens in. Over the long term addions will equal removal Rarely I need all items currently in the struct

I thought of using a queue but out of order removal from a queue is expensive.
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.