Thank you, indeed.
Actually, by now I understand it would be _impossible_ to generically
use b-tree for the keys of a hash, since some objects can be used as
a key that have no < or > operator and thus not sortable ...
1.9.3-p0 :001 > a = Object.new # => #<Object:0x9d88660>
1.9.3-p0 :002 > b = Object.new # => #<Object:0x9d814c8>
1.9.3-p0 :003 > a < b
NoMethodError: undefined method `<' for #<Object:0x9d88660>
1.9.3-p0 :004 > h= {a => '10', b => '100'}
=> {#<Object:0x9d88660>=>"10", #<Object:0x9d814c8>=>"100"}
1.9.3-p0 :005 > h[a]
=> "10"
Learned a lot, sorry for the fuss ...
Peter
···
On Thu, Jan 19, 2012 at 9:10 AM, Robert Klemme <shortcutter@googlemail.com>wrote:
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. Obviously 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
> look-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).