On Sat, Nov 28, 2015 at 12:02 PM, Pascal KISSIAN <php-mailing-l...@lool.fr> wrote:
> Sorry Nikita, > > > > I didn’t fully read your 1st message because it was speaking on changing > hash algo…, and I’ve been a bit lazy on that… > > > > However, I only have thought about a minor change introducing a salt. > > In the zend_inline_hash_func , hash is initialized with Z_UL(5381) … what > about just adding a salt value to this number, this would not make any > performance issue. > Collisions in DJBX33A are (integer overflow notwithstanding) completely independent of the starting value, so randomizing it wouldn't help. If you're interested in how DJB collisions are constructed, see http://www.phpinternalsbook.com/hashtables/hash_algorithm.html#hash-collisions . > For hashing integers, why just not adding a salt value also… and no > performance issue…. > Similarly, this would not have any effect either. We reduce hashes using an equivalent of hash % table_size, which is the same as (hash + N * table_size) % table_size for any N. If you simply add an additional number to it, the same relation still holds: (hash + salt) % table_size == (hash + salt + N * table_size) % table_size, so elements that collided previously still collide. > For storing the salt, if you choose to have one different random value > for each hash table, it would not be a problem for arrays living in > opcache SHM… > Randomizing the string hashing function would however prevent caching the hash in the zend_string structure. Nikita
