[interfacekit] Re: BHandler::fToken

<lurk mode off>

I think I must be missing something. I don't see why you need a token
queue at all.

From what I can recall from old CS lectures, the hash table is just a way of 
providing a way of sorting unpredictable
input data into relatively even piles. If we have as many, or more, buckets
than inputs, then generally we get no collision, (providing we have a good
hash function), and we have either one or zero entities per bucket. 

If we have a 32 bit id as the hash key, and we insert more than 4 billion
entries, we will get collision, but so what. In the case of 40 billion
entries it takes 10 lookups to find an entity. That sounds pretty good to
me.

Cheers,
John

On Tue, Mar 11, 2003 at 04:15:52PM -0800, Erik Jaesler wrote:
> 
> Axel Dörfler wrote:
> > Erik Jaesler <erik@xxxxxxxxxxxxxx> wrote:
> > OTOH looking up a token should be very fast, since we have to do that 
> > all the time, even more often than creating/deleting them.
> 
> It's not looking up *one* token that concerns me; even with just a 
> regular map that's plenty fast.  The case that the token queue is 
> supposed to deal with is when you've maxed out the token counter.  Once 
> that's happened, without the queue, you have to start at zero and check, 
> iteratively, whether a given token is currently being used.  With the 
> token queue, we have a cache of tokens we *know* aren't being used, so 
> we don't have to hunt through the token space trying to find a free one. 
>   With the queue, the only time that would happen is when an app has 
> maxed the token counter *and* used up everything in the queue.  Maybe 
> this is an unnecessary concern; perhaps walking the map looking for a 
> free token will be fast enough even under the worst case.
> 
> e
> 
>

Other related posts: