HashMap和HashTable的区别

HashMap 和HashTable有什么区别呢? 这个问题在stackOverflow上面有接近3000个提问,虽然是一个基础的知识点,作为热门问题翻译的分类,我觉的也可以翻译一下,具体的区别还是建议大家在阅读源码的基础上,体会这2个类的设计意图。

大概有3点不同:

  • HashTable是线程安全的,HashMap不是,HashMap更适用于非线程安全的环境,如果类本身就不存在共享,非线程安全效率更高,推荐适用HashMap。
  • HashTable的key和value都不允许null,HashMap允许有一个null的key和任意多个null的value。
  • HashMap有一个子类是LinkedHashMap,如果你想读的时候的顺序和写的时候顺序一样的话,可以很轻松的把HashMap修改为LinkedHashMap就实现了这个特性,如果以前使用的是HashTable,就没有这么方便了。

翻译完。

转载请标示: http://hushengdong/2016/12/20/HashMap和HashTable的区别/

Constant Amortized time恒定分摊时间

在上一节讨论CPU的流水线工作机制的时候,提到了一个算法复杂度的衡量原则,即Amortized Time,这次我们要讨论的是Constant Amortized Time,先在StackOverflow上面搜索了一下,有相关的内容,但是赞成人数不是特别多,我先翻译一下简单版本的解释,如果大家想看更详细的介绍,请移步到这里来what’s amortized time

当我们讨论算法复杂度的时候,恒定分摊时间是什么意思呢?

举个例子简单解释一下:

如果一个操作执行100万次,那么就不会关心其中最快的一次或者最慢的一次耗费了多长时间,而是执行100万次操作总共耗费了多长时间。

所以执行一次很慢确实不太重要,只是偶尔一次很慢在大批量执行的情况下会被摊销,所以恒定分摊时间就意味着是执行一次操作的平均时间,如果执行的次数够多,分摊时间不一定就是常量,也有可能是线性或者对数分摊时间。

我们来看一个动态数组新增元素的例子(java中可以参考ArrayList),通常新增一个元素所耗费的时间就是常量O(1),但是每一次当数组被填充满了,需要扩容到原来的2倍,然后会生成一个新数组,并且把老数组里面的元素复制到新数据当中去,释放老数据内存空间,假设分配新数组空间和释放老数组内存空间耗费时间都是常量,新增一个元素的时间会放大到O(n),n就是当前数组的大小。

所以每一次数组的扩容,都会花费最后一次扩容2倍的时间,在扩容之前也等待了2次同样的时间,因此每次扩容的时间可以分摊到每次新增元素的时间中,这意味着如果数据够大,从长远来看,将m个元素添加到动态数组中花费的时间是O(m),因此单个新增耗费的时间就是O(1)。

翻译完。

转载请标示: http://hushengdomg.com/2016/12/19/Constant-Amortized-time恒定分摊时间/