The data structure for this hashmap script

Question

I have a script in which I store values ​​in a hash map.

The keys are strings like

fruits fruits_citrus_orange fruits_citrus_lemon fruits_fleshly_apple fruits_fleshly fruits_dry 

etc.

Values ​​are some objects. Now for this input, let's say that fruit_fleshly I need to get all the cases when it starts with "fruit_fleshly" In the above case, I need to get

 fruits_fleshly_apple fruits_fleshly 

One way to do this is to make String.indexOf on top of all the keys. Is there any other effective way to do this instead of repeating all the keys on the map

Answer 1

although these are strings, but for me it looks like certain categories and subcategories, such as fruits, fresh fruits, citrus fruits, etc.

If this is the case, you can instead implement the Tree data structure. This would be most effective for a search operation.

since Tree has a parent-child structure, there is a root node and a child node. You may have a structure like this:

 (0) (1) (2) fruit |_____citrus | |_____lemon | |_____orange | |_____freshly |_____apple |_____ 

in this structure, let's say if you want to look for citrus fruits, you can just go to citrus fruits and list all your children. And finally, you can build the full name by combining the name as a path from root to leaf.

Answer 2

Map iteration seems like a pretty simple and straightforward way to do this. However, since you do not want to Maps#filterEntries over the keys yourself, you can use Guava Maps#filterEntries if you like to use a third-party library.

Here's how it works:

 Map<String, Object> = Maps.filterEntries( yourMap, Predicate.containsPattern("^fruits_fleshly")); 

But that would have repeated the map in the backyard too much. So, iteration still exists if you are concerned about efficiency.

Answer 3

Since the HashMap does not support any order for its keys, this is not a good choice for this problem. The best choice is TreeMap: it has methods for getting an extra map for a series of keys. These methods are executed in O (log n) time (n is the number of records), which is why it is better than iterating over the keys.

 Map subMap = myMap.subMap("fruits_fleshly", true, "fruits_fleshly\uffff", true); 

Answer 4

The nature of the hash map means that there is no way to make a “similar” comparison on the keys - you need to key.startsWith(input) over them all to find where key.startsWith(input) .

I assume that you can embed hash maps and split your keys. For instance,

 { "fruits":{ "citrus":{ "orange":(value), "lemon":(value) }, "fleshly":{ "apple":(value), "":(value) } } } 

... etc..

The performance implications are probably horrifying on a small scale, but this may not matter in the home context, but perhaps not so bad if you are dealing with a lot of data and only with a few nesting layers.

Alternatively, create a Category object with a list of categories (subcategories) and a list of entries.

Answer 5

I believe Radix Trie is what you are looking for. This is similar to @ ay89's solution.

You can simply use this open source library Radix Trie example . It works better than O (log (N)). You can find the hash map assigned to the key in average constant time (the number of underscores in the search key string) with a decent implementation of Radix Trie.fruits fruits_citrus_orange fruits_citrus_lemon fruits_fleshly_apple fruits_fleshly fruits_dry

 Trie<String, Map> trie = new PatriciaTrie<>; trie.put("fruits", hashmap1); trie.put("fruits_citrus_orange", hashmap2); trie.put("fruits_citrus_lemon", hashmap3); trie.put("fruits_fleshly_apple", hashmap4); trie.put("fruits_fleshly", hashmap5); Map.Entry<String, Map> entry = trie.select("fruits_fleshy"); 

If you want one hash map to be returned, you can get slightly better performance if you implement your own Radix Trie.