Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have a list of unique string. I don't want to destroy this string i need it.I only need to find out weather an given string S exist in this unique list.What would be the best data structure for this purpose.

share|improve this question

closed as off-topic by Jim G., gnat, MichaelT, BЈовић, Bart van Ingen Schenau Nov 5 '13 at 10:42

  • This question does not appear to be about software development within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

    
Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask –  gnat Nov 1 '13 at 11:08
2  
This question appears to be off-topic because it does not demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. –  Jim G. Nov 5 '13 at 3:42
add comment

3 Answers

up vote 6 down vote accepted

You could use a Set.

A Set is a data structure that can not contain duplicate objects, so you can just dump all your strings into it and it automatically filters out duplicates.

To explicitely check if a given string is already in the set you could call a contains() method.

See also: http://en.wikipedia.org/wiki/Set_%28computer_science%29 and the corresponding Java interface http://docs.oracle.com/javase/6/docs/api/java/util/Set.html

share|improve this answer
add comment

A HashSet of strings would give you good lookup performance but is only suitable if the strings are guaranteed to be unique.

share|improve this answer
    
Even if they are not unique, the HashSet will fulfill a contains-query correctly ;) –  Wilbert Nov 1 '13 at 12:35
add comment

Depends upon how many unique strings you have. There are at least three ways to store your strings.

List (Vector/Array) - keep either a sorted, or unsorted list of strings. You can then scan the list to find whether the string already exists. Adding a new string is either an append or an insert (depending upon whether you keep the list sorted).

Hash (Map/Associative Array) - You store the strings as keys into a hash/map, and you can count the occurences of each string as the values contained in the hash heys.

Trie - An N-ary tree structure where each node of the tree has a list/array of children, where each child is indexed by a character-substring differing from all other children. Leaves represent the terminal words (unique strings). The tree has depth at most equal to the length of the longest string.

Also, a simple hybrid of Hash and lists used in symbol tables (a long time ago), would hash(first character, last character) to smaller lists of strings. Provides reasonably quick access, a small number of compares on the list, and fairly easy to implement (a technique used in symbol tables a long time ago).

Another possibility: If you have a smaller number of strings to encode, a small possibility of false positives is not a concern, and you don't care to keep the string around, read about bloom filters.

share|improve this answer
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.