What DS to use for search a string in set of strings in Java?

Question

I have a few strings(about 100) and I want to store them in a Data Structure and then later I want to search it for a particular string to check whether its present or not. What DS in Java will be best in this case for fast searching.

The actual use case is that I want to create a catalog for books and need to find out whether a particular title is present or not.

All the strings are unique. I dont want to implement any DS myself but want to use any of the Collections already present in Java.

Any dictionary data structure would do – Dan Apr 09 '12 at 12:00 — Dan, Apr 09 '12 at 12:00

score 3 · Answer 1 · answered Apr 09 '12 at 12:02

The obvious choice would be to use an implementation of the Set interface. This exposes a convenient contains method, which you can use to test if a specific title exists. You could also use an implementation of a Map, like HashMap to associate a String with an object. This will allow you to store information about your book and easily access it.

The advantage of using a Set or a Map, is that searching for a specific key is very effective. You can't have duplicate items in a Set.

score 2 · Accepted Answer · answered Apr 09 '12 at 11:59

2

why don't you use any List to store all the strings and use contains() method to find whether it present in your List or not.

You can even use Set but in that case your strings must be unique.

answered Apr 09 '12 at 11:59

Chandra Sekhar

18,914
16
84
125

In case of a list and millions of book titles O(n) would be searching time hence tree or hash tables are suitable. – Yavar Apr 09 '12 at 12:02
@Yavar He has mentioned that list is about 100 length. Thats why I suggested about List. – Chandra Sekhar Apr 09 '12 at 12:03
What is the time complexity for search in case of List? – aamadmi Apr 09 '12 at 12:09
@Neerav its O(n) in worst case, as it will check each element and compare. you can also see http://stackoverflow.com/questions/5771740/time-complexity-of-containsobject-o-in-an-arraylist-of-objects – Chandra Sekhar Apr 09 '12 at 12:10
vs O(1) for lookups in a `HashSet`, for example. – darrengorman Apr 09 '12 at 12:17
@milkplusvellocet yes of course. Thats the only reason +1 by me for kgiannakakis – Chandra Sekhar Apr 09 '12 at 12:20

score 1 · Answer 3 · answered Apr 09 '12 at 11:59

1

Use a Set implementation. The contains method will tell you if a particular String title is present or not

answered Apr 09 '12 at 11:59

darrengorman

12,952
2
23
24

What DS to use for search a string in set of strings in Java?

3 Answers3