Non-oblivious hashing, where the information gathered by performing "unsuccessful" probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables: a. An 0(1) worst case scheme that requires only logarithmic additional memory (improving on the [FKS84] linear space upper bound). b. An almost sure 0(1) probabilistic worst case scheme, without any additional memory (improving on previous logarithmic time upper bounds). c. Enhancements to hashing: Solving (a) and (b) in the multikey record environment, search can be performed under any key in time 0(1); finding the nearest neighbor, the rank, etc. in logarithmic time. Our non-oblivious upper bounds are much better than the appropriate oblivious lower bounds.