But what happens when the number or size of items begins to exceed available memory? Tens of millions of names start to occupy hundreds of megabytes. Inserting an item into a sorted list of ten million items takes significant time. A hash table helps with the speed issue, but at the cost of having to store the hash codes along with the strings, and the additional runtime overhead of having to handle hash collisions. When you get to hundreds of millions of items, it's unlikely that you'll have enough memory to hold the entire table in RAM. At that point you need to make a choice: find an efficient way to store and lookup items on disk, or find a faster and more memory-efficient way to do it within the available memory.
Previous Topic
