What is the difference between locate/whereis/which

What is the basic difference between locate whereis and which command.

The basic difference that I observed is that locate locates all the related file names in the entire filesystem, whereas whereis and which commands only give the location (system/local address of file) of installed application. How accurate is my observation?

How are these commands implemented internally. Why does locate work so fast as compared to the dash search, while locate has to search a particular filename matching the target string in the entire filesystem hierarchy?

which finds the binary executable of the program (if it is in your PATH). man which explains more clearly:

which returns the pathnames of the files (or links) which would be executed in the current environment, had its arguments been given as commands in a strictly POSIX-conformant shell. It does this by searching the PATH for executable files matching the names of the arguments. It does not follow symbolic links.

whereis finds the binary, the source, and the man page files for a program. For example

$ whereis gimp
/usr/bin/gimp /usr/lib/gimp /etc/gimp /usr/share/gimp /usr/share/man/man1/gimp.1.gz

You can get extra detail by passing the output of these commands as arguments to ls -l or file

$ ls -l $(which gimp)
lrwxrwxrwx 1 root root 8 Jun 30 19:59 /usr/bin/gimp -> gimp-2.8

$ file $(which gimp)
/usr/bin/gimp: symbolic link to gimp-2.8

locate indeed finds all the files that have the pattern specified anywhere in their paths. You can tell it to only find files and directories whose names (rather than full paths) include the pattern with the -b option, which is usually what you want, and gives a less unwieldy list.

locate is fast because it uses a binary database that gets periodically updated (once daily, by cron). You can update it yourself to ensure recently added files are found by running sudo updatedb

One more thing about locate - it doesn't care whether files still exist or not, so to avoid finding recently deleted files, use -e. Often I also pipe to less as the list can be long. Typically I do:

sudo updatedb && locate -b -e gimp | less

How Unity's dash works is explained here - it uses Zeitgeist to index system files and learn from usage patterns, and enables other applications to make use of this data, so it is doing a lot more work than locate.