Well, the hash table also uses list for handling collisions, but also using it to doubly link all elements. And it's true, on modern hardware linked list are o

Well, the hash table also uses list for handling collisions, but also using it to doubly link all elements. And it's true, on modern hardware linked list are often bad due to data locality making iteration bad ... but that data structure was designed before (while, as said, revamped meanwhile ...) But it's quite fancy. If you deal with it with "proper" indexed keys data will be packed in an array (or vector, ifyou prefer C++ terms; while most data stored in there is just pointers taking away some benefit of the packing...) while also keeping the doubly-linked-list pointers and once you have holes in it or string keys or something it plays hash and gives away some of the ordered storage ... In the end that extra bookkeeping everywhere makes it slow and bloated for everything, but from a usage perspective it's quite nice.