2019年10月

再说什么是线程安全之前我们先来聊聊什么是进程。

1、什么是进程?

先来看一张图

我们看到的这些单独运行的程序就是一个独立的进程,进程之间是相互独立存在的。

我们上面图中的QQ、酷狗播放器、电脑管家等等都是独立的进程。

2、什么是线程?

上面简单的说了一下什么是进程,进程想要执行任务需要依赖线程,换句话说就是进程中的最小执行单位就是线程,并且一个进程中至少有一个线程。

3、什么是多线程?

提到多线程这里要说两个概念,就是串行和并行,搞清楚这个我们才能更好的理解多线程。

  • 串行:其实是相对于单条线程来执行多个任务来说的,我们就拿下载文件来举个例子,我们下载多个文件,在串行中它是按照一定的顺序去进行下载的,也就是说必须等下载完A之后,才能开始下载B,它们在时间上是不可能发生重叠的。
  • 并行:下载多个文件,开启多条线程,多个文件同时进行下载,这里是严格意义上的在同一时刻发生的,并行在时间上是重叠的。

4、线程安全

线程安全就是多线程访问时,采用了加锁机制,当一个线程访问该类的某个数据时,进行保护,其他线程不能进行访问直到该线程读取完,其他线程才可使用。不会出现数据不一致或者数据污染。

5、线程不安全

就是不提供数据访问保护,有可能出现多个线程先后更改数据造成所得到的数据是脏数据

ArrayList和Vector有什么区别?HashMap和HashTable有什么区别?StringBuilder和StringBuffer有什么区别?这些都是Java面试中常见的基础问题。面对这样的问题,回答是:ArrayList是非线程安全的,Vector是线程安全的;HashMap是非线程安全的,HashTable是线程安全的;StringBuilder是非线程安全的,StringBuffer是线程安全的。因为这是昨晚刚背的《Java面试题大全》上面写的。此时如果继续问:什么是线程安全?线程安全和非线程安全有什么区别?分别在什么情况下使用?这样一连串的问题,一口老血就喷出来了…


二者如何取舍

非线程安全是指多线程操作同一个对象可能会出现问题。而线程安全则是多线程操作同一个对象不会有问题。

线程安全必须要使用很多synchronized关键字来同步控制,所以必然会导致性能的降低。

所以在使用的时候,如果是多个线程操作同一个对象,那么使用线程安全的Vector;否则,就使用效率更高的ArrayList。

非线程安全!=不安全

有人在使用过程中有一个不正确的观点:我的程序是多线程的,不能使用ArrayList要使用Vector,这样才安全。

非线程安全并不是多线程环境下就不能使用。注意我上面有说到:多线程操作同一个对象。注意是同一个对象。比如最上面那个模拟,就是在主线程中new的一个ArrayList然后多个线程操作同一个ArrayList对象。

如果是每个线程中new一个ArrayList,而这个ArrayList只在这一个线程中使用,那么肯定是没问题的。

线程安全的实现

线程安全是通过线程同步控制来实现的,也就是synchronized关键字。

class Counter
{
    private int count = 0;

    public int getCount()
    {
        return count;
    }

    public synchronized void addCount()
    {
        count++;
    }
}

https://www.cnblogs.com/lijingran/p/8722301.html

问题:

最近一直在研究算法,无论是计算机算法概论、还是数据结构书中,关于算法的时间复杂度很多都用包含O(logN)这样的描述,但是却没有明确说logN的底数究竟是多少。

数学定义

logn数学定义
在数学中,对数是对求幂的逆运算,正如除法是乘法的倒数,反之亦然。
如果 ,即a的x次方等于N(a>0,且a≠1),那么数x叫做以a为底N的对数(logarithm),记作 。其中,a叫做对数的底数,N叫做真数,x叫做“以a为底N的对数”。
用于二分法。

解答:

算法中log级别的时间复杂度都是由于使用了分治思想,这个底数直接由分治的复杂度决定。
如果采用二分法,那么就会以2为底数,三分法就会以3为底数,其他亦然。
不过无论底数是什么,log级别的渐进意义是一样的。
也就是说该算法的时间复杂度的增长与处理数据多少的增长的关系是一样的。
我们先考虑O(logx(n))和O(logy(n)),x!=y,我们是在考虑n趋于无穷的情况
求当n趋于无穷大时logx(n)/logy(n)的极限可以发现,极限等于lny/lnx,也就是一个常数,
也就是说,在n趋于无穷大的时候,这两个东西仅差一个常数。
所以从研究算法的角度log的底数不重要。
最后,结合上面,我也说一下关于大O的定义(算法导论28页的定义),
注意把这个定义和高等数学中的极限部分做比较,
显然可以发现,这里的定义正是体现了一个极限的思想
假设我们将n0取一个非常大的数字,
显然,当n大于n0的时候,我们可以发现任意底数的一个对数函数其实都相差一个常数倍而已。
所以书上说写的O(logn)已经可以表达所有底数的对数了,就像O(n^2)一样。
没有非常严格的证明,不过我觉得这样说比较好理解,如果有兴趣证明,完全可以参照高数上对极限趋于无穷的证明。
原文链接