c********p
发帖数: 1969 | |
z****e
发帖数: 54598 | 2 编hashcode
按照hashcode塞入bst
遇到相同的hashcode还要额外实现equals
不过一般这种时候，对equals不会有太高的效率要求
直接线性对比就好了 |
c********p
发帖数: 1969 | 3 hashcode就比如用长度来编，那之后equal了要怎么办啊？
有什么可行操作没？
【在 z****e 的大作中提到】
: 编hashcode
: 按照hashcode塞入bst
: 遇到相同的hashcode还要额外实现equals
: 不过一般这种时候，对equals不会有太高的效率要求
: 直接线性对比就好了
|
z****e
发帖数: 54598 | 4 hashcode用平常常用的那个方法来编
如果equals的话，直接替换
如果遇到hashcode相同的，你要固定放到某一边去
比如大于的放右边，小于和等于就都放左边
其实就是用hashcode来当bst的index
【在 c********p 的大作中提到】
: hashcode就比如用长度来编，那之后equal了要怎么办啊？
: 有什么可行操作没？
|
c********p
发帖数: 1969 | 5 哦哦是这样啊。。。
刚才看你回复，我在想，是不是也建个linked list，然后每个node是一个linked list
，重复的就放在里边呢。。。
搜一个点的时间复杂度，近似是logN ?
【在 z****e 的大作中提到】
: hashcode用平常常用的那个方法来编
: 如果equals的话，直接替换
: 如果遇到hashcode相同的，你要固定放到某一边去
: 比如大于的放右边，小于和等于就都放左边
: 其实就是用hashcode来当bst的index
|
z****e
发帖数: 54598 | 6 那样就复杂了
你把hashcode相同的情况放到tree里面比较好
其实复杂度是一样的，反正都是挨个比过去
list
【在 c********p 的大作中提到】
: 哦哦是这样啊。。。
: 刚才看你回复，我在想，是不是也建个linked list，然后每个node是一个linked list
: ，重复的就放在里边呢。。。
: 搜一个点的时间复杂度，近似是logN ?
|
c********p
发帖数: 1969 | 7 嗯嗯，你的方法更好。
【在 z****e 的大作中提到】
: 那样就复杂了
: 你把hashcode相同的情况放到tree里面比较好
: 其实复杂度是一样的，反正都是挨个比过去
:
: list
|
s*******n
发帖数: 305 | 8 LZ准备写几个methods呀， 可以讨论下？ 我也正准备写这个。 其实我感觉这个更像是
写个2叉树， 而不是hashtable.
二叉树
isRoot(xxx);
insert(xxx);
remove(xxx);
size(xxx);
inorder(xxx);
hashtable
put(xxx)
get(xxx)
remove(xxx)
size(xxx)
containkey(xxx)
iterator(xxx) |
c********p
发帖数: 1969 | 9 我不写，我看看思路就好啊。
【在 s*******n 的大作中提到】
: LZ准备写几个methods呀， 可以讨论下？ 我也正准备写这个。 其实我感觉这个更像是
: 写个2叉树， 而不是hashtable.
: 二叉树
: isRoot(xxx);
: insert(xxx);
: remove(xxx);
: size(xxx);
: inorder(xxx);
: hashtable
: put(xxx)
|
c********p
发帖数: 1969 | 10 本来就是二叉树啊。。。。。
【在 s*******n 的大作中提到】
: LZ准备写几个methods呀， 可以讨论下？ 我也正准备写这个。 其实我感觉这个更像是
: 写个2叉树， 而不是hashtable.
: 二叉树
: isRoot(xxx);
: insert(xxx);
: remove(xxx);
: size(xxx);
: inorder(xxx);
: hashtable
: put(xxx)
|
|
|
c********p
发帖数: 1969 | 11 对了，你这个tree的root怎么选择？
bst的root，不是一般是中点么？
可是你并不知道一共会有多大啊？
【在 z****e 的大作中提到】
: hashcode用平常常用的那个方法来编
: 如果equals的话，直接替换
: 如果遇到hashcode相同的，你要固定放到某一边去
: 比如大于的放右边，小于和等于就都放左边
: 其实就是用hashcode来当bst的index
|
x*********w
发帖数: 533 | 12
Lazy .....
【在 c********p 的大作中提到】
: 我不写，我看看思路就好啊。
|
c********p
发帖数: 1969 | 13 是你换个马甲到处咬我么？
【在 x*********w 的大作中提到】
:
: Lazy .....
|
r*********n
发帖数: 4553 | 14 What is the point of implementing hashtable in terms of bst?
When you generate hash value, you lose all order statistics. Then you insert
the hash value into a bst. Although the hash values are ordered, but it has
nothing to do with the ordering of the original values. |
c********p
发帖数: 1969 | 15 查找快啊。。。
比放到数组里快。
insert
has
【在 r*********n 的大作中提到】
: What is the point of implementing hashtable in terms of bst?
: When you generate hash value, you lose all order statistics. Then you insert
: the hash value into a bst. Although the hash values are ordered, but it has
: nothing to do with the ordering of the original values.
|
c********p
发帖数: 1969 | 16 哈哈哈好像把你和另一位搞混了。。。
知道你是谁了。。。
【在 x*********w 的大作中提到】
:
: Lazy .....
|
x*********w
发帖数: 533 | 17
@__@ ...
【在 c********p 的大作中提到】
: 哈哈哈好像把你和另一位搞混了。。。
: 知道你是谁了。。。
|
r*********n
发帖数: 4553 | 18 为什么会比放到数组里面还要快
比如一个基于open addressing的hashtable，可以让数组很大，hash collision的概率
很小，这样基本上是O(1)查找。
如果你放到bst里面去，至少是O(logN）的时间
【在 c********p 的大作中提到】
: 查找快啊。。。
: 比放到数组里快。
:
: insert
: has
|
c********p
发帖数: 1969 | 19 My bad...说错了。。。
问问楼上的吧。。。
【在 r*********n 的大作中提到】
: 为什么会比放到数组里面还要快
: 比如一个基于open addressing的hashtable，可以让数组很大，hash collision的概率
: 很小，这样基本上是O(1)查找。
: 如果你放到bst里面去，至少是O(logN）的时间
|
q********c
发帖数: 1774 | 20 这就是一找抽题，如果谁问我这种题，我只能说他/她是白痴，连基本的hashtable怎么
工作的都不懂。 |
|
|
q********c
发帖数: 1774 | 21 插入bst要 log(n)，为什么不直接插入数组O(1)?先搞清楚hashtable vs bst,再解题，
这种答案，直接就fail了。
【在 z****e 的大作中提到】
: 编hashcode
: 按照hashcode塞入bst
: 遇到相同的hashcode还要额外实现equals
: 不过一般这种时候，对equals不会有太高的效率要求
: 直接线性对比就好了
|
s********r
发帖数: 403 | 22 从上下文来看，很可能是
把bst 挂在 hash 的 bucket 上，取代 linklist。
【在 r*********n 的大作中提到】
: 为什么会比放到数组里面还要快
: 比如一个基于open addressing的hashtable，可以让数组很大，hash collision的概率
: 很小，这样基本上是O(1)查找。
: 如果你放到bst里面去，至少是O(logN）的时间
|
f*******b
发帖数: 520 | |
s******c
发帖数: 99 | 24 我认为你说的很靠谱
【在 s********r 的大作中提到】
: 从上下文来看，很可能是
: 把bst 挂在 hash 的 bucket 上，取代 linklist。
|
z****e
发帖数: 54598 | 25 bst不需要额外的内存，hashtable会浪费一点内存
做一点trade off不是很正常的么
又不是什么都是以时间复杂度为第一优先
c++程序猿不天天就在计算内存的使用么？
看到另外一个贴，我想起来
hashtable的iterator本身无意义
如果你想根据hashcode 顺序 或者其他序输出结果的话
那显然是tree好用
【在 q********c 的大作中提到】
: 插入bst要 log(n)，为什么不直接插入数组O(1)?先搞清楚hashtable vs bst,再解题，
: 这种答案，直接就fail了。
|
z****e
发帖数: 54598 | 26 不过要真计较起理由来的话
那tree的确用得不多，在现实环境中
大多数时候用map就是hashmap
我反正是没怎么用过treemap
而且扯到tree很有可能要上递归
这两个都是不怎么用的算法
所以说算法在某种意义上就是回字的那多余的三种写法
用来对付面试用的
不要说tree了，就是hashtable
现在也基本上被淘汰了
还有vector，只有在一些老的代码里面才会看到
这主要是实现时候在多线程环境里面做得太死
不够灵活，后期大面积被其他类所取代 |
c********p
发帖数: 1969 | 27 你去抽cc150的主编吧。。。
【在 q********c 的大作中提到】
: 这就是一找抽题，如果谁问我这种题，我只能说他/她是白痴，连基本的hashtable怎么
: 工作的都不懂。
|
r*********n
发帖数: 4553 | 28 原来这才是面官的意图。
但是如果每个bucket真的很大了，成为bottleneck，要吗增加bucket数量，要吗用
second-level hashtable。
【在 s********r 的大作中提到】
: 从上下文来看，很可能是
: 把bst 挂在 hash 的 bucket 上，取代 linklist。
|
c********p
发帖数: 1969 | 29 解释一下呗？
是说一个hashcode对应很多元素，这样搜的时候要在linkedlist里挨个遍历。。。用
bst就快了，对么？
【在 r*********n 的大作中提到】
: 原来这才是面官的意图。
: 但是如果每个bucket真的很大了，成为bottleneck，要吗增加bucket数量，要吗用
: second-level hashtable。
|
s*******n
发帖数: 305 | 30
的确， 我也是在，CC 150 5th edition, Chapter 1, 的内容看到提了3个基本知识题
, 所以开始写的。。。
1. hashtable (array+list)
2. hashtable (bst)
3. StringBuffer
【在 c********p 的大作中提到】
: 你去抽cc150的主编吧。。。
|
|
|
s*******n
发帖数: 305 | 31
可以这么说， 每个bucket挂一个bst的话， 是O(logn), linked list是O(n).
要是从这个角度理解的话， 那么查找的最坏情况就可能是O(n), 如果插入的N个数据都
是hash collsion 的话
所以用二叉树除了 time space trade off, 这种情况最坏也就是O(logn)
【在 c********p 的大作中提到】
: 解释一下呗？
: 是说一个hashcode对应很多元素，这样搜的时候要在linkedlist里挨个遍历。。。用
: bst就快了，对么？
|
z****e
发帖数: 54598 | 32 其实就是不同数据结构之间的转换
等于是练习基本功
tree要转换成其他数据结构的话，是比较好的选择
各种序的遍历都很容易
hashtable相比之下就难得多
不过hashtable这种结构本身就是一个做到极致的产物
一般也不会要求去转换成其他数据结构
【在 s*******n 的大作中提到】
:
: 可以这么说， 每个bucket挂一个bst的话， 是O(logn), linked list是O(n).
: 要是从这个角度理解的话， 那么查找的最坏情况就可能是O(n), 如果插入的N个数据都
: 是hash collsion 的话
: 所以用二叉树除了 time space trade off, 这种情况最坏也就是O(logn)
|
c********p
发帖数: 1969 | 33 不是说每个bucket挂一个bst吧？而是说整个的是一个bst？
【在 s*******n 的大作中提到】
:
: 可以这么说， 每个bucket挂一个bst的话， 是O(logn), linked list是O(n).
: 要是从这个角度理解的话， 那么查找的最坏情况就可能是O(n), 如果插入的N个数据都
: 是hash collsion 的话
: 所以用二叉树除了 time space trade off, 这种情况最坏也就是O(logn)
|
s*******n
发帖数: 305 | 34
恩， 所以准备就把BST一写， hashtable不管了。
老了， 记性不好了， 只能练习基本功了。
【在 z****e 的大作中提到】
: 其实就是不同数据结构之间的转换
: 等于是练习基本功
: tree要转换成其他数据结构的话，是比较好的选择
: 各种序的遍历都很容易
: hashtable相比之下就难得多
: 不过hashtable这种结构本身就是一个做到极致的产物
: 一般也不会要求去转换成其他数据结构
|
c********p
发帖数: 1969 | 35 没看懂，你说的这啥意思？
【在 s*******n 的大作中提到】
:
: 恩， 所以准备就把BST一写， hashtable不管了。
: 老了， 记性不好了， 只能练习基本功了。
|
r*********n
发帖数: 4553 | 36 你每个bucket可以再挂一个小的hashtable，对于所有hash collision的元素重新hash
一遍（用不同的hash function）, 然后2nd-level hashtable的每个bucket用数组，不
要用linked list，因为数组能存到cpu cache里面去，比linked list快很多。所以最
后的结果还是O(1)。
另外用bst，每个node有left, right children pointer，其实根本不省内存
memory average search hit
Balanced BST 64N 1.39lgN
Hashtable 32N~128N <2.5
cited from pp. 487 <> by Sedgewick
【在 c********p 的大作中提到】
: 解释一下呗？
: 是说一个hashcode对应很多元素，这样搜的时候要在linkedlist里挨个遍历。。。用
: bst就快了，对么？
|
s*******n
发帖数: 305 | 37
不是课后题， 而是在讲hastable和stringbuffer的知识是有提的
【在 c********p 的大作中提到】
: 没看懂，你说的这啥意思？
|
s*******n
发帖数: 305 | 38
hash
【在 r*********n 的大作中提到】
: 你每个bucket可以再挂一个小的hashtable，对于所有hash collision的元素重新hash
: 一遍（用不同的hash function）, 然后2nd-level hashtable的每个bucket用数组，不
: 要用linked list，因为数组能存到cpu cache里面去，比linked list快很多。所以最
: 后的结果还是O(1)。
: 另外用bst，每个node有left, right children pointer，其实根本不省内存
: memory average search hit
: Balanced BST 64N 1.39lgN
: Hashtable 32N~128N <2.5
: cited from pp. 487 <> by Sedgewick
|
