How to auto increment the keys in a HashMap?

Question

I have a multithreading app. Multiple threads are putting things into a Map in which each thing must have a unique ID. Right now I'm using a TreeMap for this purpose like this:

TreeMap<Integer, Thing> things = new TreeMap<>();
things.put(things.isEmpty() ? 0 : things.lastKey() + 1, thing);

But a TreeMap is not thread-safe, so I decided to replace it with a ConcurrentHashMap.

But how could I achieve the same using a HashMap? So how to generate a new unique key for each thing I put into it?

Why not use a concurrent tree map? Raw hash maps aren't inherently thread safe either. — Mad Physicist, Dec 01 '17 at 14:16
It looks to me like your last key will always be equal to size which means you can use any other thread safe Map implementation. Also why not a thread safe List as you seem so just build an ordered sequence. — A4L, Dec 01 '17 at 14:22
do you have to be using `Thing` here? cause if you want just separate ID's (integer, long, UUID, etc ) there are simpler ways — Eugene, Dec 01 '17 at 14:23
@MadPhysicist I could make my TreeMap concurrent using Collections.synchronizedMap() (@Oleg and any other collection) but I heard this can lead to a much worse performance than using a ConcurrentHashMap. (whole collection gets blocked vs. only the item accessed) — tom, Dec 01 '17 at 14:33
@A4L I didn't mention but items might also get removed, not only added. — tom, Dec 01 '17 at 14:45
@Eugene Thing objects I have to store in some collection that is thread-safe and every object in it should have a unique integer key. — tom, Dec 01 '17 at 14:47
@tom, OK then stick with the map, and if the keys do not have to be a sequence then use uuid as shown in Oscar's answer. — A4L, Dec 01 '17 at 14:54
Did you consider to use a concurrent list, e.g. _CopyOnWriteArrayList_? The list creates an integer key implicitly. — Andy, Dec 01 '17 at 14:55

tkruse · Accepted Answer · 2017-12-01T14:38:17.580

2

You can generate unique Integers using Javas AtomicInteger class. It has a thread-safe getAndIncrement() method for that purpose.

However, this may cause some unpredictable bug in HashMap even with different keys. Some example listed here: Is a HashMap thread-safe for different keys?

So be sure to use a thread-safe map, or some other faster thread-safe datastructure like a Vector. If you know an upper bound of how many elements will be added, using an array with the index from AtomicInteger would be fastest, as you can avoid all synchronization.

edited Dec 01 '17 at 14:38

answered Dec 01 '17 at 14:16

tkruse

10,222
7
53
80

@MadPhysicist Combined with `ConcurrentHashMap` why not? – Oleg Dec 01 '17 at 14:26

score 1 · Answer 2 · answered Dec 01 '17 at 14:16

1

Consider using an UUID for the keys, it's extremely unlikely that a collision will occur. Something like this:

// import java.util.UUID;
UUID uuid = UUID.randomUUID();
String randomUUIDString = uuid.toString();

answered Dec 01 '17 at 14:16

Óscar López

232,561
37
312
386

1

Without knowing OP's specific use case, can you really say that it's worth the effort? – Mad Physicist Dec 01 '17 at 14:18
2

Seems to fit the bill of "a new unique key for each thing". And is not too much of an effort ;) – Óscar López Dec 01 '17 at 14:19
Thank you, but I only need auto increment integers, not more. – tom Dec 01 '17 at 14:39

score 1 · Answer 3 · answered Dec 01 '17 at 14:55

1

Well you can write (something) like this:

Map<Integer, Integer> map = new ConcurrentHashMap<>();
AtomicInteger ai = new AtomicInteger(-1);

map.compute(x, (l, r) -> {
    return ai.incrementAndGet();
})

compute is documented to be atomic

answered Dec 01 '17 at 14:55

Eugene

117,005
15
201
306

How to auto increment the keys in a HashMap?

3 Answers3