The process used to reduce the storage space required by a file
Compression is particularly important for sharing files over networks or the Internet
Downloading a compressed file over the Internet is faster than downloading the full version of the file
Lossy compression
Reduces the size of a file while also removing some of its information
Lossless compression
Reduces the size of a file without losing any information
When using lossless compression, the original file can be recovered from the compressed version
Run length encoding
A method of lossless compression in which repeated values are removed and replaced with one occurrence of the data followed by the number of times it should be repeated
Dictionary encoding
A method of lossless compression where frequently occurring pieces of data are replaced with an index and compressed data is stored alongside a dictionary which matches the frequently occurring data to an index
Data compressed using dictionary compression must be transferred alongside its dictionary
Encryption
Used to keep data secure when it's being transmitted
Symmetric encryption
Both the sender and receiver share the same private key, which they distribute to each other in a process called a key exchange
Asymmetric encryption
Two keys are used: one public and a second, private, key. The public key can be published anywhere, free for the world to see, while the private key must be kept secret
Hashing
The name given to a process in which an input (called a key) is turned into a fixed size value (called a hash)
The output of a hash function can't be reversed to form the key
Hash table
A data structure which holds key-value pairs, formed from a bucket array and a hash function
Hash tables can be used to lookup data in an array in constant time
Collision
When two pieces of data (keys) produce the same hash
Good hash function
Has a low chance of collision
Is quick to calculate
Provides an output which is smaller than the input