What do you do with the data? Do you construct a new structure often? Do you need to iterate through the whole structure or do you typically only need to access a few elements? Is this in a persistent application or in a (CGI) script that needs to start for each request?

100_000 elements is not that much (it takes about 11 Mb on my machine if filled with simple integers), so what do you put in the keys and values?