0

I need to get the position of a string in a List in constant time,

but do not find any such Java implementation.

Maybe is there no need for that, given current computers memory size ;-)

LinkedHashMap are interesting but do not maintain a position.(ref)

Any clue ?

user1767316
  • 3,276
  • 3
  • 37
  • 46

2 Answers2

0

A custom implementation could keep a list and a map in parallel. The map containing the strings as keys and their list index as values. Assuming each string occurs only once.

Reto Höhener
  • 5,419
  • 4
  • 39
  • 79
  • yes, thanks, I found that comment in another thread (the link I provided ?), I implemented a solution like that, but it can't be thread safe since LinkedHashMap is not. ConcurrentSkipListMap seems to be a solution but is 3-5 times slower, maybe not searching in linear/constant time. Now looking at [cafeine](https://github.com/ben-manes/caffeine) for this purpose – user1767316 Dec 17 '20 at 10:41
  • 1
    @user1767316 even if you'd use a Map and List implementation of which both are thread-safe, the composition of both wouldn't be. Once you compose multiple classes, you have to control thread-safety yourself. – Felix Dec 17 '20 at 11:11
  • OK, so how could be added/implemented thread safety regarding [my own answer](https://stackoverflow.com/a/65339573/1767316) – user1767316 Jan 08 '21 at 13:38
  • OK, @codeflush.dev, so how could be added/implemented thread safety regarding [my own answer](https://stackoverflow.com/a/65339573/1767316) , anything more convenient than using the m class in synchronized blocks only ? synchronized(m){ m.any_m_methodcall();} How should I use Collections.synchronizedList() and or Collections.synchronizedMap( ... ) if it exists ? – user1767316 Jan 08 '21 at 13:44
0

As reminded by @Reto Höhener like said in the ref of my question to keep original insertion order index positions, one can mirror the keys in the KeySet in something like an ArrayList, keep it in sync with updates to the HashMap and use it for finding position

for a List: Filling an ordered ConcurrentMap like ConcurrentSkipListMap with a list of positions as values should do the trick. Cafeine could also do the job but I still need to look at it.

final int[] index = {0};
     Stream<ComplexObject> t = someListOfComplexObject.stream();
     ConcurrentMap<String, List<Integer>> m = 
          t.collect(Collectors.groupingBy(
               e -> e.getComplexStringElem(),
               Collectors.mapping(
                    e -> index[0]++,
                    Collectors.toList()
               ),
               ConcurrentSkipListMap::new));
user1767316
  • 3,276
  • 3
  • 37
  • 46