Abigail, I have two minor questions for you. First off you speak of finding the correct bucket as occurring in constant time. Given that the time to calculate the bucket value is dependent on the length of the key I dont quite see how this is correct. Or does this factor disappear because it averages to a constant time in normal use? I have a similar concern about the doubling of the buckets during insertion. My by now hazy recollection of big O() says that this behaviour is signifigant and should be included in the O() of hash insertion. Is this wrong? If its not wrong how would it be calculated? I havent the foggiest how you would calculate the effect of a factor that comes into play so rarely. Or is it again that it averages to 0 and so can be left out of the equation?
First they ignore you, then they laugh at you, then they fight you, then you win.