java中建立一个哈希表，分别用线性探测和链式探测解决冲突方法的代码

在Java中，我们可以使用`HashMap`和`HashTable`（已弃用，建议使用`HashMap`）来创建哈希表。这两个数据结构底层都采用了开放寻址法，其中线性探测（Linear Probing）和链式探测（Chaining）是两种常见的解决哈希冲突的方式。 1. **线性探测** (使用 `HashMap` 的实现，因为它默认采用数组+开放寻址) ```java import java.util.HashMap; public class LinearProbingHash { private static final int TABLE_SIZE = 100; private Object[] table; public LinearProbingHash() { table = new Object[TABLE_SIZE]; } // 哈希函数示例，这里仅做演示，实际应用中可能更复杂 private int hash(int key) { return key % TABLE_SIZE; } // 线性探测冲突处理 public void put(String key, String value) { int index = hash(key); while (table[index] != null && !table[index].equals(key)) { index = (index + 1) % TABLE_SIZE; // 探测下一个位置 } table[index] = new Node<>(key, value); // 存储元素 } // 假设Node类是一个简单的键值对封装 static class Node<K, V> { K key; V value; Node(K key, V value) { this.key = key; this.value = value; } } } ``` 2. **链式探测** (在`HashTable` 或者自定义哈希表实现，如`ConcurrentHashMap`中的红黑树链表) ```java import java.util.HashMap; import java.util.LinkedList; public class ChainedHash { private static final int TABLE_SIZE = 100; private LinkedList<Entry>[] buckets; // 数组中每个元素都是一个链表 public ChainedHash() { buckets = new LinkedList[TABLE_SIZE]; for (int i = 0; i < TABLE_SIZE; i++) { buckets[i] = new LinkedList<>(); } } private int hash(int key) { return key % TABLE_SIZE; } public void put(String key, String value) { int index = hash(key); Entry entry = new Entry(key, value); buckets[index].add(entry); // 如果链表长度大于某个阈值，考虑转换到其他冲突解决策略（比如链地址法） if (buckets[index].size() > threshold) { resize(); index = hash(key); // 重新计算索引 buckets[index].add(entry); } } private void resize() { /* 扩展哈希表大小 */ } private class Entry { String key; String value; // ... 实现get等方法 } } ```