链地址法哈希表链表有序对增删查操作运行时间的影响问题

以下回答基于链地址法的常规实现前提：冲突链为单向链表、按key的升序排列，哈希函数计算桶索引的耗时不计入讨论范围。

• 已有键的搜索运行时间影响
  普通无序冲突链哈希表搜索已有key时，需要从头遍历链表直到匹配到目标节点，最坏时间复杂度为O(k)（k为对应冲突链的长度），平均需遍历k/2个节点。
  有序冲突链场景下，因为链表不支持随机访问，无法使用二分查找做优化，仍然需要顺序遍历到匹配节点才能终止，最坏和平均时间复杂度和无序场景基本一致，没有明显性能提升。
• 不存在的键的搜索运行时间影响
  普通无序冲突链哈希表搜索不存在的key时，必须遍历完整条链表才能确认key不存在，时间复杂度固定为O(k)。
  有序冲突链场景下，只要遍历到第一个key值大于目标key的节点，就可以直接判定目标key不存在，无需遍历完整个链表，平均搜索长度仅为k/2，只有当目标key大于链表所有节点的key时才需要遍历完链表，整体搜索性能比无序场景提升一倍左右。
• 新增、删除操作的搜索耗时影响
  • 新增操作：无序冲突链哈希表新增节点时可以直接在链表头部插入，不需要额外搜索，搜索耗时为O(1)；有序冲突链场景下必须先遍历找到符合排序规则的插入位置，平均搜索耗时为O(k/2)，相比无序场景搜索耗时更高。
  • 删除操作：两种场景都需要先定位到待删除的节点，搜索耗时差异和普通搜索逻辑一致：待删除的key存在时，两者的搜索耗时基本一致；待删除的key不存在时，有序冲突链可以提前终止遍历，搜索耗时比无序场景更低。

内容的提问来源于stack exchange，提问作者Lil_Chill