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>wrote:
>
>>
>> On Jan 18, 2012, at 12:26 , Ralph Shnelvar wrote:
>>
>> > I agree with you.    ...
> 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
>   >
> 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

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