[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: lookup table with integer keys
- From: Coda Highland <chighland@...>
- Date: Sun, 9 Mar 2014 11:34:18 -0700
On Sun, Mar 9, 2014 at 11:00 AM, Luiz Henrique de Figueiredo
>> > is the usage of a lookup table with keys from 0 to n less efficient compared
>> > to 1 to n+1?
>> Only the index 0 itself, which always is in the "hash" part.
> Don't assume that all entries in a sequence are stored in the array part.
> It may well happen that part of the sequence is in the hash part.
> OTOH, you shouldn't need to care about these implementation details,
> unless we're talking about n being *very* large, in which case you
> probably have other concerns.
On the flip side, odds are that a sequence with keys 1..n and a
sequence with keys 0..n are only going to differ by the index 0. If
they're constructed the same way, there's high (though not 100%)
probability that the two sequences are going to be stored the same
way. That is to say, if the 1..n sequence has some stuff in the hash
part and some stuff in the array part, the 0..n sequence will have a
very similar breakdown, and if the 1..n sequence doesn't use the hash
part, it's likely that the 0..n sequence will only use the hash part
for element 0.
Of course, that's saying the same thing Luiz was, in more words -- you
shouldn't need to care about the implementation details when
distinguishing between the two cases.