h*********3
发帖数: 111 | 1 以前我的理解是hash表没有遍历一说。但sgi的实现有iterator.
是所有的hash_map实现都提供了iterator吗？
这个iterator是如何遍历的呢？复杂度是多少？ |
g*********s
发帖数: 1782 | 2
应该是。
一个链表？hash里存链表的指针？
【在 h*********3 的大作中提到】
: 以前我的理解是hash表没有遍历一说。但sgi的实现有iterator.
: 是所有的hash_map实现都提供了iterator吗？
: 这个iterator是如何遍历的呢？复杂度是多少？
|
g**e
发帖数: 6127 | 3 buckets are stored in an array, iterate the linked list in this array
【在 h*********3 的大作中提到】
: 以前我的理解是hash表没有遍历一说。但sgi的实现有iterator.
: 是所有的hash_map实现都提供了iterator吗？
: 这个iterator是如何遍历的呢？复杂度是多少？
|
g*********s
发帖数: 1782 | 4 what is linked list in an array?
【在 g**e 的大作中提到】
: buckets are stored in an array, iterate the linked list in this array
|
j***r
发帖数: 69 | 5 Hash table or hash map is an array. Iterator just loops though this array,
with keys not in order. |
r**d
发帖数: 316 | 6 hash map 的实现： 一般arrry并不直接存value，而是存一个链表，以解决hash冲突.
【在 g*********s 的大作中提到】
: what is linked list in an array?
|
g*********s
发帖数: 1782 | 7 then the iteration complexity is decided by the total hash map capacity,
not the valid entry.
if so, this is inefficient and i doubt if this is the real implementation.
array,
【在 j***r 的大作中提到】
: Hash table or hash map is an array. Iterator just loops though this array,
: with keys not in order.
|
g*********s
发帖数: 1782 | 8 u still didn't answer how to iterate all the valid entries.
【在 r**d 的大作中提到】
: hash map 的实现： 一般arrry并不直接存value，而是存一个链表，以解决hash冲突.
|
|
r**d
发帖数: 316 | 9 这个和实现有关，java.util.hashmap的办法是在array里面找下一个非空元素，这应该
是个链表头，然后再遍历链表。
【在 g*********s 的大作中提到】
: u still didn't answer how to iterate all the valid entries.
|
g*********s
发帖数: 1782 | 10 lz's post is exactly asking how in reality it is implemented. we know the
principle.
in ur example, how to find the next non-empty list entry? if u iterate the
array element one bye one, the efficiency is low.
【在 r**d 的大作中提到】
: 这个和实现有关，java.util.hashmap的办法是在array里面找下一个非空元素，这应该
: 是个链表头，然后再遍历链表。
|
j***r
发帖数: 69 | 11 The hash_map is open-source. Check the source code and you'll get the answer
.
【在 g*********s 的大作中提到】
: lz's post is exactly asking how in reality it is implemented. we know the
: principle.
: in ur example, how to find the next non-empty list entry? if u iterate the
: array element one bye one, the efficiency is low.
|
g**e
发帖数: 6127 | 12 First off, in java HashMap does not implement Collection interface, it does
NOT have iterator, in stead it has keySet, values and entrySet methods where
you can get a collection of keyset/value set/entry set to iterate the map.
Second, iterating a hashmap is quite slow, comparing to other collection
classes. Hashmap should not be used if you need to iterate the map
frequently.
Back to your question, to find the next entry, simply call entry.next
and check if next entry is empty, and use a while loop to advance to the
next non-empty bucket. This is not too slow because it's iterating through
the entry set (each entry is a linked list), but surely it's not very
efficient as hashmap is not designed to do this.
This is how java HashMap implements "iterator". check the inner class
HashIterator source code for details.
应该
【在 g*********s 的大作中提到】
: lz's post is exactly asking how in reality it is implemented. we know the
: principle.
: in ur example, how to find the next non-empty list entry? if u iterate the
: array element one bye one, the efficiency is low.
|
