Used for identification/verification of the host you are connecting to

A public key is encoded into a sequence of bytes (hashed with SHA1/SHA2) - this can then be recreated when next connecting to the device to verify that the device is the same device you connected to before.

If the fingerprint has changed, it means the machine you are connecting to has had their public key changed.
This could be due to OS re-installs, re-installing ssh
WARNING: However this could also mean that the machine you are connecting to is different. If you are sshing to a domain then the server behind the domain may have changed, or you could be targeted by a main-in-the-middle attack where the attacker somehow intercepts/reroutes your ssh connection to a different machine. They could be doing this to snoop your username and password combination.

A servers public key is stored:

/etc/ssh/ssh_host_rsa_key.pub

When sshing to a device for the first time you will see something similar to:

The authenticity of host 'x.x.x.x (x.x.x.x)' can't be established.
RSA key fingerprint is 59:c7:8c:34:e7:97:c1:3f:e4:3a:13:e2:s6:39:7c:l9.
Are you sure you want to continue connecting (yes/no)? 

This 'fingerprint' is a more 'human friendly' output of a servers public key.


Now its worth noting, if you are very strict about security then it would be worth retrieving the following information BEFORE sshing to the device for the first time. To prevent accidental exposing your username and password to an unknown device.

If you wish to obtain the fingerprint before connecting to a device then you should ask the owner of the other server to run the following command and send you the output before you connect:

cd /etc/ssh
for file in *sa_key.pub
do   ssh-keygen -lf $file
done

Ouput should be similar:

1024 df:7e:cd:54:4a:76:78:3e:2a:23:32:de:30:6n:09:43 ssh_host_dsa_key.pub (DSA)
2048 59:c7:8c:34:e7:97:c1:3z:e4:3a:13:e2:g6:39:7c:k9 ssh_host_rsa_key.pub (RSA)

You can now compare the two when first sshing to the device.

Your server stores a FULL copy of the target devices public key in the file known_hosts, along with its IP.
The fingerprint hash is for the use of humans so that its easier to compare fingerprints rather than trying to compare full private keys quickly.
Know hosts output for an ip looks similar to:

x.x.x.x ssh-rsa AAAAB3NzaC1ycHJLJASLK@KSAABAQCwYykFF8PXobqCVGHOiLGxqDIa6m4ka7MHbLr
9IyL9SAZw9mnod2YZN311mGSGSoNww1XByZS7+PFzTbkd/Mudoa4LznZpmKL5eU3n61F/kNnKoJS3sEDkv
cZ+ybuEJrwUMN+8gg9Il+IvJ6yz4zv7Xb84o4PuGZSkXvC9L+LlNDDfehnjLbzfBgHJAkhjAsjlkj;lm'6
+F79g bjSCI6X4zvxNmaqyY9/PaqRWPpAAnnBLGmZpOolMHMo9jmom0797asHJAJKSVXlil/sr3Y5eQqEv3sV
tTppE4vlEuni0fHKHASJljsadljklasdJKHnuAxjAz

Below is an example output when a devices public key has changed. If you receive the following warning and you believe the target device has NOT been re-installed/edited etc, then I would highly recommend being very cautious.

The public key could have changed because:
- OS has been reinstalled
- SSH has been reinstalled
- Suspicious behavior: attacker using man-in-the-middle attack

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
@    WARNING: REMOTE HOST IDENTIFICATION HAS CHANGED!     @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
IT IS POSSIBLE THAT SOMEONE IS DOING SOMETHING NASTY!
Someone could be eavesdropping on you right now (man-in-the-middle attack)!
It is also possible that the RSA host key has just been changed.
The fingerprint for the RSA key sent by the remote host is
2b:sa:a0:af:97:f8:0c:04:81:5b:ef:4d:56:ad:09:34.
Please contact your system administrator.
The authenticity of host 'x.x.x.x (2001:4d48:ad51:2f00::2:2)' can't be established.
RSA key fingerprint is 6a:de:e0:af:56:f8:0c:04:11:5b:ef:4d:49:ad:09:23.
Are you sure you want to continue connecting (yes/no)? 

- Man-in-the-middle Attack
- Preimage Attack
- Collision Attack

http://www.phcomp.co.uk/Tutorials/Unix-And-Linux/ssh-check-server-fingerprint.html
https://en.wikipedia.org/wiki/Public_key_fingerprint
http://www.lysium.de/blog/index.php?/archives/186-How-to-get-ssh-server-fingerprint-information.html