c*****y
发帖数: 90 | 1 SDET Position
包括recruiter一共见了5个人，最后一个是大经理，我拿到的schedule上没安排的。我
因为已经有一个offer了，要recruiter尽快告诉我结果，最后没拿到offer。所有的人都
很nice，题目也很简单。我说我答得不好的吧，反正我也没签什么协议。
一个array，没有sorted，找出所有pairs，sum是100。我说出了不同方法。问我如果用
hash table，准备用什么hash function？这是我一点都不知道怎么答的。我非CS科班
毕业，只知道用hash table，从来没考虑过用什么hash function。接下来就讨论hash
table实现的问题，也答得不好。 |
m******9
发帖数: 968 | |
m****n
发帖数: 589 | 3 谢谢分享～
我也要去面SDET～
hash function也不会。。。。汗
请问还有别的什么题目？
人都
hash
【在 c*****y 的大作中提到】
: SDET Position
: 包括recruiter一共见了5个人，最后一个是大经理，我拿到的schedule上没安排的。我
: 因为已经有一个offer了，要recruiter尽快告诉我结果，最后没拿到offer。所有的人都
: 很nice，题目也很简单。我说我答得不好的吧，反正我也没签什么协议。
: 一个array，没有sorted，找出所有pairs，sum是100。我说出了不同方法。问我如果用
: hash table，准备用什么hash function？这是我一点都不知道怎么答的。我非CS科班
: 毕业，只知道用hash table，从来没考虑过用什么hash function。接下来就讨论hash
: table实现的问题，也答得不好。
|
s******t
发帖数: 2374 | 4
人都
hash
是说用比如Java里面的Hashtable
table.get(key);
table.put(key, entry);
吧
【在 c*****y 的大作中提到】
: SDET Position
: 包括recruiter一共见了5个人，最后一个是大经理，我拿到的schedule上没安排的。我
: 因为已经有一个offer了，要recruiter尽快告诉我结果，最后没拿到offer。所有的人都
: 很nice，题目也很简单。我说我答得不好的吧，反正我也没签什么协议。
: 一个array，没有sorted，找出所有pairs，sum是100。我说出了不同方法。问我如果用
: hash table，准备用什么hash function？这是我一点都不知道怎么答的。我非CS科班
: 毕业，只知道用hash table，从来没考虑过用什么hash function。接下来就讨论hash
: table实现的问题，也答得不好。
|
c*****y
发帖数: 90 | 5 不是。我觉得就是问key和value的map用什么hash function。我觉得如果事先稍微
看看就好了，也不会一句也答不上来。
【在 s******t 的大作中提到】
:
: 人都
: hash
: 是说用比如Java里面的Hashtable
: table.get(key);
: table.put(key, entry);
: 吧
|
s******t
发帖数: 2374 | 6 你是说比如
long hash = getHashcode（key）;
Object entry = value[hash];
?
我只是随便举个例子。真是的hashcode的取法会复杂一些。
【在 c*****y 的大作中提到】
: 不是。我觉得就是问key和value的map用什么hash function。我觉得如果事先稍微
: 看看就好了，也不会一句也答不上来。
|
c*****y
发帖数: 90 | 7 你看看Introduction to Algorithms上的。我正在看。
【在 s******t 的大作中提到】
: 你是说比如
: long hash = getHashcode（key）;
: Object entry = value[hash];
: ?
: 我只是随便举个例子。真是的hashcode的取法会复杂一些。
|
s******t
发帖数: 2374 | 8 好。我翻出来看看。
【在 c*****y 的大作中提到】
: 你看看Introduction to Algorithms上的。我正在看。
|
m******9
发帖数: 968 | 9 hash function通常有:
modulo
folding
mid-square function
extraction
radix transformation
collision的解决办法:
line probing
quadratic search
double hashing
chaining
bucket addressing |
s******t
发帖数: 2374 | 10 一般比如jdk的实现里面他们处理collision了么？（我看了看好像没看到）
我之前好像看到说如果bucket如果超过factor了就自动增加一倍之类的。算是double
hashing
么？
我得好好看看书了。
【在 m******9 的大作中提到】
: hash function通常有:
: modulo
: folding
: mid-square function
: extraction
: radix transformation
: collision的解决办法:
: line probing
: quadratic search
: double hashing
|
m******9
发帖数: 968 | 11 double hashing是说, 存在2个hash function, 一个用来计算index, 另一个在出现
collision的时候才用到:
比如:
h(key),
if conflict, then h(key)+h'(key)
if conflict again, then h(key)+ 2*h'(key)
if conflict again, ...
h(key)+ i*h'(key)
最后再取余: % size |
c******f
发帖数: 2144 | |
g*******y
发帖数: 1930 | 13 这个叫 open addressing吧
【在 m******9 的大作中提到】
: double hashing是说, 存在2个hash function, 一个用来计算index, 另一个在出现
: collision的时候才用到:
: 比如:
: h(key),
: if conflict, then h(key)+h'(key)
: if conflict again, then h(key)+ 2*h'(key)
: if conflict again, ...
: h(key)+ i*h'(key)
: 最后再取余: % size
|
