比较开放地址和链地址法冲突处理技术的优缺点

发布网友发布时间：2022-05-16 11:20

共1个回答

热心网友时间：2023-10-21 00:09

开放地址法将所有结点均存放在散列表（Hash）T[0..m-1]中，链址法将互为同义词的结点链成一个但链表，而将此链表的头指针放在散列表T[0..m-1]中。
与开放地址相比链地址法有如下优点：1，链地址法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短。2，链地址法中链表的结点是动态申请的，故它更适合造表前无法确定表长的情况，3，开放定址法为了减少冲突要求填充因子较小，故结点规模较大时会浪费很多空间，而链地址法中填充因子可以大于1且结点较大时，拉链法中增加的指针域可以忽略不计，因此节省空间，4，链地址法构造的散列表删除结点很方便，只需简单的删去链表上相应的结点即可。