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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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
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
A HashSet of strings would give you good lookup performance but is only suitable if the strings are guaranteed to be unique.
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.