二叉树和哈希表的对比与选择

优缺点

哈希表

哈希表使用hash function来对输入的数据分配index到哈希表对应的槽中。 理论上来说，该哈希表插入和查找操作的时间复杂度都是O(1)。

当更多的数插入时，哈希表冲突的可能性就更大。对于冲突，哈希表通常有两种解决方案：
第一种是线性探索，相当于在冲突的槽后建立一个单链表，这种情况下，插入和查找以及删除操作消耗的时间会达到O(n)，且该哈希表需要更多的空间进行储存。

第二种方法是开放寻址，他不需要更多的空间，但是在最坏的情况下（例如所有输入数据都被map到了一个index上）的时间复杂度也会达到O(n)。

所以，在决定建立哈希表之前，最好可以估计输入的数据的size。否则，resize哈希表的过程将会是一个非常消耗时间的过程，且扩展之后所有的数都需要重新rehash。

二叉树

平衡二叉树的话，对于每个元素的插入和查找操作的时间复杂度是O(log(n))，n是树的节点个数，log(n)通常是树的深度。
当然，对于不平衡的情况，那就需要更复杂的数据结构的树（红黑树等）进行处理。

二叉树不会有冲突（collision），这意味着我们能够保证二叉树的插入和查找操作一直都是O(log(n))的时间复杂度。

二叉树的空间占用跟输入的输入数据一致。所以我们不需要为二叉树预先分配固定的空间。所以，你也不需要预先知道输入数据的size。

所有的元素可能在树中，还是是排序好的。

选择

哈希表

如果你预先知道输入数据的大小，而且有足够的空间储存哈希表，且不需要对数据进行排序，那么哈希表总是好的。因为哈希表在插入，查找和删除操作中只需要常数时间。

二叉树

如果数据是持续的加入，你预先不知道数据的大小，那么二叉树是一个折中的选择。