AVL vs带链接的Hashtable

Question

我知道avl树的最好情况和最坏情况会被记录为查找，插入和删除。然而，最好的情况和最糟糕的情况是，链接的哈希表是什么？如果给出两个神秘数据结构，我将如何区分两者？

Answer 1

链接的哈希表最好的情况和最坏的情况是什么？

查找，插入，删除操作的最佳时间为O（1）或恒定时间。对于最坏的时候，

• 插入：O（K），其中k =最长链元件的数目：O（1），假定链通过只是增加了链
• 删除的端部进行。 k == n散列函数非常差，并且所有n值映射到相同条目并被链接。所以，绝对最坏的情况是O（n）。
• 发现：O（N），使用同样理由删除

我将如何区分这两个如果给出了两个神秘的数据结构？

只是一个想法：在这两种结构

• 插入数据并绘制插入时间插入操作VSñ。选择数据以使模仿AVL树的最坏情况（即如果整数，请按1000000，99999，999998 ...的顺序插入），但不适用于散列表。
• 注意正在生成的情节。 AVL树将从头开始具有插入时间log（n），而对于散列表，这应该是相当恒定的。大约第1000个插入式ALV树将插入10次（假设插入发生最坏情况）。但是对于hashtable，插入时间应该和以前几乎相同。假设散列表有足够的容量和散列函数是不够愚蠢与序列数据，如'1000000，99999，999998 ...'
• 冲突如果仍然不确定，然后轰炸这两个结构与插入，希望填满散列表并强制它开始链接。多次插入后，注意情节。 AVL仍然保持log（n）曲线，但散列表将显示不同的曲线，如：具有较高常数值的恒定时间。