r**h
发帖数: 1288 | 1 在C++中，set/map是用的红黑树，unordered_set/unordered_map使用的线性表+hash函数
那么java里面的Set、HashSet和HashMap的内部实现是什么呢？ | b*****n
发帖数: 618 | 2 Set是个interface
HashSet和HashMap实现方法是一样的，hash function + linkedlist 处理collision | t******h
发帖数: 120 | 3 HashSet internally uses HashMap, an entry in HashMap is a pair,
HashSet would only use "key" to store its value, and put dummy data in "
value".
A hash function would map the "key" to one position in the internal array in
HashMap. If collision happens in HashMap, the old value will be kicked out.
You can read the JDK source code. | s*******u
发帖数: 220 | 4 in java, it seems every object has unique hash value; this is the reason why
String is immutable. Object.hashcode() can get the unique hash value. May
not be right~
函数
【在 r**h 的大作中提到】
: 在C++中，set/map是用的红黑树，unordered_set/unordered_map使用的线性表+hash函数
: 那么java里面的Set、HashSet和HashMap的内部实现是什么呢？
| b*****n
发帖数: 618 | 5 collision指的是hash相同但并不equals的情况，你说的是equals的情况
如果真的读过sourcecode应该知道 hashcode, hash, equals这三个是不一样的概念
Entry本身就是个单链表用来处理collision
pair,
in
out.
【在 t******h 的大作中提到】
: HashSet internally uses HashMap, an entry in HashMap is a pair,
: HashSet would only use "key" to store its value, and put dummy data in "
: value".
: A hash function would map the "key" to one position in the internal array in
: HashMap. If collision happens in HashMap, the old value will be kicked out.
: You can read the JDK source code.
| t******h
发帖数: 120 | 6 Yes. You are right, i did not read the source code in detail.
【在 b*****n 的大作中提到】
: collision指的是hash相同但并不equals的情况，你说的是equals的情况
: 如果真的读过sourcecode应该知道 hashcode, hash, equals这三个是不一样的概念
: Entry本身就是个单链表用来处理collision
:
: pair,
: in
: out.
| t**e
发帖数: 36 | 7 http://hg.openjdk.java.net/jdk7/jdk7-gate/jdk/file/e947a98ea3c1
查了一下，it is a linked list implementation, i dont quite understand the
following
#1
line 467 - 468, wont newTable[i] points to the entry after original src[j]?
void transfer(Entry[] newTable) {
487 Entry[] src = table;
488 int newCapacity = newTable.length;
489 for (int j = 0; j < src.length; j++) {
490 Entry e = src[j];
491 if (e != null) {
492 src[j] = null;
493 do {
494 Entry next = e.next;
495 int i = indexFor(e.hash, newCapacity);
496 e.next = newTable[i];
497 newTable[i] = e;
498 e = next;
499 } while (e != null);
500 }
501 }
502 }
#2
">>>" is bitwise shift to the right ? how is it different from ">>"
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 }
#3 why is entry hash value generated this way?
275 static int indexFor(int h, int length) {
276 return h & (length-1);
277 }
网上大牛请解答一下，非常感谢。 |
|
