From: "Oskar Sandberg" <[email protected]> > On Sat, 05 Aug 2000, Henry Hemming wrote: > <> > > Sorry if I'm a bit behind here, but whats wrong with using a hash table that > > uses the routing key as the hash, and then just check previous and next hash > > entry for closeness? > > What you want is in an ordered list. Using a hashtable to do that is at best a > hack, and probably won't work (even if you control the hashfnction, hashtables > move stuff around on collisions and such). In my oppinion you dont need secondary hashing in case of collision, as when you have a collision you already have a close enough distrinction, no point in having ..001 and ..002 in the hash table refering to the same direction. By by controling the size of the hash table you will also be able to control the accuracy of your routing. Besides if originally empty hash table produces problems you can rehash the hash table until you reach the level of accuracy that you want ( I belive the java.util.hash* used this method ), and use chaining instead of secondary hashing. > > What you are missing is that I am refering to the general problem of keys which > don't have an order at all, or at least not one that corresponds to the > closeness relation. > > To put it in programmer terms, we would want something that works for a Key > about which we know nothing of the value, but whose only public method is: > > boolean isCloser(Key A, Key B) By using key comparison you can never archieve anything better than O(log n) theoretically for retrieval. > > which returns true if it closer to A, and false if it closer to B. > > > I'm a lazy bastard and dont check the implementation but as java uses int's > > in hashtables and routing keys are alot longer shouldnt the highest bits of > > the routing key be used in the hash table so that close entries that point > > to the same direction dont take excess space? Then again local entries are > > typically close to each other and should therefore use the lowest bits as > > the hash.. :-P > > In order to produce maximum entropy, the each 4 byte part of the key is xored > to the hashcode. This could be changed, but there are much better methods to > produce ordered lists (binary trees) anyways. Well, I was after the hashtable O(1) search, instead of binary trees O(log n). Maximum entropy is not archieved by xoring all parts if the parts dont originally have equal entropy value. And in my oppinion they dont have in this case, as I already explained. > > > > > --typo > > > > > > _______________________________________________ > > Freenet-dev mailing list > > Freenet-dev at lists.sourceforge.net > > http://lists.sourceforge.net/mailman/listinfo/freenet-dev > -- > \oskar > > _______________________________________________ > Freenet-dev mailing list > Freenet-dev at lists.sourceforge.net > http://lists.sourceforge.net/mailman/listinfo/freenet-dev >
--typo _______________________________________________ Freenet-dev mailing list Freenet-dev at lists.sourceforge.net http://lists.sourceforge.net/mailman/listinfo/freenet-dev
