save dictionary to a file without brackets.

[Dave Angel]

On 08/09/2012 06:53 PM, 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.
>
> (And yes, I know an option was added to older versions to randomize
> the hashes there too. It's not active by default, so "vanilla CPython"
> is still vulnerable.)
>
> ChrisA

Thank you to you and others, who have corrected my over-general
response.  I was not intending to claim anything about either a
deliberate DOS, nor a foolishly chosen hash function.  But the message I
was replying to seemed to me to claim that for large datasets, even a
good hash algorithm would end up giving O(n) performance.



-- 

DaveA