m*******i
发帖数: 370 | 1 Assume you have large set of data, say more than 100,000 elements. Each data
element has a unique string associated with it.
What data structures would you use in the implementation of a single new
data structure that has all of the following properties? Explain how this
implementation works.
i) Optimal algorithmic random access time to any element knowing only the
unique string associated with it (as above)
ii) Keeps track of the order of insertion into the data structure, so you
can acquire |
r**u
发帖数: 1567 | 2 看看这样行不行，所有的elements都insert到一个array里，hash table里放element的
index。
给定一个unique string，先到hash table里找到index，再去array找到element。
另外，array是按insert顺序ordered，还可以用any index访问array里的任意元素。
data
the
the
【在 m*******i 的大作中提到】
: Assume you have large set of data, say more than 100,000 elements. Each data
: element has a unique string associated with it.
: What data structures would you use in the implementation of a single new
: data structure that has all of the following properties? Explain how this
: implementation works.
: i) Optimal algorithmic random access time to any element knowing only the
: unique string associated with it (as above)
: ii) Keeps track of the order of insertion into the data structure, so you
: can acquire
|
e********c
发帖数: 66 | |
m*******i
发帖数: 370 | 4 thanks! 应该是这个。不知道怎么implement的
是使用array吗？比如
MyClass* obj_ptr=new MyClass[N];
根据hash key insert to the array, 然后maintain pointer根据insert 的顺序指向
上一个insert的obj和下一个将要insert的obj?
不知道是不是这样？给解释一下吧，多谢！
【在 e********c 的大作中提到】
: LinkedHashMap
|
r**u
发帖数: 1567 | 5 hash_table 放index,
array放elements
hash_table and array are seperate.
key->(hash_table) get index, index->(array) get element.
你现在是要用俩种方式做索引，一种是用key and hash it，令一种是用array的index
，我觉得single DS只能做到用一种索引。
【在 m*******i 的大作中提到】
: thanks! 应该是这个。不知道怎么implement的
: 是使用array吗？比如
: MyClass* obj_ptr=new MyClass[N];
: 根据hash key insert to the array, 然后maintain pointer根据insert 的顺序指向
: 上一个insert的obj和下一个将要insert的obj?
: 不知道是不是这样？给解释一下吧，多谢！
|
e********c
发帖数: 66 | 6 Map.Entry has two attributes in HashMap. With LinkedHashMap, each
node has two additional fields: before and after to form a doubly linked
list. The implementation is the same as any Hashtable but you need to update
before and after nodes accordingly upon insertion and deletion.
You can take a look at the implementation in SUN's JDK source code. |
s*****i
发帖数: 355 | 7 赞详细解答
update
【在 e********c 的大作中提到】
: Map.Entry has two attributes in HashMap. With LinkedHashMap, each
: node has two additional fields: before and after to form a doubly linked
: list. The implementation is the same as any Hashtable but you need to update
: before and after nodes accordingly upon insertion and deletion.
: You can take a look at the implementation in SUN's JDK source code.
|
m*******i
发帖数: 370 | 8 多谢！
update
【在 e********c 的大作中提到】
: Map.Entry has two attributes in HashMap. With LinkedHashMap, each
: node has two additional fields: before and after to form a doubly linked
: list. The implementation is the same as any Hashtable but you need to update
: before and after nodes accordingly upon insertion and deletion.
: You can take a look at the implementation in SUN's JDK source code.
|
b****r
发帖数: 1272 | 9 请问linksedHashMap对第三条怎么实现的：iii) Optimal algorithmic random access
time to any element knowing only the index of insertion.
given index, random access elem in linkedlist?
update
【在 e********c 的大作中提到】
: Map.Entry has two attributes in HashMap. With LinkedHashMap, each
: node has two additional fields: before and after to form a doubly linked
: list. The implementation is the same as any Hashtable but you need to update
: before and after nodes accordingly upon insertion and deletion.
: You can take a look at the implementation in SUN's JDK source code.
|
s*****i
发帖数: 355 | 10 first, it's a hashmap
access
【在 b****r 的大作中提到】
: 请问linksedHashMap对第三条怎么实现的：iii) Optimal algorithmic random access
: time to any element knowing only the index of insertion.
: given index, random access elem in linkedlist?
:
: update
|
|
|
x***y
发帖数: 633 | 11 I still don't get it....the index of the order is not the key, and then how
to use hashmap to access it in the constant time?
【在 s*****i 的大作中提到】
: first, it's a hashmap
:
: access
|
e********c
发帖数: 66 | 12 values() will return an array of contents in the LinkedHashMap in the
insertion order. You only need to call it once and the query will be O(1)
after the first call. |
x***y
发帖数: 633 | 13 So, basically, LinkedHashMap realizes the 3rd property with an additional
array...
If insertion or deletion happens, we have to adjust array(call value())
again, right?
【在 e********c 的大作中提到】
: values() will return an array of contents in the LinkedHashMap in the
: insertion order. You only need to call it once and the query will be O(1)
: after the first call.
|
r********9
发帖数: 1116 | |
r********9
发帖数: 1116 | |
