Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.mixmin.net!feeds.phibee-telecom.net!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!post.news.xs4all.nl!not-for-mail
Return-Path: <ian.g.kelly@gmail.com>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.013
X-Spam-Evidence: '*H*': 0.97; '*S*': 0.00; 'value,': 0.04; 'insert': 0.05; 'binary': 0.07; 'table.': 0.07; 'dan': 0.09; 'inserts': 0.09; 'linear': 0.09; 'bucket': 0.16; 'exponential': 0.16; 'fetch': 0.16; 'size;': 0.16; 'tends': 0.16; 'vanishingly': 0.16; 'worst': 0.16; 'wrote:': 0.18; 'trying': 0.19; 'dependent': 0.19; 'things.': 0.19; '>>>': 0.22; 'case.': 0.24; 'header:In-Reply- To:1': 0.27; 'function': 0.29; 'fixed': 0.29; 'resolution': 0.29; 'array': 0.29; 'needed.': 0.30; 'message-id:@mail.gmail.com': 0.30; 'getting': 0.31; '>>>>': 0.31; 'schemes': 0.31; 'becomes': 0.33; 'entirely': 0.33; 'used,': 0.33; 'table': 0.34; 'case,': 0.35; 'but': 0.35; 'received:google.com': 0.35; 'there': 0.35; 'scheme': 0.36; 'possible': 0.36; 'list': 0.37; 'list.': 0.37; 'arrange': 0.38; 'e.g.': 0.38; 'to:addr:python-list': 0.38; 'pm,': 0.38; 'itself': 0.39; 'to:addr:python.org': 0.39; 'enough': 0.39; 'even': 0.60; 'access,': 0.60; 'full': 0.61; 'such': 0.63; 'more': 0.64; 'linked': 0.65; 'mar': 0.68; 'grow': 0.77; 'balanced': 0.84; 'collision': 0.84; 'probe': 0.91; 'average': 0.93
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :content-type; bh=uWsDkwwP1HrlMCxUA05aCQ00PJZJQA5tYgmaGtnmjDg=; b=uQTqQI1wAWrQh4dd9OyBuGTMVNgqNhr2RyA9nuYn2QOvhARhcivBrIrelwXYB3gJld g3JJblRj0+qJj6kgdLfI4Y0ft0BM40zMyi/3RL12Npzh2QH7icd402fUJQEVNJEnXcGn e8H+M7FkjYLOgifNNcvasM2GJItamqhOoJNWpEKKb9GlEpEuZmAmLQDprMY//FRsPYpc KWHMVf+Li3SVt7dudTOetvRDfLx8EyaOjz89s8WGOR6v4fpC5AdZW30SrJUxP/k2WbDU +Jd2gHJASleCZmoUzlFbDcVMbA1DSJWWXMSIGD2hLBE8/syGUexCkx/EMqtDaNCvRuaG hYsg==
X-Received: by 10.68.201.67 with SMTP id jy3mr36427362pbc.20.1394409926227; Sun, 09 Mar 2014 17:05:26 -0700 (PDT)
MIME-Version: 1.0
In-Reply-To: <CAGGBd_oSgZgtsg52JBDhSUxuxHpi9ZJSw4WfOwGwy7Zo6zhTTQ@mail.gmail.com>
References: <lennh4$kpm$1@cabale.usenet-fr.net> <CAPTjJmomgZSFj7TanBn8_qXP4ULhCm85abJ5=2PcikXJkrH6GQ@mail.gmail.com> <CAN1F8qU8AJ+Z-Rb4+wGsYWd_bS5aOA3bsjd5NjF46MUvnecSeQ@mail.gmail.com> <mailman.7473.1393598638.18130.python-list@python.org> <XnsA2E95FA1E1EB6duncanbooth@127.0.0.1> <bnvctpF5vanU1@mid.individual.net> <mailman.7920.1394252278.18130.python-list@python.org> <87eh2d3x8h.fsf_-_@elektro.pacujo.net> <CAGGBd_qU3Zp3A4pymnDQfWynWZwFVrdHJpG=U0WZTap4HiymdA@mail.gmail.com> <mailman.7937.1394311101.18130.python-list@python.org> <87eh2ctmht.fsf@elektro.pacujo.net> <mailman.7941.1394328694.18130.python-list@python.org> <87zjkz3eo3.fsf@elektro.pacujo.net> <mailman.7963.1394400019.18130.python-list@python.org> <87a9czrrax.fsf@elektro.pacujo.net> <mailman.7965.1394401067.18130.python-list@python.org> <8761nnrqsk.fsf@elektro.pacujo.net> <CAGGBd_oSgZgtsg52JBDhSUxuxHpi9ZJSw4WfOwGwy7Zo6zhTTQ@mail.gmail.com>
From: Ian Kelly <ian.g.kelly@gmail.com>
Date: Sun, 9 Mar 2014 18:04:46 -0600
Subject: Re: Balanced trees
To: Python <python-list@python.org>
Content-Type: text/plain; charset=ISO-8859-1
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.7975.1394409929.18130.python-list@python.org>
Lines: 33
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1394409929 news.xs4all.nl 2889 [2001:888:2000:d::a6]:60378
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:68110

On Sun, Mar 9, 2014 at 4:08 PM, Dan Stromberg <drsalists@gmail.com> wrote:
> On Sun, Mar 9, 2014 at 2:43 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>> Dan Stromberg <drsalists@gmail.com>:
>>
>>> On Sun, Mar 9, 2014 at 2:32 PM, Marko Rauhamaa <marko@pacujo.net> wrote:
>>>> There is no O(1) hash table.
>>>
>>> http://stackoverflow.com/questions/2771368/can-hash-tables-really-be-o1
>>
>> Please elaborate.
>
> A hash table of fixed size is O(1) until you fill it so full that you
> start getting enough collisions to make it O(n), as one bucket becomes
> a linked list.  This is because the hash function is O(1), and looking
> up a value in a C array is O(1).
>
> A more flexible hash table will not have a fixed size; instead it will
> grow itself as needed.  This growth operation tends to be O(n), but
> happens vanishingly infrequently as the table grows, so it's still
> amortized O(1).

A hash table can also only ever be O(1) in the average case.  Worst
case, everything you put into the hash table has the same hash value,
and so the time to fetch an item is entirely dependent on the
collision resolution scheme -- e.g. O(n) if a linked list or linear
probe is used, or perhaps O(log n) if each bucket is a balanced binary
tree.

There are schemes such as cuckoo hashing that allow true O(1) worst
case access, but they have other drawbacks -- inserts with cuckoo
hashing are amortized O(1), and it is even possible for an insert to
fail entirely after spending exponential time trying to find a way to
arrange things.