You are partially right. There is no free lunch in the universe. The cost of computing a perfect hash is, I vaguely recall, on the order of O(n lg n). The point is, no matter how big the results get, calculating the array offset into the table is still O(1). In other words, it's just as cheap to add 2 to 4 as it is to add it to 4000000000000. Since this table will probably be accessed an order of magnitude more often than it will be written, it makes sense to pay for the load on the update side, rather than the access side.

Nope, yourself. Hashing can only have a slowdown when there are collisions. The way you deal with those collisions determines the efficiency of your algorithm. Importantly, there exists an algorithm that guarantees no collisions and is therefore O(1). Checkout Perfect Hashing on Wikipedia for details.

Nope. O(1) is O(1). The constant doesn't change with the size of the input. Otherwise, it would be O(whatever relates the "constant" to the input size). A perfect hash, or a chained hash are, in fact, O(1) for lookups. If something is linear time, then it's O(n). But we have efficient algorithms, such as binary search, that are O(lg n).

Here is a neat one:

First, compute the set of tags for your project. You can use ctags *.c *.h, for example, but other programs may also be able to produce a tags file. The format of the tags file is fairly simple. Each line is the tag, followed by a tab, then the relative path to the file containing that tag, followed by a tab, then a regular expression matching the line on which that tag is found. If the tag occurs more than once, just insert new copies of the line with different regexes.

Now for the neat, Vimmy part. When typing in insert mode, press Crtl-N and you will get a completion window that lists all of your tags. Pretty neat, huh?