On Wed, Jan 18, 2012 at 10:50 PM, Peter Vandenabeele
<peter / vandenabeele.com> wrote:
> On Wed, Jan 18, 2012 at 10:24 PM, Ryan Davis <ryand-ruby / zenspider.com>wr=
ote:
>
>>
>> On Jan 18, 2012, at 12:26 , Ralph Shnelvar wrote:
>>
>> > I agree with you. =A0Obviously there is sorting going on.
...
> I stand corrected ... (should have looked instead of speculated).
>
> Do I understand correctly from `st_lookup` in `st.c` that:
>
> * if (table->entries_packed) there is a linear search in bins
> * else FIND_ENTRY uses a hashing mechanism to keep the cost of
> =A0look-up essentially linear.
>
> I had speculated that a b-tree with sorting was used to keep the
> look-up cost low (but I presume now that is not the case)!

Peter, a Hash uses _hashing_ to keep lookup cost low.  This has complexity =
O(1).

http://en.wikipedia.org/wiki/Hash_table#Performance_analysis

Cheers

robert

--=20
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/