两个面试题 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

两个面试题

两个面试题# JobHunting - 待字闺中

z*e2014-07-10 07:07

1 楼

arraylist的add(Object o)的复杂度是多少？
hashtable的get(Object key)的复杂度是多少？
严格来说无所谓语言
因为其它语言同样可以实现类似的数据结构
但是如果你非要计较，那就java
不考虑多线程
进阶问题：
考虑多线程情况下，如何优化这两个数据结构？

l*i2014-07-10 07:07

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*a2014-07-10 07:07

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*i2014-07-10 07:07

4 楼

hashcode must be fast, or it would be useless.