Телеграмм чат группы javascript

1) У любой хэш-функции есть коллизии
2) Из-за них есть бакеты, которые на практике реализованы как списки.
3) При большом кол-ве коллизий все будет складываться в несколько списков.
4) Поиск по списку O(N)

источник

10:30пожаловаться #4

AI

Arthur Irgashev in JavaScript.Ninja

Artem Kobzar

1) У любой хэш-функции есть коллизии
2) Из-за них есть бакеты, которые на практике реализованы как списки.
3) При большом кол-ве коллизий все будет складываться в несколько списков.
4) Поиск по списку O(N)

это про худший случай

источник

10:33пожаловаться #5

AK

Artem Kobzar in JavaScript.Ninja

О большое и есть про худший случай

источник

10:33пожаловаться #6

AK

Artem Kobzar in JavaScript.Ninja

Там дальше можно просто посмоттреть на вероятность коллизии

источник

10:33пожаловаться #7

AI

Arthur Irgashev in JavaScript.Ninja

прикол в том, что хеш-фция даёт тебе индекс в бакете

источник

10:33пожаловаться #8

AI

Arthur Irgashev in JavaScript.Ninja

Artem Kobzar

1) У любой хэш-функции есть коллизии
2) Из-за них есть бакеты, которые на практике реализованы как списки.
3) При большом кол-ве коллизий все будет складываться в несколько списков.
4) Поиск по списку O(N)

и там не тупой перебор по списку идёт, который даёт O(n)

источник

10:33пожаловаться #9

AK

Artem Kobzar in JavaScript.Ninja

Посчитать распределение и получим что-то около O(0,00001 * N)

источник

10:34пожаловаться #10

AK

Artem Kobzar in JavaScript.Ninja

Или

источник