WikiGalaxy
Hash Functions: Introduction
A hash function is a special type of function used in computer science to map data of arbitrary size to fixed-size values, typically for fast data retrieval. It is a crucial component in data structures like hash tables, ensuring efficient data access and storage.
Example 1: Simple Hash Function
Simple Hash Function
A simple hash function takes an integer input and returns the remainder when divided by a fixed number.
int simpleHash(int key, int tableSize) {
return key % tableSize;
}
Console Output:
For key = 10, tableSize = 3, Output = 1
Example 2: Multiplicative Hash Function
Multiplicative Hash Function
This hash function uses multiplication and division to distribute keys uniformly across the hash table.
int multiplicativeHash(int key, int tableSize) {
double A = (Math.sqrt(5) - 1) / 2;
return (int)(tableSize * ((key * A) % 1));
}
Console Output:
For key = 10, tableSize = 3, Output = 2
Example 3: Cryptographic Hash Function
Cryptographic Hash Function
Designed to be secure, cryptographic hash functions are used in various security applications and protocols, like SSL/TLS.
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
String cryptographicHash(String input) throws NoSuchAlgorithmException {
MessageDigest md = MessageDigest.getInstance("SHA-256");
byte[] hash = md.digest(input.getBytes(StandardCharsets.UTF_8));
return bytesToHex(hash);
}
private String bytesToHex(byte[] hash) {
StringBuilder hexString = new StringBuilder();
for (byte b : hash) {
String hex = Integer.toHexString(0xff & b);
if (hex.length() == 1) hexString.append('0');
hexString.append(hex);
}
return hexString.toString();
}
Console Output:
For input = "hello", Output = "2cf24dba5fb0a30e26e83b2ac5b9e29e1b161e5c1fa7425e73043362938b9824"
Example 4: Division Method
Division Method
The division method involves dividing the key by the table size and using the remainder as the hash value.
int divisionHash(int key, int tableSize) {
return key % tableSize;
}
Console Output:
For key = 15, tableSize = 7, Output = 1
Example 5: Universal Hash Function
Universal Hash Function
Universal hashing involves creating a hash function that minimizes the probability of collision, often using randomization techniques.
int universalHash(int key, int a, int b, int p, int tableSize) {
return ((a * key + b) % p) % tableSize;
}
Console Output:
For key = 20, a = 3, b = 5, p = 31, tableSize = 10, Output = 7
