how hash_t toHash() works?

Ivan Kazmenko gassa at mail.ru
Sat May 4 16:17:47 PDT 2013


> One more question... why associative arrays in D can't be 
> implemented like here?
>
> http://svn.php.net/viewvc/php/php-src/trunk/Zend/zend_hash.h?view=markup
>
> it seems that php arrays uses hash tables too but they preserve 
> orders.

 From what I see there, this code traverses a hash table in the 
order in which the elements were inserted, not any other 
particular order (such as lexicographical).  Much like Java's 
LinkedHashSet: 
http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html

This however has a cost of maintaining a linked list which is at 
least one pointer per entry in size.  If that was the implemented 
behavior, the performance would suffer for users who don't need 
any particular order.

Slightly off topic:  by the way, polynomial hashing modulo a 
power of two (as in the link you gave) is fast but has a rather 
general corner case regardless of the multiplier.  And 
multiplying by small integers such as 33 gives another easy way 
to produce plenty of strings with identical hashes, this time 
regardless of the modulo.  So, hashing like "hash(i) = hash(i-1) 
* 33 + str[i]" is a piece of cake for an adversary who wants your 
running time to be quadratic instead of linear.

Ivan Kazmenko.


More information about the Digitalmars-d-learn mailing list