哈希表和二叉查找树的区别于选取

哈希表 哈希表是一种线性结构，通过对 key 值合理 hash，理论上插入与查询操作都可以做到 O(1) 复杂度。由于哈希表可能会存在冲突，在处理哈希冲突时，无论是线拉链法还是开放寻址法，都能达到 O(n) 的复杂度，且如果哈希表不够存储当前数据，可能需要扩充哈希表，很可能需要重新计算哈希。 常见的以哈希表为基础的数据结构类似于 Java 的 HashMap、C++ 的 unordered_map、set 等

二叉查找树 二叉查找树我们一般讨论自平衡二叉查找树，像红黑树、AVL 树。对于 n 个节点的树，插入与查询的时间复杂度都在 O(logn)，虽然如此，但二叉查找树的大小的动态的，不会限制节点个数，因此对于未知数据比较友好。 常见的二叉查找树类似于 C++ 的 map 便是用红黑树实现的。

因此选择的关键点在于数据的性质与大小，如果数据不易产生哈希冲突、数据量已知可控那么就可选择哈希表，如果数据是未知不可控的，就最好选择二叉查找树