定义Java类来实现一个字符串键/值对的哈希表,遵循下面的规范。1. 哈希表: 在一个名为StrHashTable.java的文件中定义一个名为StrHashTable的类。这个类要实现以下方法: insert(String k, String v) - 将字符串键/值对k,v添加到哈希表的适当索引处。不处理碰撞。delete(String k) - 从哈希表中删除一个键/值对,给出键k。hashFunction(String k) - 使用 "folding with strings "方法,创建一个哈希函数,返回字符串k的哈希代码。 ○ rehash() - 当负载率达到75%时,增加哈希表的大小(2倍) ○ contains(String k) - 如果字符串k在哈希表中,返回true,否则返回false。get(String k) - 返回哈希表中的项目,给定键k。isEmpty() - 如果哈希表中没有任何东西,返回true,否则返回false。size()--返回存储在哈希表中的项目数量。dump() - 将哈希表的内容打印到屏幕上,使其符合以下格式: index: key, value 0: key1, value1 1: key2, value2 2: key3, value3 3: ... 2. 节点:为你的StrHashTable中的节点定义一个叫做Node的类。它可以是一个单独文件中的外部类,名为Node.java,也可以是StrHashTable的一个内部类。它应该有以下内容: 一个成员变量来保存字符串的键。一个用于保存字符串值的成员变量。一个构造函数,将键/值对作为两个字符串参数,并将其复制到Node的私有成员变量中。3. 3. 调试: 编写一个程序类,创建一个或多个StrHashTable对象,并确保你的所有方法按照规范工作。例如,你可以写一个程序,从文本文件中读取单词,并将它们放入你的哈希表,计算发生碰撞的次数。
时间: 2024-03-10 11:50:33 浏览: 68
好的,我知道了。下面是实现Java类来实现一个字符串键/值对的哈希表的代码:
StrHashTable.java:
```
public class StrHashTable {
private Node[] table;
private int size;
public StrHashTable(int initialSize) {
table = new Node[initialSize];
size = 0;
}
public void insert(String k, String v) {
int index = hashFunction(k);
table[index] = new Node(k, v, table[index]);
size++;
if (size >= 0.75 * table.length) {
rehash();
}
}
public void delete(String k) {
int index = hashFunction(k);
Node prev = null;
Node current = table[index];
while (current != null && !current.key.equals(k)) {
prev = current;
current = current.next;
}
if (current != null) {
if (prev == null) {
table[index] = current.next;
} else {
prev.next = current.next;
}
size--;
}
}
public int hashFunction(String k) {
int hash = 0;
for (int i = 0; i < k.length(); i++) {
hash += k.charAt(i);
}
return hash % table.length;
}
private void rehash() {
Node[] oldTable = table;
table = new Node[2 * oldTable.length];
size = 0;
for (int i = 0; i < oldTable.length; i++) {
Node current = oldTable[i];
while (current != null) {
insert(current.key, current.value);
current = current.next;
}
}
}
public boolean contains(String k) {
int index = hashFunction(k);
Node current = table[index];
while (current != null) {
if (current.key.equals(k)) {
return true;
}
current = current.next;
}
return false;
}
public String get(String k) {
int index = hashFunction(k);
Node current = table[index];
while (current != null) {
if (current.key.equals(k)) {
return current.value;
}
current = current.next;
}
return null;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public void dump() {
for (int i = 0; i < table.length; i++) {
Node current = table[i];
System.out.print(i + ": ");
while (current != null) {
System.out.print(current.key + ", " + current.value + " ");
current = current.next;
}
System.out.println();
}
}
private class Node {
private String key;
private String value;
private Node next;
public Node(String k, String v, Node n) {
key = k;
value = v;
next = n;
}
}
}
```
Node.java:
```
public class Node {
private String key;
private String value;
private Node next;
public Node(String k, String v, Node n) {
key = k;
value = v;
next = n;
}
public String getKey() {
return key;
}
public String getValue() {
return value;
}
public Node getNext() {
return next;
}
}
```
测试程序:
```
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
public class Test {
public static void main(String[] args) {
StrHashTable table = new StrHashTable(16);
int collisions = 0;
try {
BufferedReader reader = new BufferedReader(new FileReader("words.txt"));
String line;
while ((line = reader.readLine()) != null) {
String[] words = line.split("\\s+");
for (int i = 0; i < words.length; i++) {
if (table.contains(words[i])) {
collisions++;
}
table.insert(words[i], "");
}
}
reader.close();
} catch (IOException e) {
e.printStackTrace();
}
System.out.println("Collisions: " + collisions);
System.out.println("Size: " + table.size());
System.out.println("Empty: " + table.isEmpty());
System.out.println("Contains \"the\": " + table.contains("the"));
System.out.println("Get \"the\": " + table.get("the"));
table.dump();
}
}
```
注意:此代码仅供参考,实际使用时需要根据实际情况进行修改。
阅读全文