Java Hash

1. 引言

在計算機科學中，哈希函數（Hash Function）是一種將數據映射到指定位數的索引（hash code）的函數。即將任意長度的消息，壓縮到某一固定長度的消息摘要（message digest）的函數。

在Java語言中，哈希可以應用於很多方面，比如實現集合類、在密碼學中可以應用哈希函數保證消息的完整性，在網路中可以進行數據包的校驗等等。本篇文章主要介紹Java中哈希相關的基礎知識、哈希演算法的實現以及如何在Java中使用哈希函數。

2. Java中哈希的基礎知識

1. hashCode方法

在Java中每個對象都有一個默認的hashCode()方法，它返回的是該對象的哈希碼值。默認情況下，hashCode()方法返回的哈希碼值實際上是該對象的內存地址經過某種演算法得到的。因此每個對象的哈希碼值都是唯一的。

public class Person {
    private String name;
    private int age;
    // 省略 getter/setter 方法
    @Override
    public int hashCode() {
        int result = 17;
        result = result * 31 + name.hashCode();
        result = result * 31 + age;
        return result;
    }
}

2. equals方法

在Java中，equals()方法用於判斷兩個對象是否相等。如果我們想要自定義一個類的判斷相等的邏輯，需要重寫equals()方法和hashCode()方法。在重寫equals()方法的過程中是經常會用到hashCode()方法來計算這兩個對象的哈希碼值是否相等。

public class Person {
    private String name;
    private int age;
    // 省略 getter/setter 方法
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null || getClass() != obj.getClass()) {
            return false;
        }
        Person person = (Person) obj;
        if (age != person.age) {
            return false;
        }
        return name.equals(person.name);
    }
}

3. 哈希演算法的實現

1. MD5

MD5全名Message-Digest Algorithm 5（信息-摘要演算法 5），可以將不限長度的字元串處理為固定長度的哈希值（通常為128位二進位）。MD5演算法主要是通過對原始數據（消息）進行多次分組處理，每次處理後生成散列值，再將散列值相連得到最終哈希值。

2. SHA

SHA全名Secure Hash Algorithm（安全散列演算法），和MD5一樣，也是將不定長度消息用哈希函數計算成定長的摘要信息的演算法。但SHA輸出摘要信息長度可以達到160、256、384、512位。

3. MurmurHash

MurmurHash是在2008年由Austin Appleby創建出來的一種高性能、低碰撞率的哈希演算法。它的速度比市面上絕大部分哈希演算法都快得多，且具有較低的碰撞率。

public static int murMurHash(String key) {
    int length = key.length();
    int h = 0;
    int seed = 31;
    // 設置不同的種子可以避免哈希碰撞
    for (int i = 0; i < length; i++) {
        h = h * seed + key.charAt(i);
    }
    return h;
}

4. 在Java中使用哈希函數

在Java中，哈希函數的應用非常廣泛，比如HashTable、HashSet、HashMap等容器都以哈希表形式實現。

1. HashMap的實現原理

HashMap是Java中最常用的哈希容器之一，它是基於哈希表實現的。當我們向HashMap中插入一組鍵值對時，首先會對鍵進行哈希計算，然後將其作為下標，將值存入哈希表中。如果其中一個下標已經存在一個值，那麼就會產生哈希碰撞。

2. ConcurrentHashMap的實現原理

ConcurrentHashMap是Java中的線程安全哈希容器，它採用了分段鎖機制來保證線程安全。在ConcurrentHashMap的內部實現中，使用了分段數組來存儲鍵值對，每一段都維護了一個哈希表。在操作ConcurrentHashMap時，首先會通過哈希函數計算出該操作所需要使用的哈希表。然後，對該哈希表進行加鎖，確保線程安全。

3. BitSet的使用

BitSet是Java中的位集合容器類，它可以存儲一個由布爾值（位）組成的固定長度的序列。在某些情況下，BitSet可以用來替代HashSet，可以大幅度的降低內存的使用。

public static void bitSetDemo() {
    BitSet bitSet = new BitSet(1000);
    bitSet.set(10, 200);
    int cardinality = bitSet.cardinality();
    System.out.println("cardinality: " + cardinality);
    System.out.println(bitSet.get(20));
}

5. 總結

本篇文章主要介紹了Java中哈希相關的基礎知識、哈希演算法的實現以及如何在Java中使用哈希函數。

在Java中，哈希容器可以實現快速的數據查找，哈希演算法可以實現密碼學、校驗數據完整性等。需要注意的是，在使用哈希容器時需要重寫對象的hashCode和equals方法，以保證數據的正確性。

同時，多數哈希演算法都無法避免哈希碰撞問題的出現，因此應盡量選擇具有低碰撞率、高性能的哈希演算法，比如上文提到的MurmurHash。