b****g
发帖数: 192 | 1 how does HashMap works in Java？
我不明白问题是什么意思，他让我以put（key，value）为例，我就说用key算出
bucket的位置，把value存进去。
他就继续问我怎么用key算出存在hash表的位置。
这才明白他是在问我Java HashMap怎么计算hash value.跟他确认了一下，就是这个意
思。
我说就是用hash function算，他又问我到底是怎么算的，总之就是问得很细致，看样
子是要求我看过代码才行。
面试结束后，我按了一下这个页面
http://www.docjar.com/html/api/java/util/HashMap.java.html
不知道是不是源代码。
又找了一下hash函数，就是移位异或操作。
hash函数的输入参数是把key用hashCode函数计算成一个整数。hashcode的返回值实际
是object的address。
可是，java不是不能找地址吗？
我看了代码，不过hashCode函数前面有个native关键字，意思是用其他语言写的函数。
看来java里用别的语言写的函数来找对象地址了。
谁能找到这个hashCode函数的源代码？ |
e***s
发帖数: 799 | 2 他要问这个？
264 static int hash(int h) {
265 // This function ensures that hashCodes that differ only by
266 // constant multiples at each bit position have a bounded
267 // number of collisions (approximately 8 at default load
factor).
268 h ^= (h >>> 20) ^ (h >>> 12);
269 return h ^ (h >>> 7) ^ (h >>> 4);
270 }
这太牛B了吧？ |
p*****p
发帖数: 379 | 3 这个问题hash不重要
主要是怎么根据hashcode放置元素，怎么处理collision，怎么取，满了怎么办，之类
的问题
【在 b****g 的大作中提到】
: how does HashMap works in Java？
: 我不明白问题是什么意思，他让我以put（key，value）为例，我就说用key算出
: bucket的位置，把value存进去。
: 他就继续问我怎么用key算出存在hash表的位置。
: 这才明白他是在问我Java HashMap怎么计算hash value.跟他确认了一下，就是这个意
: 思。
: 我说就是用hash function算，他又问我到底是怎么算的，总之就是问得很细致，看样
: 子是要求我看过代码才行。
: 面试结束后，我按了一下这个页面
: http://www.docjar.com/html/api/java/util/HashMap.java.html
|
b****g
发帖数: 192 | 4 如果我能回答到这一步（用位操作计算hash value），他就会问我那个数值是怎么来的。
你有没有注意到这个hash函数的参数是int型？实际上算hash value是
int hash = hash(key.hashCode());
于是我就要先把key（可能是个class，int，char）转成int。
于是我查了一下Object的code，找到了关于hashCode的部分：
http://www.docjar.com/html/api/java/lang/Object.java.html
(This is typically implemented by converting the internal
address of the object into an integer, but this implementation
technique is not required by the JavaTM
programming language.)
public native int hashCode();
所以我还是没找到hashCode函数是怎么实现的。。。你能帮我找找吗？
by
【在 e***s 的大作中提到】
: 他要问这个？
: 264 static int hash(int h) {
: 265 // This function ensures that hashCodes that differ only by
: 266 // constant multiples at each bit position have a bounded
: 267 // number of collisions (approximately 8 at default load
: factor).
: 268 h ^= (h >>> 20) ^ (h >>> 12);
: 269 return h ^ (h >>> 7) ^ (h >>> 4);
: 270 }
: 这太牛B了吧？
|
b****g
发帖数: 192 | 5 我开始也是这么理解的，结果他不听，就问我java中怎么calculate hash value
【在 p*****p 的大作中提到】
: 这个问题hash不重要
: 主要是怎么根据hashcode放置元素，怎么处理collision，怎么取，满了怎么办，之类
: 的问题
|
c******4
发帖数: 22 | 6 I think he was trying to ask something about equal() and hashcode() in the
Object class.
【在 b****g 的大作中提到】
: how does HashMap works in Java？
: 我不明白问题是什么意思，他让我以put（key，value）为例，我就说用key算出
: bucket的位置，把value存进去。
: 他就继续问我怎么用key算出存在hash表的位置。
: 这才明白他是在问我Java HashMap怎么计算hash value.跟他确认了一下，就是这个意
: 思。
: 我说就是用hash function算，他又问我到底是怎么算的，总之就是问得很细致，看样
: 子是要求我看过代码才行。
: 面试结束后，我按了一下这个页面
: http://www.docjar.com/html/api/java/util/HashMap.java.html
|
h***i
发帖数: 1970 | 7 对
【在 c******4 的大作中提到】
: I think he was trying to ask something about equal() and hashcode() in the
: Object class.
|
b****g
发帖数: 192 | 8 那我该怎么回答呢？
【在 c******4 的大作中提到】
: I think he was trying to ask something about equal() and hashcode() in the
: Object class.
|
p*****p
发帖数: 379 | 9 hashcode很多是要override的
如果不管的话好像和memory reference有关
【在 b****g 的大作中提到】
: 那我该怎么回答呢？
|
l*n
发帖数: 529 | 10 一般object是返回地址对应的int，String有他自己的哈希函数，自定仪的obj可以随便
写hashCode实现，反正collision之后还有链表顶着
【在 b****g 的大作中提到】
: 那我该怎么回答呢？
|
c******4
发帖数: 22 | 11 By default, the hashcode() in Object class returns unique value, which is
decided by
the address of the object in memory.
Say, you have a HashMap map,
and you do following map.put(new Object(), 1) twice,
then map will have two entries.
So you can override the hashcode() to resolve this if this is not what you
need.
Then you may talk about the entry bucket, and collisions.
The position of the entry is decided by a hash function, say the simplest
one, mode % size of bucket.
How can you tell it's collision? as two instances which are not equal may
have same hashcode. then equals() comes to work.
then followup could be how to solve collision?
linear probing? use a linkedlist? rehashing?
Welcome to be corrected if any statement is wrong :)
【在 b****g 的大作中提到】
: 那我该怎么回答呢？
|
b****g
发帖数: 192 | 12 解释得真好，谢谢！
但是我还有一个问题，你说hashcode的返回值实际是object的address。
我也查了但是没找到hashCode函数的代码，只是在代码前的注释说返回的确实是地址。
可是，java不是不能找地址吗？
不过hashCode函数前面有个native关键字，意思是用其他语言写的函数。看来java里用
别的语言写的函数来找对象地址了。
你能找到这个hashCode函数的源代码吗？我怎么也找不到：（
【在 c******4 的大作中提到】
: By default, the hashcode() in Object class returns unique value, which is
: decided by
: the address of the object in memory.
: Say, you have a HashMap map,
: and you do following map.put(new Object(), 1) twice,
: then map will have two entries.
: So you can override the hashcode() to resolve this if this is not what you
: need.
: Then you may talk about the entry bucket, and collisions.
: The position of the entry is decided by a hash function, say the simplest
|
c******4
发帖数: 22 | 13 See if you can find it through:
http://hg.openjdk.java.net/jdk7/jdk7-gate/jdk/file/e947a98ea3c1
which is the source code of native methods in Java.
【在 b****g 的大作中提到】
: 解释得真好，谢谢！
: 但是我还有一个问题，你说hashcode的返回值实际是object的address。
: 我也查了但是没找到hashCode函数的代码，只是在代码前的注释说返回的确实是地址。
: 可是，java不是不能找地址吗？
: 不过hashCode函数前面有个native关键字，意思是用其他语言写的函数。看来java里用
: 别的语言写的函数来找对象地址了。
: 你能找到这个hashCode函数的源代码吗？我怎么也找不到：（
|
