Java数据结构之实现哈希表的分离链接法

Java数据结构之实现哈希表的分离链接法

哈希表是一种非常常用的数据结构，它将数据存储在一个数组中，每个数组元素都存储着链表中的一个节点，这样可以实现高效的数据存储和查找操作。在哈希表中，我们可以通过哈希函数将关键字映射到数组中的特定位置。

但是，当哈希表的负载因子过高时，就会造成哈希冲突，这意味着两个或更多的关键字映射到了同一个数组位置。一种常见的解决方案是使用哈希表的分离链接法，这意味着在哈希表的每个位置上都存储一个链表，这些链表包含了该位置上的所有关键字。

下面是按照分离链接法实现哈希表的步骤：

1. 首先，需要定义一个哈希函数，将关键字映射到数组中的特定位置。哈希函数的选择通常取决于数据集的大小和分布，以及哈希表的大小。

2. 然后，我们需要创建一个存储链表的数组，需要确保它的大小足够大，以便可以容纳所有的关键字。

public class HashTableSeparateChaining {
    private static final int TABLE_SIZE = 10;
    private List<Integer>[] table;

    public HashTableSeparateChaining() {
        table = new List[TABLE_SIZE];
        for (int i = 0; i < TABLE_SIZE; i++) {
            table[i] = new LinkedList<Integer>();
        }
    }

    public int hashFunction(int key) {
        return key % TABLE_SIZE;
    }

这段代码创建了一个大小为10的哈希表，其中每个位置都是一个链表。

1. 接下来，我们需要实现哈希表的插入操作。这个插入操作需要先找到哈希表中将要插入的位置，然后检查该位置上是否已经存在相同的关键字。如果存在，则说明发生了哈希冲突，需要将新节点插入到该位置对应的链表中。

    public void insert(int key) {
        int hashValue = hashFunction(key);
        List<Integer> list = table[hashValue];
        if (list.contains(key)) {
            return;
        }
        list.add(key);
    }

这个插入操作首先计算了要插入的关键字的哈希值，然后获取哈希表中的链表并在其中查找。如果链表中已经存在相同的关键字，则直接返回，否则将新的节点插入到链表的末尾。

1. 最后，我们需要实现哈希表的查找操作。这个查找操作需要先找到关键字对应的哈希值，然后在哈希表中查找该值所在的链表，最后再遍历链表以寻找对应的节点。

    public boolean search(int key) {
        int hashValue = hashFunction(key);
        List<Integer> list = table[hashValue];
        return list.contains(key);
    }

这个查找操作先计算了关键字的哈希值，然后查找哈希表中对应的链表，并在其中查找目标节点。如果找到了，则返回true，否则返回false。

示例1：

HashTableSeparateChaining hashtable = new HashTableSeparateChaining();
hashtable.insert(10);
hashtable.insert(20);
hashtable.insert(30);
System.out.println(hashtable.search(20));  // 输出 true
System.out.println(hashtable.search(40));  // 输出 false

这个示例创建了一个大小为10的哈希表，并插入了三个关键字。然后它在哈希表中查找值为20和40的关键字。由于20是一个已经存在的关键字，所以第一个查找返回true，而40是一个不存在的关键字，所以第二个查找返回false。

示例2：

HashTableSeparateChaining hashtable = new HashTableSeparateChaining();
Random random = new Random();
for (int i = 0; i < 100; i++) {
    int value = random.nextInt(1000);
    hashtable.insert(value);
}
System.out.println(hashtable.search(500));  // 输出 true 或 false

这个示例创建了一个大小为10的哈希表，并插入了100个随机关键字。然后，它在哈希表中查找值为500的关键字。由于该关键字可能存在于哈希表中，也可能不存在于哈希表中，所以返回结果可能是true或false。