线性探测法创建人名哈希表代码分析
时间: 2024-06-19 18:03:44 浏览: 10
线性探测法是哈希表中的一种解决哈希冲突的方法。当哈希函数将两个不同的键映射到了同一个位置时,就会发生哈希冲突。线性探测法就是在这种情况下,顺序地检查下一个位置,直到找到一个空位置或者找遍整个哈希表为止。
以下是使用线性探测法创建人名哈希表的代码示例:
```c++
#include <iostream>
#include <string>
using namespace std;
const int TABLE_SIZE = 10;
class Person {
public:
string name;
int age;
Person(string n, int a) {
name = n;
age = a;
}
};
class HashTable {
private:
Person* table[TABLE_SIZE];
public:
HashTable() {
for (int i = 0; i < TABLE_SIZE; i++) {
table[i] = nullptr;
}
}
int hash(string key) {
int hashVal = 0;
for (int i = 0; i < key.length(); i++) {
hashVal += key[i];
}
return hashVal % TABLE_SIZE;
}
void insert(Person* p) {
int index = hash(p->name);
while (table[index] != nullptr) {
index++;
index %= TABLE_SIZE;
}
table[index] = p;
}
Person* search(string name) {
int index = hash(name);
while (table[index] != nullptr && table[index]->name != name) {
index++;
index %= TABLE_SIZE;
}
if (table[index] == nullptr) {
return nullptr;
} else {
return table[index];
}
}
void remove(string name) {
int index = hash(name);
while (table[index] != nullptr && table[index]->name != name) {
index++;
index %= TABLE_SIZE;
}
if (table[index] != nullptr) {
delete table[index];
table[index] = nullptr;
}
}
void printTable() {
for (int i = 0; i < TABLE_SIZE; i++) {
if (table[i] != nullptr) {
cout << "Index " << i << ": " << table[i]->name << endl;
} else {
cout << "Index " << i << ": Empty" << endl;
}
}
}
};
int main() {
HashTable h;
Person* p1 = new Person("Alice", 25);
Person* p2 = new Person("Bob", 30);
Person* p3 = new Person("Charlie", 35);
Person* p4 = new Person("David", 40);
h.insert(p1);
h.insert(p2);
h.insert(p3);
h.insert(p4);
h.printTable();
Person* p = h.search("Bob");
if (p != nullptr) {
cout << "Bob is " << p->age << " years old." << endl;
} else {
cout << "Bob not found." << endl;
}
h.remove("Bob");
h.printTable();
return 0;
}
```