save dictionary to a file without brackets.

[Steven D'Aprano]

On Fri, 10 Aug 2012 08:53:43 +1000, Chris Angelico wrote:

> On Fri, Aug 10, 2012 at 8:26 AM, Dave Angel <d at davea.name> wrote:
>> On 08/09/2012 06:03 PM, Andrew Cooper wrote:
>>> O(n) for all other entries in the dict which suffer a hash collision
>>> with the searched entry.
>>>
>>> True, a sensible choice of hash function will reduce n to 1 in common
>>> cases, but it becomes an important consideration for larger datasets.
>>
>> I'm glad you're wrong for CPython's dictionaries.  The only time the
>> lookup would degenerate to O[n] would be if the hash table had only one
>> slot.  CPython sensibly increases the hash table size when it becomes
>> too small for efficiency.
>>
>> Where have you seen dictionaries so poorly implemented?
> 
> In vanilla CPython up to version (I think) 3.3, where it's possible to
> DoS the hash generator. Hash collisions are always possible, just
> ridiculously unlikely unless deliberately exploited.

Not so unlikely actually.

py> hash(3)
3
py> hash(2**64 + 2)
3

py> hash(-1)
-2
py> hash(-2)
-2


By its very nature, a hash function cannot fail to have collisions. The 
problem is that in general you have an essentially unlimited number of 
objects being mapped to a large but still finite number of hash values.



-- 
Steven