Best data structure/algorithm for word search?

[tr00don]

Given a list of words, I need to determine whether a string perfectly matches a word in the list.

Which of the data structures below supports the fastest search/match algorithm?

1. a single-column (VARCHAR(), PRIMARY KEY) SQLite database table
2. a HashTable()
3. a Dictionary<string, int>

Your help is greatly appreciated.

[BigEd781]

Maybe you should ask your teacher.

[tr00don]

Hm... you either try to imply that it's obvious (which to me it won't be until I run tests with each of the three options) or you just don't know. Either way your answer is not helping.

[Mutant_Fruit]

I can give you a 100% correct and accurate answer - it depends. Any of those can potentially be the fastest depending on your dataset. The real answer is - who cares which is fastest unless it turns out to be a bottle neck. There are dozens of algorithms out there for string matching so if the simplest solution is a performance problem, then try another

[tr00don]

All right, I chose Dictionary<string, int>. I need to store a lot of data but it's really fast, so performance is not an issue. The problem is, the application crashes with an OutOfMemory exception when working memory reaches 1 GB.

I know that objects in C# cannot be larger than 2 GB, but a 1 GB limit for the whole program? This is a 32-bit application. Any ideas?

Thanks.

[Mutant_Fruit]

Are you storing all that massive amount of info in one single dictionary? It's possible that the dictionary itself is resizing large enough that it alone is trying to allocate a massive amount of contiguous memory and that can't be satisfied by the operating system so the app is shut down.

If so you could just split your single massive dictonary of 1 billion items into several smaller dictionaries. Maybe based on the first char in the string like: a-e, f-j, k-p, etc. (assuming the first char is semi-random)

[tr00don]

Thank you for your suggestion, it works. I created an array of 16 dictionaries (~ 2 letters each) and now the application work memory can go above 1 GB.