Java深入了解数据结构之哈希表篇

1. 哈希表的定义

哈希表（Hash Table），也叫散列表，是根据关键码值(Key Value)而直接进行访问的数据结构。通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数(Hash Function)。

哈希表是基于哈希函数实现的，哈希函数将关键字映射到哈希表中的位置，如果存在两个关键字映射到同一个位置，则发生碰撞。

2. 哈希表的工作原理

哈希表的工作原理可以分为以下几个步骤：

1. 建立哈希表。
2. 根据哈希函数把关键字映射到表的位置。
3. 如果该位置已经有其他关键字占用，则发生碰撞。
4. 碰撞解决（拉链法，开放地址法等）。
5. 查找记录：根据关键字计算哈希值，找到对应的数据。

3. 哈希表的特点

哈希表的特点：

1. 查找/插入/删除的时间复杂度都是O(1)的。
2. 哈希表大小一般为素数，可以有效避免哈希冲突。
3. 哈希表的哈希函数应该尽量少的发生哈希冲突。

4. 哈希表的实现

哈希表的实现有多种方法，比如：

1. 拉链法
2. 线性探测法
3. 双散列法

4.1 拉链法

拉链法是哈希表实现最为常用也最为简单的方法。拉链法把每个哈希值相同的元素都放到一个链表中，查询时遍历该链表，查找对应元素。

public class HashTable<T> {

    private int size;
    private LinkedList<T>[] table;

    public HashTable() {
        size = 17;
        table = new LinkedList[size];
    }

    public void put(T element) {
        int hash = element.hashCode() % size;
        if (table[hash] == null) {
            table[hash] = new LinkedList<>();
        }
        table[hash].add(element);
    }

    public T get(T element) {
        int hash = element.hashCode() % size;
        LinkedList<T> list = table[hash];
        if (list != null) {
            for (T e : list) {
                if (e.equals(element)) {
                    return e;
                }
            }
        }
        return null;
    }
}

4.2 线性探测法

线性探测法是一种开放地址法，也就是说，发生哈希冲突时，根据一定规则继续探测下一个位置，直到找到空位置或者查询结束为止。

public class LinearHashTable<T> {

    private int size;
    private Object[] table;

    public LinearHashTable() {
        size = 17;
        table = new Object[size];
    }

    public void put(T element) {
        int hash = element.hashCode() % size;
        while (table[hash] != null) {
            hash = (hash + 1) % size;
        }
        table[hash] = element;
    }

    public T get(T element) {
        int hash = element.hashCode() % size;
        while (table[hash] != null && !table[hash].equals(element)) {
            hash = (hash + 1) % size;
        }
        if (table[hash] != null) {
            return (T) table[hash];
        }
        return null;
    }
}

5. 示例说明

5.1 示例一

一种常见的使用哈希表的场景是在数据去重上。比如，去掉一个文件中的重复单词，可以使用哈希表来实现。

public static void main(String[] args) {
    try (Scanner scanner = new Scanner(new File("input.txt"), "UTF-8");
         PrintWriter writer = new PrintWriter("output.txt", "UTF-8")) {
        Set<String> set = new HashSet<>();
        while (scanner.hasNext()) {
            String word = scanner.next();
            if (!set.contains(word)) {
                set.add(word);
                writer.print(word + " ");
            }
        }
    } catch (IOException e) {
        e.printStackTrace();
    }
}

5.2 示例二

哈希表还广泛应用于快速查找。比如，在一堆卡片中查找编号为123456的卡片，可以使用哈希表来实现。

public static void main(String[] args) {
    Map<String, Card> map = new HashMap<>();
    List<Card> cards = new ArrayList<>();
    cards.add(new Card("123456", "xxx"));
    cards.add(new Card("654321", "yyy"));
    cards.add(new Card("111111", "zzz"));
    for (Card card : cards) {
        map.put(card.getId(), card);
    }
    Card target = map.get("123456");
    System.out.println(target.getName());
}
class Card {
    private String id;
    private String name;
    public Card(String id, String name) {
        this.id = id;
        this.name = name;
    }
    public String getId() {
        return id;
    }
    public String getName() {
        return name;
    }
}