# Hashtable collision resolution in PHP 7

- Thread: https://externals.io/message/99056
- Original archive: https://news-web.php.net/php.internals/99056
- Started by Pawel Por on 2017-05-16T09:28:36+00:00
- Messages: 4
- Reply by email to internals@lists.php.net
- More for agents: search with https://externals.io/search.md?q={query} · JSON API at https://externals.io/api · documentation at https://externals.io/llms.txt

---

## #99056 — Pawel Por — 2017-05-16T09:28:36+00:00

URL: https://externals.io/message/99056#99056

Hi

I'm trying to understand why PHP 7 hashtables are more efficient than
PHP 5 hashtables.
I'm confused about hashes that are in collision.
In PHP 5 there were a linked lists to resolve collisions.
What about PHP 7 ? Are there still linked lists ?
I read somewhere that the solution taken in PHP 7 is L1 cache friendly
so I conclude PHP 7 cannot resolve collisions using linked lists but
rather arrays.
If so please write me where the buckets that are in collision are
stored in memory I mean by what field the array is pointed to by (e.g.
zval.u2.next) and a few words of high level design of how it is
implemented.

thanks for help

---

## #99057 — Sara Golemon — 2017-05-16T10:00:06+00:00

URL: https://externals.io/message/99056#99057 · In reply to: #99056

https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html


> Hi
>
> I'm trying to understand why PHP 7 hashtables are more efficient than
> PHP 5 hashtables.
> I'm confused about hashes that are in collision.
> In PHP 5 there were a linked lists to resolve collisions.
> What about PHP 7 ? Are there still linked lists ?
> I read somewhere that the solution taken in PHP 7 is L1 cache friendly
> so I conclude PHP 7 cannot resolve collisions using linked lists but
> rather arrays.
> If so please write me where the buckets that are in collision are
> stored in memory I mean by what field the array is pointed to by (e.g.
> zval.u2.next) and a few words of high level design of how it is
> implemented.
>
> thanks for help

---

## #99059 — Dmitry Stogov — 2017-05-16T11:47:34+00:00

URL: https://externals.io/message/99056#99059 · In reply to: #99056

PHP 7 still uses a kind of linked list for collision resolution (trough zval.u2.next) and this is still an expensive operation.

---

## #99060 — Julien Pauli — 2017-05-16T11:49:56+00:00

URL: https://externals.io/message/99056#99060 · In reply to: #99057

> https://nikic.github.io/2014/12/22/PHPs-new-hashtable-implementation.html
>
> 
> > […]
>

I also blogged about that,

http://jpauli.github.io/2016/04/08/hashtables.html

Short answer : yes, there is a single-linked-list to solve collisions in
PHP 7 hashtables.


Julien.