hash - superfulous代码示例
hash - superfulous代码示例
提问于 2011-10-15 01:25:09
我发现这段here是最简单的散列的一个例子。它让since..basically使用模运算符将数据集从DATA_SIZE(隐含的)减少到TABLE_SIZE(定义的)。
但是，如果发生冲突，即数组元素已被占用，它将移动到
hash = (hash + 1) % TABLE_SIZE但是，如果您已经使用表大小计算了一个模数，则此行将始终生成(hash+1) b.c。当x< y时，x%y总是等于x。问题:这是一个错误吗…我的意思是它应该可以工作，但% TABLE_SIZE是额外的对吗？它在下面的代码中什么也不做。
const int TABLE_SIZE = 128;
class HashEntry
{
private:
int key;
int value;
public:
HashEntry(int key, int value)
{
this->key = key;
this->value = value;
}
int getKey()
{
return key;
}
int getValue()
{
return value;
}
};
class HashMap
{
private:
HashEntry **table;
public:
HashMap()
{
table = new HashEntry*[TABLE_SIZE];
for (int i = 0; i < TABLE_SIZE; i++) table[i] = NULL;
}
int get(int key)
{
int hash = (key % TABLE_SIZE);
while (table[hash] != NULL && table[hash]->getKey() != key) hash = (hash + 1) % TABLE_SIZE;
if (table[hash] == NULL)return -1;
else return table[hash]->getValue();
}
void put(int key, int value)
{
int hash = (key % TABLE_SIZE);
while (table[hash] != NULL && table[hash]->getKey() != key) hash = (hash + 1) % TABLE_SIZE;
if (table[hash] != NULL) delete table[hash];
table[hash] = new HashEntry(key, value);
}
~HashMap()
{
for (int i = 0; i < TABLE_SIZE; i++)
if (table[i] != NULL) delete table[i];
delete[] table;
}
};Stack Overflow用户
回答已采纳
发布于 2011-10-15 01:29:56
这个模数是在溢出的情况下存在的。
假设hash == TABLE_SIZE - 1。然后是hash + 1 == TABLE_SIZE，而是hash+1 % TABLE_SIZE == 0。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7771285
复制相关文章
相似问题
腾讯云开发者
