I'm looking for a fast Set or Map implementation that has a weaker thread-safety in favor of speed.
The idea is to have a data structure that can quickly be checked whether it contains a (Long) entry at best without thread-synchronization. It is okay if a new entry that is written by another thread becomes visible to the other threads at a later time.
I know already that the non thread-safe HashSet Java standard implementation may disrupt the datastructures while inserting a new element and a reader thread ends up in an endless loop during lookup.
I also know that whenever the writing methods are using synchronized blocks, all reader methods should be synchronized as well in a multi-threaded implementation.
So my ultimate goal is to find a possibility to insert in O(1) and lookup in O(1) where
- the inserts might get queued in some way for bulk insert at a sync-point (if there is no other possibility)
- the read does not get stuck but should not need to wait (for any writers)
- the inserted element should be visible to any subsequent reads of the thread that added the element (which might prevent the aforementioned queue)
I am experimenting with Longs that represent hash-codes mapping to Lists of usually one, sometimes two or more entries.
Is there a way to achieve this e.g. via an array and compare-and-exchange and which is faster than using the ConcurrentHashMap?
How would a sketched implementation look like given that the input consists of node-ids (type Long) of a graph that is traversed with multiple threads that somehow exchange information which nodes have been visited already (as described in the list above).
I really appreciate any comments and ideas, thanks in advance!
Edit: Added extended information on the actual task that I am doing some hobby-research on and which led me to asking the question here in the forum.