哈希表针对冲突的两种方式优缺点是什么?

哈希表在针对冲突的时候,会采用两种方式,一种是冲突链表的方式(由于Java的HashMap就是如此处理的,我倒是可以容易理解),另一个是开放地址方式.百度了一些资料,对比优缺点的时候,还是不太理解.我对他们的执行方式的理解. 首先,相同点都是冲突的时候,在开辟一块内存用来存储冲突的数据,并且也需要相应的指针指向这块内存(如果不记录地址的啊,每次寻找都得重新计算一遍,速度太慢了吧~,~! 所以我是这么认为的),那么应该是等同于都是使…
关注者
28
被浏览
2208

3 个回答

看这个 Hash table
介绍的四种主流冲突解决方式, 比百度的好懂多啦

另外, 动静态内存分配的问题, 和动静态语言无关
开放定址法一般还真没有冲突的时候额外新开辟内存,仅仅是再算出一个新的地址而已。而且还真是每次都要算一遍,并且还真没有很慢。

Linux 的进程(好吧 task 并不是真的进程只是不知道应该翻译成什么了)管理中的哈希表就是使用链表解决冲突。Python 的 Dictionary 实现是使用的开放定址法。

开放定址的性能分析在 CLRS 中有分析,随着装填因子(表项数/容量)升高探查期望也将升高。故开放定址法适用于不是那么满的表。Python 的实现中当项数大于容量的2/3时就会给表扩容保证其装填因子的范围。

数组……就算只会 Java 也应该应该知道 new 一个数组是怎么回事吧(逃
而且静态语言一般指类型系统,题主想说的应该是编译语言和直译(解释)语言吧(逃