How to describe the time complexity of a continually running program with a stream of inputs?
I would say that you should not look at the overall runtime (as it will be dominated by $m =\infty$ anyway) and instead look at the expected complexity of processing a single element (or a group of them if it doesn't scale linearly).

I'm not entirely sure what you mean with "Tree lookup" but I will just guess and provide an answer for that:

Calculating the hash of a key with length $k$ is done in $\mathcal O(k)$.
The corresponding field in the hashmap/table/set is then retrieved with a single lookup.

Assuming your tree is a BST where each node is a key (256 chars, alphabet of size 26) and you compare either left or right side and you have 10 nodes in the tree:


The tree has $log_2(10) \approx 4$ levels (1,2,4,2 nodes)
For a lookup, in each level the current key has to be compared to the node's key. The chance that the first characters match is $\frac1{26}$. That the first two match $\frac1{26^2}$, and so on.
In most cases, you will have a mismatch at the all four nodes where a value is compared
Your average case thus involves a few (2-4) lookups (following left or right child pointers in the tree) and comparing a few letters. If the key matches, the whole key is compared but I assume that this doesn't happen very often.


Thus, the BST lookup has a better performance without further modifications.

Maybe more fitting for stackoverflow than cs.stackexchange but still, my suggestion for your problem would be the following:


Determine if the values in the collection have some pattern (if they are SHA hashes of random data or similar, very very likely not the case)
Look at the percentage of successful matches (I would guess very low)
Implement a custom "Hashing". If the items in your collections start with different letters (or 2, whatever), you only need the first letter of each element in your stream to know with which item from your collection you have to compare it (for equality).