Stay determined.

Hash Table

Posted on By Yang Guang
Viewed   times

SEPARATE CHAINING

=================================================
今天在听老师讲hash冲突的时候,先讲的是按位往后放

当时就想问为什么不直接用链表串到本来的地址上,能大大减少ASL

没想到老师接下来就介绍了拉链法;D

MD今天学完才知道,HashSort时间复杂度是O(1)的

以前还以为O(1)只存在与幻想中…-_-!!

最坏时间复杂度也只有O(n),牺牲了空间,但是效果是很明显的。

(如图所示,按hash函数 h(key) = key % m; m = 8; 查找10时只用三步)




================================================================================================