I have a collection of strings that I want to filter. They'll be in this pattern:

```
xxx_xxx_xxx_xxx

```

so always a sequence of letters or numbers separated by three underscores. The max length of each string will be 60 characters. I might have a few million of these in my collection.

What data structure could I use to efficiently do something like this:

> 
> Get all strings starts with: "abc\_123\_456"
> 
> 
> Get all strings starts with: "def\_999\_888"
> 
> 
> etc..
> 
> 
> 

for example, I could do this:

```
List<String> matched = new ArrayList<String>();
for (String it : strings) {
    if (it.startsWith(match)) {
        matched.add(it);
    }
}

```

but that would take a long time if my collection is on the order of millions of strings, and worse yet if the number of matched strings is also high.

The high-level problem is that I want to answer the following question for an app I'm writing: "which of my friends have recommended product A for product B?". I could store this information in a sql table and run the following statement:

```
select recommender from recs where username='me' and prodIdA='a' and prodIdB='b';

```

I'm curious if something custom in java/C/C++ could run faster, using encoded flat strings like I have above:

> 
> myusername\_prodIdA\_prodIdB\_recommenderusername
> 
> 
> 

The idea being that you could do a starts-with operation on the whole collection of encoded strings to get your answer.

I know trying to implement a custom solution like this is most likely not usable in a production environment, so some sql db would be better, just curious though,

Thanks