散列表 淩亂°似流年 2021-09-26 14:26 364阅读 0赞 **直接寻址表** 假设某个动态集合中的每个元素取自于U=\{0,1,2,…,m-1\},这里的m不是一个很大的数,假设没有两个元素具有相同的关键字。我们用一个数组(**直接寻址表**),记为T\[0…m-1\],其中的每个位置成为槽,对应全局区域中的一个关键字,如T\[k\]指向集合中关键字为k的元素,如果不存在k元素,则记为T\[k\]=null。 优点:在U很小的情况下,插入、查找、删除的时间复杂度均为O(1)。 缺点:在U很大的情况下,计算机的可用内存可能无法存储;若关键字集合远小于U,则会造成很大的空间浪费。 **散列表** 在散列表中,将存储需求降至了|O(K)|,同时保持了其查找元素的优势。在该方式下,关键字k存放在槽h(k)中,即利用散列函数h,由关键字计算出槽的位置,这里,函数h将关键字k的全局U映射到散列表T\[0…m\]的槽位上。 **散列函数**: 好的散列函数的特点:h尽可能随机,即将关键字映射到同一个槽中的可能性尽可能降低。 多数散列函数都假定关键字的全域为自然数集N=\{0,1,2…\}。因此,如果所给关键字不是自然数,则需要找到一种方式将其转换为自然数。例如字符串pt,可以转换为十进制整数对(112,116)(ASCII码表),然后以128为基数,pt即为关键字(112\*128)+116=14452。 三种设计散列函数的方法: **除数散列法** h(k)=k mod m (m应该取不太接近2的整数幂的素数) **乘数散列法** h(k)=|m(kA mod 1)|(向下取整) (kA mod 1指的是取kA的小数部分,m的取值一般为2的某个幂次,A取(√5-1)/2是一个比较理想的值) **全域散列**(性能最好) 随机地选择散列函数,使之独立于要存储的关键字。 两个关键字可能会映射到同一个槽中,这种情况成为冲突。 为了解决冲突,有两种方法:链接法和开放寻址法。 **链接法**: 把散列到同一槽中的所有元素都放在一个链表中。如果槽j中有一个指针,它指向存储所有散列到j的元素的链表的表头;如果不存在这样的元素,则槽j中为NULL。 **开放寻址法**: 在开放寻址法中,所有元素都存放在散列表里,即每个表项或包含动态集合的的一个元素,或包含NIL。当查找某个元素时,要系统的检查所有的表项,知道找到所需的元素或者最终表明该元素不在表中。 线性探查: ![这里写图片描述][70] 二次探查: ![这里写图片描述][70 1] 双重探查: ![这里写图片描述][70 2] [70]: /images/20210923/03ba5a8bbc7548e0b6ca4fa508742502.png [70 1]: /images/20210923/aa356539ce33418f9747206ee920ef2f.png [70 2]: /images/20210923/630245940e5547e09048ea5782414f31.png
还没有评论,来说两句吧...