首页 > 代码库 > 散列表

散列表

散列表(hash table)
在直接寻址的方式下,具有关键字k的元素被放到槽k中。在散列方式下,该元素放在槽h(k)中;
即利用散列函数hash funciton h , 由关键字k计算出槽的位置。这里,函数h将关键字的全域U映射到
散列表hash table T[0....m-1]的槽位上
h:U -> {0,1,....,m-1}
这里存在一个问题,两个关键字可能映射到同一槽中。我们称这种情形为冲突。
散列的含义是随机混杂和拼凑。
解决冲突的办法,链接法,开发寻址法
通过链接伐解决冲突

技术分享

 


把散列到同一槽中的所有元素都放在一个链表中。
CHAINED-HASH-INSERT(T,x)
insert x at the head of list T
CHAINED-HASH-SEAARCH(T,x)
CHAINED-HASH-DELEETE(T,x)

技术分享

 

散列表