h*****3
发帖数: 1391 | 1 1) which one can be accessed randomly, hash table, binary tree, array or
linkedlist?
2) difference between fork & exec.
我咋觉得１）可以ｈａｓｈ ｔａｂｌｅ和array. 可标答是ａｒｒａｙ。 |
d**u
发帖数: 1065 | 2 其实问得不严谨。可以做一个random access的hash table，只不过他问的hash table
是.net或java那种hash table，用树结构实现的，不可random access |
k**********g
发帖数: 989 | 3 In this question, it seems "random access" means O(1) access given the index
of the item (consecutive numbers assigned to each item, from 0 to N-1).
Hash table is an array of pairs between hash values and content. If you know
either (1) the hash value of your item, or (2) a "replica item" from which
you can recalculate the hash value, then you can access that item in O(1).
But a Hash table (a basic one) doesn't assign any item index to items, nor
does it remember it.
Thinking of them as maps with different properties. Map as a concept is very
general and widely applicable to almost all containers. |
f*******n
发帖数: 12623 | 4
index
know
which
very
Hash table has worst case O(n) access, because multiple items (in the worst
case, all items) could be put in the same bucket, and you have to traverse
them linearly to find the one you want.
The question doesn't really make sense. Binary tree and hash table are
associative containers (indexed by some key element). Whereas arrays and
linked lists are sequences (indexed by integer from 0). So they are not even
the same type of thing.
【在 k**********g 的大作中提到】
: In this question, it seems "random access" means O(1) access given the index
: of the item (consecutive numbers assigned to each item, from 0 to N-1).
: Hash table is an array of pairs between hash values and content. If you know
: either (1) the hash value of your item, or (2) a "replica item" from which
: you can recalculate the hash value, then you can access that item in O(1).
: But a Hash table (a basic one) doesn't assign any item index to items, nor
: does it remember it.
: Thinking of them as maps with different properties. Map as a concept is very
: general and widely applicable to almost all containers.
|
f*******n
发帖数: 12623 | 5 "用树结构实现的" what? hash table = hash table. 和树结构无关系
table
【在 d**u 的大作中提到】
: 其实问得不严谨。可以做一个random access的hash table，只不过他问的hash table
: 是.net或java那种hash table，用树结构实现的，不可random access
|
d**u
发帖数: 1065 | 6 怎么没关系？！stl的map就是用rbtree实现的。
【在 f*******n 的大作中提到】
: "用树结构实现的" what? hash table = hash table. 和树结构无关系
:
: table
|
y**********u
发帖数: 6366 | 7 这个类似于java的TreeMap
HashMap和树没有关系,stl扩展里有hash_map,和这个map一点关系都没有
【在 d**u 的大作中提到】
: 怎么没关系？！stl的map就是用rbtree实现的。
|
d**u
发帖数: 1065 | 8 OK.是我说的不准确。应该说hashtable和rbtree都是dictionary的实现方法。
hashtable的确和tree无关。
【在 y**********u 的大作中提到】
: 这个类似于java的TreeMap
: HashMap和树没有关系,stl扩展里有hash_map,和这个map一点关系都没有
|
