Java数据结构和算法中哈希表知识点详解

什么是哈希表

哈希表是一种以键值对（key-value）形式存储数据的数据结构，通过使用哈希函数将对应的键映射为一个索引，使得数据的添加、删除、查找等操作可以在常数时间内完成。

具体来讲，哈希表主要包含以下几个部分：

• 哈希函数：将键转换为一个索引，通常使用散列算法实现。
• 数组：用于存储哈希表的元素（键值对）。
• 冲突解决机制：当不同的键映射至同一个索引时，需要使用一种方法来解决冲突，常见的方法有链表法和开放地址法。

哈希函数的设计

哈希函数的设计对哈希表的性能至关重要，一个好的哈希函数应该满足以下几个条件：

• 易于计算：哈希函数的计算速度应该尽量快，这可以提高哈希表的插入、查找等操作性能。
• 均匀分布：哈希函数应该尽量将不同的键映射到不同的索引上，避免过多的冲突。
• 抗碰撞：哈希函数应该尽量减少碰撞的发生。

常见的哈希函数包括简单取模法、乘法哈希法、一致性哈希等。

冲突解决机制

当哈希函数将不同的键映射至同一个索引时，就会发生冲突。为了解决这个问题，通常采用一些冲突解决机制来解决。

链表法

链表法是最常见的一种冲突解决机制，它的核心思想是：当发生冲突时，将键值对存储到一个链表中。这样，在查找时，需要先找到相应的索引，然后在对应的链表中进行查找。

链表法的优点是简单易实现，缺点是如果哈希表中大量的键映射至同一个索引，那么链表的长度会变得非常长，影响性能。

开放地址法

开放地址法的核心思想是：当发生冲突时，通过一些算法将键值对存储在离冲突点最近的空白位置上。通常的做法是，如果当前的索引已经被占用，就尝试往后寻找下一个空白索引，直到找到为止。

开放地址法的优点是可以减少链表长度，缺点是容易产生聚簇现象，即大量的键值对会聚集在某些索引上，从而影响性能。

哈希表的时间复杂度

哈希表的各种操作的时间复杂度如下：

• 添加：O(1)
• 查找：O(1)
• 删除：O(1)

需要注意的是，哈希表的性能通常取决于哈希函数的好坏和冲突解决机制的选择。

示例一：使用哈希表存储学生成绩

下面是一个示例，使用哈希表存储学生成绩：

import java.util.HashMap;
import java.util.Map;

public class StudentScore {
    public static void main(String[] args) {
        Map<String, Integer> scores = new HashMap<>();
        scores.put("张三", 90);
        scores.put("李四", 80);
        scores.put("王五", 70);
        scores.put("赵六", 60);
        System.out.println("张三的成绩：" + scores.get("张三"));
    }
}

上面的代码中，我们使用了Java提供的HashMap实现哈希表，并将学生的姓名和成绩作为键值对存储到哈希表中。最后，我们通过get方法来获取张三的成绩。

示例二：使用哈希表实现LRU缓存

下面是另一个示例，使用哈希表实现LRU缓存：

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(2);
        cache.put("a", 1);
        cache.put("b", 2);
        System.out.println(cache);
        cache.put("c", 3);
        System.out.println(cache);
        cache.get("b");
        System.out.println(cache);
        cache.put("d", 4);
        System.out.println(cache);
    }
}

上面的代码中，我们实现了一个LRU缓存，即如果缓存达到了指定的最大容量，那么在添加新元素时，就会删除最近最少使用的元素。我们使用了Java中的LinkedHashMap实现，重载了removeEldestEntry方法和构造方法，就能实现LRU算法。最后，我们通过put方法往缓存中添加元素，并通过get方法获取元素。