[[XHashTable]] > We should fix the issue with vacant/deleted marker Oh, then you haven't yet looked at my work from yesterday? There is no problem anymore, but it could be improved.
I've implemented (A) (a counter that tells me when every position had been checked). And there is an obvious threshold to trigger rehashing, namely, in case there is no vacant position anymore, any search for a key that is not in the table takes a probing length that hits every bucket. Since the table is never full (load factor is 0.7), it is safe to trigger rehashing in that case. And this I have implemented. (I'll probably should add some tests.) I'm currently thinking about another threshold value. Given that the probing length should usually be short, it would also be OK if I hit a probing length that is bigger than the number of entries in the table. (All this is easily tested by a simple comparison of two Integers which will fit into SingleInteger for tables that are not too huge). Even if there are no DELETED entries in the probing sequence (i.e. all keys have a initial collision, the insertion of keys during rehashing will most probably be done in a different order than initial insertion so that it's unlikely that the rehashed table has again a probing sequence of maximal size. Of course, the latter could still happen and would basically mean to rehash every time that a key is not found. So, maybe I should think about a randomized insertion during rehashing. With randomization (and the fact that double hashing uses two independent hash functions), one could even start rehashing for a smaller value than the number of entries. I just have no idea how small I can make the threshold that I don't end up with endless rehashing. What do you think? Of course, (without randomized rehashing) one could also think about a threshold that is between the number of actual entries and the number of buckets in the array, but since from a hash table we want nearly constant time access, making the rehashing threshold bigger than the number of actual entries doesn't seem reasonable to me. > and performance problem due to lazy resolution of import in anonymous > function. Ooops. Sorry. I actually wanted to implement that last nigth, but forgot. I'll try tonight. > To check performance you can use the short input file I > posted. Ok, I'll try. Still, I think the weekend already taken with other business. Ralf -- You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/fricas-devel?hl=en.
