avatar
z*e
1
arraylist的add(Object o)的复杂度是多少?
hashtable的get(Object key)的复杂度是多少?
严格来说无所谓语言
因为其它语言同样可以实现类似的数据结构
但是如果你非要计较,那就java
不考虑多线程
进阶问题:
考虑多线程情况下,如何优化这两个数据结构?
avatar
l*i
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.
avatar
l*a
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.

avatar
l*i
4
hashcode must be fast, or it would be useless.
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。