>This works because the elements in the array are close to each other in the physical memory. But with a hash, my understanding is that they wouldn't be so clos

>This works because the elements in the array are close to each other in the physical memory. But with a hash, my understanding is that they wouldn't be so close, and thus we wouldn't benefit from this spatial locality effect. By the same logic, when n is small, they will be close and benefit from cache locality as well.