CODEWITHSUNDEEP
javaspring-boot
Joy
Joy

Reputation: 4511

Prefix based search in Spring boot application

I am going to implement an API that will take text as input as follows:

/api/tags/namePrefix?prefix=<prefix>

In this API, I am going to return a set of Key, Value pairs in API response.

I am not going to store the data in DB, but in application memory only. So I am thinking of using a ConcurrentHashMap for the same.

I understand, for prefix search, Trie may be data structure. But I did not find any concurrent flavor of Trie where I can store the keys along with values.

Could anyone please give any pointers regarding the same ?

Upvotes: 0

Views: 222

Answers (1)

Daniil
Daniil

Reputation: 19

There's no concurrent implementation of the red-black tree in Java. But there is ConcurrentMap interface with 2 out-of-box realizations: ConcurrentHashMap and ConcurrentSkipListMap.

ConcurrentMap<String, String> foo = new ConcurrentHashMap<>();
ConcurrentMap<String, String> bar = new ConcurrentSkipListMap<>();

  • ConcurrentHashMap is thread-safe HashMap based structure with additional optimizations for performance. It provides constant-time performance that is O(1) for the basic operations like get() and put().

  • ConcurrentSkipListMap is used for cases when ordering of keys is required. It provides O(log(n)) time cost for the containsKey(), get(), put() and remove() operations and their variants.

Simply speaking, you can use ConcurrentHashMap if you don't need to care about keys order. More details you can find in this article

Upvotes: 1

Related Questions