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 的大作中提到】
: 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 的大作中提到】
: 谢谢各位。
: 我有次被人问了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了…… |
