c++ - 哈希表实现(使用数组)
问题描述
这是我第一次尝试实现哈希表。我正在阅读一些指南,但似乎不对。对于我所有的功能,我必须创建一个新的 int 然后使用它?
对于我所有的函数调用,我正在创建一个“int hi”。并使用它来散列我正在制作的任何密钥。这是设置哈希表的正确方法吗?我找不到那么多解释如何正确设置哈希表和正确映射键的指南。
我仍在处理整个代码,但我不想继续。我很确定我缺少一些东西。在每个函数调用中创建新的整数和字符串对我来说似乎很不合适。
下面是我正在处理的代码。
#include <iostream>
using namespace std;
class HashTable
{
struct Element
{
string key;
int mark;
};
Element** table;
int size;
private:
int hash(string);
public:
HashTable(int);
~HashTable();
void insert(string);
void remove(string);
bool isFull();
bool isEmpty();
void clear();
void print();
bool find(string);
};
int HashTable::hash(string s)
{
return 0;
}
HashTable::HashTable(int s)
{
int hi;
table = new Element *[s];
for (int i = 0; i < size; i++)
{
table[hi] = NULL;
}
}
HashTable::~HashTable()
{
int hi;
for (int i = 0; i < size; i++)
{
if (table[hi])
delete table[hi];
}
delete[]table;
}
void HashTable::insert(string s)
{
string key;
int hi;
if (!isFull)
{
hi = hash(key);
while (table[hi]->mark == 1)
{
hi = (hi + 1) % size;
}
table[hi]->key = key;
table[hi]->mark = 1;
}
}
void HashTable::remove(string s)
{
string key;
int i;
int hi;
if (!isEmpty)
{
hi = hash(key);
i = 0;
}
while (i < size && table[hi]->mark != 0)
{
if (table[hi]->key == key)
{
table[hi]->mark = 2;
break;
}
i = i + 1;
hi = (hi + 1) % size;
}
}
bool HashTable::isFull()
{
int hi;
if (table[hi] >= size)
{
return true;
}
}
bool HashTable::isEmpty()
{
int hi;
if (table[hi] >= size)
{
return true;
}
}
void HashTable::clear()
{
int hi;
for (int i = 0; i < size; i++)
{
delete table[hi];
table[hi] = nullptr;
}
}
void HashTable::print()
{
int hi;
string key;
for (int i = 0; i < size; ++i)
{
if (table[hi]->mark == 2)
{
printf("test \n", table[hi]->key);
}
}
}
bool HashTable::find(string s)
{
string key;
int i;
int found;
int hi;
if (!isEmpty)
{
hi = hash(key);
found = false;
}
i = 0;
while (table[hi]->mark != 0 && (!found) && i < size)
{
if (table[hi]->mark == 1 && table[hi]->key == key)
{
found = true;
}
hi = (hi + 1) % size;
i = i + 1;
}
return found;
}
解决方案
首先,让我们修复您的构造函数:
HashTable::HashTable(int s)
{
table = new Element*[s];
size = s; // you forgot this line
for (int i = 0; i < size; i++)
{
table[i] = NULL; // "i", not "hi"
}
}
您希望您的哈希操作将任何唯一字符串映射到一个数字(以哈希表数组的大小为模):
你可以这样做:
size_t HashTable::hash(const string& s)
{
size_t hashvalue = 0;
for (char ch : s)
{
hashvalue += (unsigned)ch;
}
return (hashvalue % size);
}
C++ 本身有一个内置的散列算法,它可能具有更好的传播和分布:
size_t HashTable::hash(const string& s)
{
std::hash<string> hasher;
size_t hi = hasher(s) % size;
return hi;
}
这更接近您想要的 Element 类型:
struct Element
{
string key;
Element* next;
};
因此,插入可以简单地是这样的:
void insert(const string& key)
{
size_t hi = hash(key);
Element* e = Lookup(key);
if (e == nullptr)
{
e = new Element();
e->key = key;
e->value = value;
e->next = table[hi];
table[hi] = e;
}
else
{
// item already exists
}
}
并查找:
Element* Lookup(const string& key)
{
Element* e = nullptr;
size_t hi = hash(key);
e = table[hi];
while (e && e->key != key)
{
e = e->next;
}
return e;
}
而remove是类似的查找操作
void HashTable::remove(const string& key)
{
size_t hi = hash(key);
Element* e = table[hi];
Element* prev = nullptr;
while (e && e->key != key)
{
prev = e;
e = e->next;
}
if (e && prev)
{
prev->next = e->next;
delete e;
}
else if (e)
{
table[hi] = e->next;
delete e;
}
}
我会把剩下的方法留在你的课堂上作为练习。
推荐阅读
- r - R S4类对象函数槽访问另一个槽中的函数
- facebook-graph-api - Facebook API - 如何获取广告帐户 ID
- c++ - 由于标头中的#define 不匹配而导致内存损坏
- c++ - 将 Eigen::MatrixXd 矩阵转换为 cgal 容器类型
- reactjs - 如何在 Electron 应用程序中实现 ReactJs?
- python - 如何在 Matplotlib 中获取包装文本的高度?
- mysql - 如何找到针对不同数据库的查询执行时间差异的原因?
- ios - 如何使用iOS图表仅在饼图中显示所选切片上的文本
- java - JAXB 覆盖 package-info.java:“命名空间”应该是什么?
- java - 用于查找连续字符串中的两个字符是否为数字的程序在java中不起作用