散列表和二叉树的优缺点对比，如何在这两种数据结构中选择

Question

如题所述

Answer 1

散列表是一种数据结构，通过散列函数（也就是 hash 函数）将输入映射到一个数字，一般用映射出的数字作为存储位置的索引。数组在查找时效率很高，但是插入和删除却很低。而链表刚好反过来。设计合理的散列函数可以集成链表和数组的优点，在查找、插入、删除时实现 O(1) 的效率。散列表的存储结构使用的也是数组加链表。执行效率对比可以看下图 1.3：

散列表的主要特点：1. 将输入映射到数字2. 不同的输入产生不同的输出3. 相同的输入产生相同的输出4. 当填装因子超过阈值时，能自动扩展。填装因子 = 散列表包含的元素数 / 位置总数，当填装因子 =1，即散列表满的时候，就需要调整散列表的长度，自动扩展的方式是：申请一块旧存储容量 X 扩容系数的新内存地址，然后把原内存地址的值通过其中的 key 再次使用 hash 函数计算存储位置，拷贝到新申请的地址。5. 值呈均匀分布。这里的均匀指水平方向的，即数组维度的。如果多个值被映射到同一个位置，就产生了冲突，需要用链表来存储多个冲突的键值。极端情况是极限冲突，这与一开始就将所有元素存储到一个链表中一样。这时候查找性能将变为最差的 O(n)，如果水平方向填充因子很小，但某些节点下的链表又很长，那值的均匀性就比较差。

Answer 2

散列表的优点很明显，查询时间为常数1，最快的查询速度。
二叉树的查询速度也很快，为log(n)但是慢于散列表。

但是二叉树相对于散列表的优点是，对于一个二叉查找树，即binary search tree，其中元素是排序的，而散列表是不排序的。那么问题就来了，在你手机中，显然你希望联系人是按姓氏排序的，那么如果你使用散列表，你就需要额外的内存空间进行排序，而二叉查找树本身就是排好序的，因此节省了宝贵的空间。

结论就是，在空间不受限制时，且不需要高频率的排序操作时，二叉查找树不如散列表。反之二叉查找树优于散列表。本回答被提问者和网友采纳