Why is an internal table of PATH directories maintained?

Question

I was looking for what rehash command does and found this:

The rehash command re-computes the internal hash table of the contents of directories listed in the path environmental variable to account for new commands added.

I never knew about any internal hash tables. Why and how are they maintained?

Answer 1

When you enter a command, if there were no hash table, the shell would check every directory listed in the $PATH variable to see if your command is found there.

This can be a slow process if any of those directories is attached to a slow device. You would get a pause every time you enter a command.

So, when the shell starts running, it reads every directory in the $PATH and determines what all the executable programs are, then stores this list into a hash table in memory. Then, it never needs to check them again, and it can quickly know if a command you typed is valid or not.

This works great as long as you never add or remove programs, because as soon as you do, the hash table is going to be out of date. The purpose of the rehash command is to ask the shell to go and read the list of programs again.

The above applies to csh and tcsh.

With the bash shell, it does not read in the names of all your programs at startup. It does keep a hash table, but it only puts things in it as you type commands. For example:

bash-3.2$ ls
foo bar baz
bash-3.2$ cp
cp: missing file operand
Try `cp --help' for more information.
bash-3.2$ hash
hits    command
   1    /bin/cp
   1    /bin/ls

It has remembered the locations of the cp and ls commands.

Answer 2

It's generally simple, though there are variations between shells. In order to avoid unnecessary IO, the shell maintains a table mapping executable names to their complete paths.

zsh has two options related to this, both enabled by default:

HASH_CMDS <D>

Note the location of each command the first time it is executed. Subsequent invocations of the same command will use the saved location, avoiding a path search. If this option is unset, no path hashing is done at all. However, when CORRECT is set, commands whose names do not appear in the functions or aliases hash tables are hashed in order to avoid reporting them as spelling errors.

HASH_DIRS <D>

Whenever a command name is hashed, hash the directory containing it, as well as all directories that occur earlier in the path. Has no effect if neither HASH_CMDS nor CORRECT is set.

With these options, appending directories (and new commands) to the PATH should work as intended. However, if you prepend a directory to the path that is supposed to take precedence over a certain command (e.g. /usr/local/bin/ls), you may have to rehash or restart the shell.