I see. Note that the amount of lookups for the hash table only holds if there is no collision, but that may be a fair assumption. Given that the data are string

I see. Note that the amount of lookups for the hash table only holds if there is no collision, but that may be a fair assumption. Given that the data are strings, a specialized datastructure such as a Trie or suffix array might work well, especially if it is possible to exploit redundancy in the data (i.e., repeated substrings). There are specialized datastructures used in full-text search which will probably be useful. In any case dealing with this amount of data might mean that using an off-the-shelf database might be a good idea.