c***G 发帖数: 88 | 1 tree和hashmap有啥区别?有啥优缺点?什么情况下用哪一个?
我已经多次碰到过这个问题了,有次就这个问题被问了20多分钟,实在是不知道要怎么
回答了。。。
各位大牛能给点建议么?
谢谢! |
R*****i 发帖数: 2126 | 2 感觉比较tree和hashmap就是比较牛头和马嘴,除了都是collection以外,没有任何相
似之处。tree是一种hierarchy,寻找的cost是O(log(n)),并且可以让您快速找到大小顺
序中的左邻右舍,hashmap是hashtable?, 根据key找value,寻找的cost是O(1). |
z****e 发帖数: 54598 | 3 java吧
其它语言hashtable比较多
java里面对比hashmap vs treemap
你google一下,可以看到很多 |
z****e 发帖数: 54598 | 4 tree是一种结构
hashcode是另外一种结构
java常见两个对比
hashmap vs treemap,这个是结构的不同,索引方式的不同
hashmap vs hashtable,这个是并发差异,结构是类似的 |
z****e 发帖数: 54598 | 5 tree和hash应该是最常见的两种结构
总体而言,现在用hash比较多,因为hash可以提供amortized o(1)复杂度的search
while tree只能保证o(lgn)复杂度的search
但是如果需要频繁排序,比如经常性插入,删除,弹出一个最小最大值
这个时候才用tree,比如priorityqueue,其实就是堆排序
否则就用hash,包括分布式现在常见的consistent hashing |
c***G 发帖数: 88 | 6 谢谢各位。
我有次被人问了20多分钟的应该是tree和hash的比较,我基本把这里说的都给说上了,
可是面试官还在问我想想有啥别的区别,又没有任何提示。实在是想不到还要答什么。
。。
【在 z****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : tree和hash应该是最常见的两种结构 : 总体而言,现在用hash比较多,因为hash可以提供amortized o(1)复杂度的search : while tree只能保证o(lgn)复杂度的search : 但是如果需要频繁排序,比如经常性插入,删除,弹出一个最小最大值 : 这个时候才用tree,比如priorityqueue,其实就是堆排序 : 否则就用hash,包括分布式现在常见的consistent hashing
|
z****e 发帖数: 54598 | 7 你说了为什么要用hashcode了么?
复杂度一旦说出来,我不信对方还会追问有啥差别
那个amortized复杂度很多人不懂
【在 c***G 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 谢谢各位。 : 我有次被人问了20多分钟的应该是tree和hash的比较,我基本把这里说的都给说上了, : 可是面试官还在问我想想有啥别的区别,又没有任何提示。实在是想不到还要答什么。 : 。。
|
z****e 发帖数: 54598 | 8 20分钟,你把tree和hash如何实现给他说一遍
这差异要是看不懂,那没啥道理,差别太明显了 |
f*******w 发帖数: 1243 | 9 个人感觉两点:一是复杂度,O(1)和O(logn)的区别; 二是tree结构通常是说BST,所以
整体是排好序的,而hashmap不是。所以当你需要in order输出,或者找到前一个/后一
个element的时候用tree比hash好。
反正我面试的时候碰到这题回答这两点一般就move on了…… |