3 ms·

Seems to have changed in the implementation indeed and I now didn't spend much time thinking through the current implementation. But the old implementation had

Seems to have changed in the implementation indeed and I now didn't spend much time thinking through the current implementation. But the old implementation had pointers to next and last (previous) element in the list: https://github.com/php/php-src/blob/PHP-5.3/Zend/zend_hash.h#L59 https://github.com/php/php-src/blob/PHP-5.3/Zend/zend_hash.h...

tialaramex 3y ago
Oh I see. Yes, this is a very common way for C programmers - in particular - to make a hash table, it's the design that C++ enshrines as std::unordered_map and it's the data structure you'd have been taught in a University data structures course in the 1980s, and maybe even the 1990s [depending on who is teaching and where] While internally this is indeed using linked lists, I don't think you can make use of that from PHP which is what I'd imagined was meant. Suppose I had a million integers that I found somewhere, and then I want to splice in a different million integers I have, so that in total there are two million integers. With linked lists that's very cheap, basically instant, but with most data structure, including a hash table, not so much. Linked Lists are very rarely what you needed, even though when they are what you needed they're invaluable. They are really easy to implement in C, so it's sort of a "I've got a hammer, now all I see are nails" situation in C.
- johannes1234321 3y ago
  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.

tialaramex 3y ago

Oh I see. Yes, this is a very common way for C programmers - in particular - to make a hash table, it's the design that C++ enshrines as std::unordered_map and it's the data structure you'd have been taught in a University data structures course in the 1980s, and maybe even the 1990s [depending on who is teaching and where] While internally this is indeed using linked lists, I don't think you can make use of that from PHP which is what I'd imagined was meant. Suppose I had a million integers that I found somewhere, and then I want to splice in a different million integers I have, so that in total there are two million integers. With linked lists that's very cheap, basically instant, but with most data structure, including a hash table, not so much. Linked Lists are very rarely what you needed, even though when they are what you needed they're invaluable. They are really easy to implement in C, so it's sort of a "I've got a hammer, now all I see are nails" situation in C.

johannes1234321 3y ago
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.