趣文:哈希表哪家强?几大编程语言吵起来了,结果没想到…

广告位

比特宇宙编程语言联合委员会准备举办一次大会,主题为哈希表,给各大编程语言帝国都发去了邀请函。 很快就到了大会这…

比特宇宙编程语言联合委员会准备举办一次大会,主题为哈希表,给各大编程语言帝国都发去了邀请函。

很快就到了大会这一天

联合委员会秘书长开场发言:“诸位,为促进技术交流与发展,增强各帝国友谊,联合委员会特设此盛会,感谢诸位的捧场”

会场传来一阵鼓掌声······

秘书长继续发言:“本次大会的主题是哈希表,人类程序员使用最多的数据容器之一,各大编程语言帝国相信都有实现。今天的大会就围绕哈希表分为几个议题讨论,首先是第一个议题:存储结构与冲突解决”

存储结构与冲突解决

来自 Go 帝国的 map 率先发言:“哈希表,哈希表,首先得是个表嘛,所以最基本的要用一个数组来存储,数组中的每一个元素叫做 bucket。至于 hash 冲突嘛,就用链表来解决嘛”

GoLang帝国的map说完,有人站了起来:“英雄所见略同!在下C++帝国的unordered_map,我们基本上也是选择的这种方法”

此时,Python 帝国的代表提出了质疑:“链表确实可以解决冲突,不过嘛,这要是冲突太多,链表太长,搜寻起来岂不费时?”

GoLang 帝国的 map 和 C++ 帝国的 unordered_map 面面相觑,不知如何应对。

“链表太长的话,那就转成树结构!”,就在这时,又有人站了起来。

见有人起身,Python 帝国代表转身问道:“在下乃 Python 帝国的字典 dict{},敢问阁下怎么称呼”

“我是 Java 帝国的 HashMap,和前面两位兄台的策略大体相同,只是在冲突过多,具体来说链表长度超过 8 的时候就转换成红黑树的结构,以此加快查找”

说完,map、unordered_map 松了一口气,和 HashMap 一起坐下了。

dict{} 继续发问:“在座的都是这个思路,用链表解决冲突?”

说完,另外一位代表站了起来,“等等,我们 C# 帝国的 HashTable 就没用链表!”

dict{} 露出了满意的表情,“那你们是怎么解决冲突的呢?”

“咱 HashTable 内部使用的是双重散列法,咱内部不止一种哈希计算方式,一次 Hash 冲突,咱就换一个再算,直到找到有空位的地方存储”,HashTable 回答到。

dict{} 看起来有些失望,估计这也不是他所用的方式。

“你问了半天,还没说你们 Python 是怎么处理冲突的呢?”,Java 帝国的 HashMap 开口了。

“是啊,是啊”,其他代表也跟着起哄。

见众人起哄,dict{} 只好应答:“链表法固然不错,不过需要在插入数据过程中动态分配内存构建链表节点,开销不小,我们没有采用。”

“那到底用了啥,你倒是说啊,快急死我了”,C++ 的 unordered_map 有些急了。

“我们用的是一种叫开放寻址法的策略,如果发现了冲突,就按照制定的策略从这个位置往后找,直到找到有空的位置存储”,dict{} 继续说到。

“哪有那么简单的事,你把别人的位置占了,那对应那个位置的数据来了怎么办?还有查找怎么找?删除怎么处理?这不全乱套了吗”,unordered_map追问不舍。

“是这样的,按照我们既定的规则,在查找的时候就需要额外做一些工作,另外删除的时候也不能直接删除,否则会破坏规则链条·····”,接下来一段时间,dict{}给大家仔细介绍了他们的处理思路。

“你这个也太麻烦了,不如我们链表法来的清晰明了”

“这怎么就麻烦了?这好处不显而易见嘛?”,dict{}也不甘示弱。

这时,秘书长打断了大家的争辩:“诸位,诸位,静一静,静一静,咱们这个议题到此为止,进入下一个议题:哈希到位置映射

哈希到位置映射

急性子的C++帝国代表 unordered_map第一个说话:“这有什么好讨论的,不就是用hash值对哈希表数组长度进行一个求模运算吗?”

“就是,这有什么好讨论的”,C# 帝国的 HashTable 也附和到。

“哎,此言差矣,我就没用取模运算”,众人望去,这 Python 帝国的 dict{} 又要闹什么新鲜玩意。

GoLang 帝国的 map 问道:“老哥用的什么办法,别卖关子了,快说来听听”

dict{} 扫了众人一眼说到,“我的办法就是:”

关于作者: 大数据教程学习

为您推荐