z****e
发帖数: 54598 | 1 arraylist的add(Object o)的复杂度是多少？
hashtable的get(Object key)的复杂度是多少？
严格来说无所谓语言
因为其它语言同样可以实现类似的数据结构
但是如果你非要计较，那就java
不考虑多线程
进阶问题：
考虑多线程情况下，如何优化这两个数据结构？ | l***i
发帖数: 1309 | 2 答一下试试。
arraylist is like c++ vector, so amortized O(1) for insertion, assuming
underlying array will double size when full.
hashtable lookup is O(1), assuming linkedlist is O(1) length, if use
chaining.
multithreading makes it more difficult, the bruteforce solution is to lock
the whole data structure when insert/delete, and this could be slow. | l*****a
发帖数: 14598 | 3 lookup姑且算O(1)
但是计算hashcode的复杂性呢？
【在 l***i 的大作中提到】
: 答一下试试。
: arraylist is like c++ vector, so amortized O(1) for insertion, assuming
: underlying array will double size when full.
: hashtable lookup is O(1), assuming linkedlist is O(1) length, if use
: chaining.
: multithreading makes it more difficult, the bruteforce solution is to lock
: the whole data structure when insert/delete, and this could be slow.
| l***i
发帖数: 1309 | 4 hashcode must be fast, or it would be useless. |
|
