如何创建哈希表

Question

我想在继续之前提及我已经查看了在本网站以及其他网站上提出相同问题的其他问题.我希望我能得到一个好的答案,因为我的目标是双重的:

1. 最重要的是,我想学习如何创建哈希表.
2. 其次,我发现Stack Overflow上的很多答案都倾向于假设某个主题的知识水平通常不存在,特别是对于较新的类型.话虽这么说,我希望编辑我的主要信息,一旦我弄明白自己,就会更深入地解释这个过程.

---

在主菜上:

据我所知,到目前为止,哈希表是一个列表数组(或类似的数据结构),希望最佳地尽可能少地进行冲突,以保持其受到称赞的O(1)复杂性.以下是我目前的流程:

所以我的第一步是创建一个指针数组:

Elem ** table;
table = new Elem*[size];//size is the desired size of the array

我的第二步是创建一个散列函数(一个非常简单的函数).

int hashed = 0;
hashed = ( atoi( name.c_str() ) + id ) % size;
//name is a std string, and id is a large integer. Size is the size of the array.

我的第三步是创建一些东西来检测碰撞,这是我目前所处的部分.

这是一些伪代码:

while( table[hashedValue] != empty )
    hashedValue++

else
    put in the list at that index.

它相对不优雅,但我仍处于"这是什么"阶段.忍受我.

还有别的事吗？我错过了什么或做错了吗？

谢谢

Answer 1

处理查找空槽位并调整表大小的过程。