San*_*alp 4 c++ hashtable hashmap binary-search-tree data-structures
我有一个困惑:
我在很多帖子中都读到Hash-map被实现为二进制搜索树,这使得各种操作时间复杂度成为对数顺序.
另一方面,哈希表提供恒定的时间提取.
但是,正如我在本文中所读到的那样,在两个数据结构中检索/搜索元素的复杂性方面没有提供任何差异.
所以,这是我的问题 -
由于散列表保证提供恒定的搜索时间复杂度,因此它们的实现必须与散列映射的实现不同.那么,如果有人不提供恒定时间搜索,为什么有人会使用哈希映射.另外,为什么首先将它们实现为二叉搜索树？
我知道哈希映射以排序的形式存储密钥,并通过映射提供迭代.但是,也可以在哈希表中提供相同的内容.
您的困惑源于以下内容:
散列图实现为二叉搜索树
他们不是.没有明智的命名约定会使用术语"hashmap"来描述基于树的结构.
例如,在Java中,HashMap基于哈希表并TreeMap基于树.
C++在其标准容器的命名中既不使用"hash"也不使用"tree".这两个容器对应于HashMap和TreeMap是std::unordered_map和std::map.