hash table

[Redjik]

http://nikic.github.io/2012/03/28/Understanding-PHPs-internal-array-implementation.html

• nTableSize specifies the size of the internal C array. It is always the next power of 2 greater or equal to nNumOfElements. E.g. if an array stores 32 elements, the internal C array also has a size of 32. But if one more element is added, i.e. the array then contains 33 elements, the internal C array is resized to 64 elements.
  
  This is done to always keep the hash table efficient in space and time. It is clear that if the internal array is too small there will be many collisions and the performance will degrade. If the internal array is too big on the other hand, we’d be wasting memory. The power-of-2 size is a good compromise.

Не могу осилить.
Почему будет много коллизий - их же будет одинаковое кол-во независимо от величины.

1) У нас всегда юзается одна и та же функция для хэша.
2) Потом применяется маска, чтобы числа были не сильно большие.

То есть даже если хэши будут одинаковые, то после применения маски индексы массива будут одинаковые.

ЗЫ. Статья классная, все понятно и разжевано, кроме этого момента. Посмотрел как поиск происходит
http://lxr.php.net/xref/PHP_5_4/Zend/zend_hash.c#913
все логично

Не понимаю или Никита ошибся или я чего-то недопонимаю именно с nTableSize

 

[Redjik]

Могу предположить, что умножение на 2 происходит именно из-за битовой маски и для избежания коллизий не хешей, а hash & mask - для создания индекса
то есть для того, чтобы разные хеши не давали один и тот же индекс после применения маски.

 

[Вурдалак]

Коллизий будет много, потому что индексов не хватает. 20 элементов распределить на 32 индекса более-менее равномерно несложно. А 33 элемента на 32 индекса распределить уже невозможно: очевидно, что гарантированно найдутся 2 элемента с одинаковым значением hash & mask. И чем дальше — тем хуже.

 

[Redjik]

Пока писал, сам допер - взял виндовый инженерный калькулятор и проверил пример
193491849 & 63 = 9
193491849 & 127 = 9
193491849 & 255 = 137

то есть при добавлении 129 го элемнта будут коллизии для масок 127 и 63
поэтому и умножаем на 2

 

[Вурдалак]

А что ты проверил?

Коллизия — это, например, когда hash("foo") == 193491849 и hash("bar") == 264926089 при mask = 63, потому что 193491849 & 63 = 9 и 264926089 & 63 = 9. Очевидно, что чем больше разрядов мы сравним, тем меньше вероятность такого совпадения.

 

[Redjik]

Пример проверил, что же еще =)
Да, основной принцип понял. умножение на 2 для лучшего случая без коллизий. тогда поиск O(1), худший случай когда в массиве из 32 элементов после применения маски все значения попадают в один индекс - O(N).
Я просто не мог понять зачем умножать на 2, а это как раз для поиска лучшего случая и применения маски

 

[fixxxer]

чочочо, какое умножение на 2? где?

 

[hell0w0rd]

E.g. if an array stores 32 elements, the internal C array also has a size of 32. But if one more element is added, i.e. the array then contains 33 elements, the internal C array is resized to 64 elements.

Тут написано, что если массив хранит 32 элемента, размер хеша будет равен 32, затем если добавить еще один элемент, создастся новый хеш в два раза больше.
Хеш увеличивается в два раза при достижении очередной степени двойки.

 

[Вурдалак]

Кстати: http://habrahabr.ru/company/*****/blog/175085/ — на графике видно, что при достижении степени двойки есть тормоза.

 

[Redjik]

Тут написано, что если массив хранит 32 элемента, размер хеша будет равен 32, затем если добавить еще один элемент, создастся новый хеш в два раза больше.
Хеш увеличивается в два раза при достижении очередной степени двойки.

у меня проблемы с русским =) на английском мне такое проще сформулировать

 

[Redjik]

Кстати: http://habrahabr.ru/company/*****/blog/175085/ — на графике видно, что при достижении степени двойки есть тормоза.

наконец то я понимаю эту статью

 

[Breeze]

наконец то я понимаю эту статью

на эту тему можно глянуть phpng, там не judy, но тоже интересно стало

 

[Redjik]

на эту тему можно глянуть phpng, там не judy, но тоже интересно стало

а дак я же был на докладе на phpConf, там правда про звалы было в основном

 

[hell0w0rd]

Redjik, 16-19 слайд как раз о изменениях в HashTable

 

[fixxxer]

Хеш увеличивается в два раза при достижении очередной степени двойки.

Именно, никакой гарантии отсутствия коллизий быть не может. Просто в какой-то момент надо сделать реаллок, чтобы соблюсти баланс memory/cpu, округление в большую сторону от числа элементов - вполне ок компромисс. Поскольку это похапе, тут все неуправляемо и автоматом. В Java Hashtable есть такие конструкторы:

Hashtable()
Constructs a new, empty hashtable with a default initial capacity (11) and load factor (0.75).

Hashtable(int initialCapacity)
Constructs a new, empty hashtable with the specified initial capacity and default load factor (0.75).

Hashtable(int initialCapacity, float loadFactor)
Constructs a new, empty hashtable with the specified initial capacity and the specified load factor.

где

load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. The initial capacity and load factor parameters are merely hints to the implementation. The exact details as to when and whether the rehash method is invoked are implementation-dependent.

Generally, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the time cost to look up an entry (which is reflected in most Hashtable operations, including get and put).

Оно как бы hint, но подозреваю, что поведение php близко к new Hashtable(0, 0.5).

там правда про звалы было в основном

ну как бы в zval-е тоже бывает hashtable

typedef union _zvalue_value {
    long lval;                 /* long value */
    double dval;               /* double value */
    struct {                   
        char *val;
        int len;               /* this will always be set for strings */
    } str;                     /* string (always has length) */
    HashTable *ht;             /* an array */
    zend_object_value obj;     /* stores an object store handle, and handlers */
} zvalue_value;

А в объекте хэш-таблиц минимум две (методы и свойства).

 

[Breeze]

а дак я же был на докладе на phpConf, там правда про звалы было в основном

вот как раз звал в качестве базы поменялся же и интовые массивы стали гораздо лучше.
кстати тестировал тут свои творения на phpng, с 5.4 разницы по скорости почти нет, но по памяти выигрыш ~30%