为什么一种语言使用树,另一种使用哈希表来看似相似的数据结构？
c的地图vs python的dict
树保证有O(log n).
而哈希表无法保证,除非由于可能的冲突而事先知道输入.
我倾向于认为随着问题的大小越来越多,哈希表的性能将会接近O(n).
因为我没有听说过随着问题大小的增长动态地调整表格大小的哈希函数.
因此,散列表仅对某些特定范围的问题大小有用,这就是为什么大多数DB使用树比哈希表.
解决方法
新的C标准的std :: unordered_map类型为
which is a hash table. IIRC他们希望它达到以前的标准,但在讨论中没有足够的时间被遗漏.然而,大多数流行的编译器多年来一直以这种方式提供.
换句话说,别担心太多了.使用正确的数据结构来完成任务.
至于你对哈希表的理解,这是不准确的：
I haven’t heard of a hash function that dynamically adjust its table
size as problem size grows
所有严格的散列表实现通过分配更大的数组并重新对所有的键重新进行动态调整.虽然这个操作是昂贵的,如果设计得当(要做的很少),表现仍然是摊销O(1).
