java使用链地址法实现哈希表的构造与查找
时间: 2024-05-15 17:14:26 浏览: 4
链地址法是哈希表中解决哈希冲突的一种方法,它的基本思想是将哈希表中的每个桶都设置为一个链表的头结点,当发生哈希冲突时,将新元素插入到对应桶的链表中。
下面是使用链地址法实现哈希表的构造和查找的Java代码:
```java
// 定义哈希表节点类
class Node {
int key;
String value;
Node next;
public Node(int key, String value) {
this.key = key;
this.value = value;
this.next = null;
}
}
// 定义哈希表类
class HashTable {
private Node[] table;
private int size;
// 构造函数
public HashTable(int size) {
this.size = size;
this.table = new Node[size];
for (int i = 0; i < size; i++) {
this.table[i] = null;
}
}
// 哈希函数
private int hash(int key) {
return key % size;
}
// 插入元素
public void put(int key, String value) {
int index = hash(key);
Node node = new Node(key, value);
if (table[index] == null) {
table[index] = node;
} else {
Node cur = table[index];
while (cur.next != null) {
cur = cur.next;
}
cur.next = node;
}
}
// 查找元素
public String get(int key) {
int index = hash(key);
Node cur = table[index];
while (cur != null) {
if (cur.key == key) {
return cur.value;
}
cur = cur.next;
}
return null;
}
}
// 测试代码
public class HashTableTest {
public static void main(String[] args) {
HashTable ht = new HashTable(10);
ht.put(1, "Tom");
ht.put(2, "Jerry");
ht.put(11, "Mike");
System.out.println(ht.get(1)); // Tom
System.out.println(ht.get(2)); // Jerry
System.out.println(ht.get(11)); // Mike
System.out.println(ht.get(3)); // null
}
}
```
在上述代码中,我们通过定义Node类来表示哈希表中的节点,然后定义HashTable类来实现哈希表。其中,put()方法用于插入元素,get()方法用于查找元素。在构造函数中,我们初始化哈希表的大小,并将每个桶初始化为null。在哈希函数中,我们使用取余运算来计算哈希值。在插入元素时,如果对应桶为空,则直接插入;否则,遍历链表,将元素插入链表的末尾。在查找元素时,根据哈希值找到对应桶,然后遍历链表,查找是否有对应的元素。如果找到,则返回元素的值;否则,返回null。