Latest Entries

Basic code about tree and sort

package com.solution.test; /* Enter your code here. Read input from STDIN. Print output to STDOUT Your class should be named Solution */ import java.util.*; public class Solution { static LinkedList stack = new LinkedList(); static TreeNode BuildTree(int low, int high, int[] array) { if (low > high) return null; int mid = 0; TreeNode node … Continue reading

Android Handler

解析Android消息处理机制 ——Handler/Thread/Looper & MessageQueue 田海立@CSDN 2011/07/12 Keywords: Android Message HandlerThread Looper UML 本文解析Android如何利用Handler/Thread/Looper以及MessageQueue来实现消息机制的内部实现。知道了它的内部实现机理之后,以后再遇到使用它们时候的任何问题就驾轻就熟、迎刃而解了。 Android利用执行在HandlerThread线程中的Looper的相应消息分发/处理,与其他线程中的消息发送结合,实现完整的消息处理机制。本文首先介绍这些消息处理过程中的参与者之间的关系,然后结合WifiService消息处理的实际实例,讲解消息处理的全过程,最后还从线程视图的角度,重新审视一下线程同步模型。 一、HandlerThread/Looper/MessageQueue的前世今生 下图是从Froyo从抽取出的HandlerThread、Looper和MessageQueue的关系图。他们被定义在package android.os。 图一:HandlerThread/Looper/MessageQueue实例关系 HandlerThread是一个Thread,继承自Thread。它保留着对Looper实例的引用,不过这里还看不到HandlerThread、Looper和MessageQueue如何实例化,这要到二、HandlerThread/Looper/MessageQueue实例化之后才能看清如何实现的。 一看便知,Looper的构造函数是私有的,外界无法直接实例化之;要实例化,只有通过Looper::prepare()。这样HandlerThread就与Looper建立了对应关系。对如何建立的是不是已经迫不及待了,那就接着看下一小节。 二、HandlerThread/Looper/MessageQueue实例化 上一节只是看了HandlerThread、Looper和MessageQueue之间的静态视图关系,他们具体如何实例化的,还要看动态的实例初始化过程。 图二:HandlerThread/Looper实例化 HandlerThread是一个Thread,在它被实例化并执行start()[序列1&2]之后,它的run()方法会在它自己的线程空间执行[序列3]。 上节已经提到了Looper的实例化是通过Looper::prepare实现的,图中可以看到Looper::prepare()正是在HandlerThread::run()中被调用而实例化[序列4&5]的。 而MessageQueue是在Looper的私有构造函数Looper()中实例化的。 总结一下,HandlerThread是被显式地通过new创建的实例,而与它绑定在一起的Looper是在HandlerThread的执行过程中被实例化的,相应的MessageQueue也是在这个过程中实例化的。 三、Looper::loop分发处理消息 上节重点讲了HandlerThread/Looper的实例化过程,它发生在Thread::run()这也是线程运行的关键,从图二也看到了Looper::loop()这个消息处理的核心正是在这里执行的,下面就看看它到底做了什么。 图三:Looper::loop()处理 图中的所有序列是发生在一个无限循环体while (true) {} 中的。 mQueue:MessageQueue是Looper保留的一份引用,通过它的next()[序列1]获取MessageQueue中的下一个要处理的消息,这个过程中如果没有相应的消息,执行它的线程会用this.wait()释放它所拥有的MessageQueue的对象锁而等待。 一旦有消息到来[序列2],Looper会用获得的Message的Handler(msg.target)来分发处理消息[序列3&4]。消息处理完之后,还要回收[序列5]。 四、Handler实现具体消息处理 在Looper::loop()消息处理的顺序图里看到了Handler,这个消息分发处理的参与者。下面结合WifiHandler这个具体的Handler看它如何参与到消息的发送、分发和处理的。 4.1 Handler实例化 WifiService中定义了如下的WifiHandler。 图四、消息的发送、分发、处理者Handler 看Handler的构造函数是需要Looper的,从上面的分析知道,Looper是在HandlerThread执行中实例化的,Looper实例如何获得的呢?看图一&图二,知道HandlerThread保留着Looper的应用mLooper,并可通过getLooper()被外面获取。而Handler的mQueue: MessageQueue可以通过mLooper.mQueue获得。 所以,Wifi的HandlerThread,WifiHandler可以这样实例化: [java] view plaincopy HandlerThread wifiThread = new HandlerThread(“WifiService”); wifiThread.start(); mWifiHandler … Continue reading

Java Collections

Java集合框架(JCF:Java Collections Framework)之比较 数组类Array是Java中最基本的一个存储结构。它用于存储一组连续的对象或基本类型的数据。其中的元素的类型必须相同。 Array是最有效率的一 种: 1、效率高,但容量固定且无法动态改变。 Array还有一个缺点是,无法判断其中实际存有多少元素,length只是告诉我们Array的容量。 2、Java中有一个Arrays类,专门用来操作Array,提供搜索、排序、复制等静态方法。 equals():比较两个Array是否相等,Array拥有相同元素个数,且所有对应元素两两相等。 fill():将值填入Array中。 sort():用来对Array进行排序。 binarySearch():在排好序的Array中寻找元素。 System.arraycopy():Array的复制。 Java Collections Framework成员主要包括两种类型,即:Collection和Map类型。 在Java中提供了Collection和Map接口。其中List和Set继承了Collection接口;Vector、ArrayList、 LinkedList三个类实现List接口,HashSet、TreeSet实现Set接口,HashTable、HashMap、 TreeMap实现Map接口。由此可见,Java中用8种类型的基本数据结构来实现其Collections Framework;下面分别进行介绍。 Vector:基于Array的List,性能也就不可能超越Array,并且Vector是”sychronized”的,这个也是Vector和ArrayList的唯一的区别。 ArrayList:同Vector一样是一个基于Array的,但是不同的是ArrayList不是同步的。所以在性能上要比Vector优越一些,但 是当运行到多线程环境中时,可需要自己在管理线程的同步问题。从其命名中可以看出它是一种类似数组的形式进行存储,因此它的随机访问速度极快。 LinkedList:LinkedList不同于前面两种List,它不是基于Array的,所以不受Array性能的限制。它每一个节点(Node) 都包含两方面的内容: 1、节点本身的数据(data); 2、下一个节点的信息(nextNode)。所以当对LinkedList做添加,删除动作的时候 就不用像基于Array的List一样,必须进行大量的数据移动。只要更改nextNode的相关信息就可以实现了所以它适合于进行频繁进行插入和删除操 作。这就是LinkedList的优势。Iterator只能对容器进行向前遍历,而 ListIterator则继承了Iterator的思想,并提供了对List进行双向遍历的方法。 List总结: 1、所有的List中只能容纳单个不同类型的对象组成的表,而不是Key-Value键值对。例如:[ tom,1,c ]; 2、所有的List中可以有相同的元素,例如Vector中可以有 [ tom,koo,too,koo ]; 3、所有的List中可以有null元素,例如[ tom,null,1 ]; 4、基于Array的List(Vector,ArrayList)适合查询,而LinkedList(链表)适合添加,删除操作。 HashSet:虽然Set同List都实现了Collection接口,但是他们的实现方式却大不一样。List基本上都是以Array为基础。但是 Set则是在HashMap的基础上来实现的,这个就是Set和List的根本区别。HashSet的存储方式是把HashMap中的Key作为Set的 对应存储项,这也是为什么在Set中不能像在List中一样有重复的项的根本原因,因为HashMap的key是不能有重复的。HashSet能快速定位 一个元素,但是放到HashSet中的对象需要实现hashCode()方法0。 TreeSet则将放入其中的元素按序存放,这就要求你放入其中的对象是可排序的,这就用到了集合框架提供的另外两个实用类Comparable和 Comparator。一个类是可排序的,它就应该实现Comparable接口。有时多个类具有相同的排序算法,那就不需要重复定义相同的排序算法,只要实现Comparator接口即可。TreeSet是SortedSet的子类,它不同于HashSet的根本就是TreeSet是有序的。它是通过SortedMap来实现的。 Set总结: 1、Set实现的基础是Map(HashMap); 2、Set中的元素是不能重复的,如果使用add(Object obj)方法添加已经存在的对象,则会覆盖前面的对象; Set里的元素是不能重复的,那么用什么方法来区分重复与否呢? 是用==还是equals()? … Continue reading

Master list of Java interview questions – 115 questions

15 questions total, not for the weak. Covers everything from basics to JDBC connectivity, AWT and JSP. What is the difference between procedural and object-oriented programs?- a) In procedural program, programming logic follows certain procedures and the instructions are executed one after another. In OOP program, unit of program is object, which is nothing but … Continue reading

Java multi-thread yield(),sleep(),wait()…

java中yield(),sleep()以及wait()的区别 往往混淆了这三个函数的使用。 从操作系统的角度讲,os会维护一个ready queue(就绪的线程队列)。并且在某一时刻cpu只为ready queue中位于队列头部的线程服务。 但是当前正在被服务的线程可能觉得cpu的服务质量不够好,于是提前退出,这就是yield。 或者当前正在被服务的线程需要睡一会,醒来后继续被服务,这就是sleep。 sleep方法不推荐使用,可用wait。 线程退出最好自己实现,在运行状态中一直检验一个状态,如果这个状态为真,就一直运行,如果外界更改了这个状态变量,那么线程就停止运行。 sleep()使当前线程进入停滞状态,所以执行sleep()的线程在指定的时间内肯定不会执行;yield()只是使当前线程重新回到可执行状态,所以执行yield()的线程有可能在进入到可执行状态后马上又被执行。 sleep()可使优先级低的线程得到执行的机会,当然也可以让同优先级和高优先级的线程有执行的机会;yield()只能使同优先级的线程有执行的机会。 当调用wait()后,线程会释放掉它所占有的“锁标志”,从而使线程所在对象中的其它synchronized数据可被别的线程使用。 waite()和notify()因为会对对象的“锁标志”进行操作,所以它们必须在 synchronized函数或synchronized block中进行调用。如果在non-synchronized函数或non- synchronized block中进行调用,虽然能编译通过,但在运行时会发生IllegalMonitorStateException的异常。 彻底明白多线程通信机制: 线程间的通信 1. 线程的几种状态 线程有四种状态,任何一个线程肯定处于这四种状态中的一种: 1) 产生(New):线程对象已经产生,但尚未被启动,所以无法执行。如通过new产生了一个线程对象后没对它调用start()函数之前。 2) 可执行(Runnable):每个支持多线程的系统都有一个排程器,排程器会从线程池中选择一个线程并启动它。当一个线程处于可执行状态时,表示它可能正处于线程池中等待排排程器启动它;也可能它已正在执行。如执行了一个线程对象的start()方法后,线程就处于可执行状态,但显而易见的是此时线程不一定正在执行中。 3) 死亡(Dead):当一个线程正常结束,它便处于死亡状态。如一个线程的run()函数执行完毕后线程就进入死亡状态。 4) 停滞(Blocked):当一个线程处于停滞状态时,系统排程器就会忽略它,不对它进行排程。当处于停滞状态的线程重新回到可执行状态时,它有可能重新执行。如通过对一个线程调用wait()函数后,线程就进入停滞状态,只有当两次对该线程调用notify或notifyAll后它才能两次回到可执行状态。 2. class Thread下的常用函数函数 2.1 suspend()、resume() 1) 通过suspend()函数,可使线程进入停滞状态。通过suspend()使线程进入停滞状态后,除非收到resume()消息,否则该线程不会变回可执行状态。 2) 当调用suspend()函数后,线程不会释放它的“锁标志”。 例11: class TestThreadMethod extends Thread{ public static int shareVar = 0; public TestThreadMethod(String name){ super(name); } public synchronized void … Continue reading

全面分析Java的垃圾回收机制

全面分析Java的垃圾回收机制 2006-01-18 13:53 来源:博客园 作者:蒋涛 责任编辑:方舟·yesky 评论(0)   引言   Java的堆是一个运行时数据区,类的实例(对象)从中分配空间。Java虚拟机(JVM)的堆中储存着正在运行的应用程序所建立的所有对象,这些对象通过new、newarray、anewarray和multianewarray等指令建立,但是它们不需要程序代码来显式地释放。一般来说,堆的是由垃圾回收 来负责的,尽管JVM规范并不要求特殊的垃圾回收技术,甚至根本就不需要垃圾回收,但是由于内存的有限性,JVM在实现的时候都有一个由垃圾回收所管理的堆。垃圾回收是一种动态存储管理技术,它自动地释放不再被程序引用的对象,按照特定的垃圾收集算法来实现资源自动回收的功能。   垃圾收集的意义   在C++中,对象所占的内存在程序结束运行之前一直被占用,在明确释放之前不能分配给其它对象;而在Java中,当没有对象引用指向原先分配给某个对象的内存时,该内存便成为垃圾。JVM的一个系统级线程会自动释放该内存块。垃圾收集意味着程序不再需要的对象是”无用信息”,这些信息将被丢弃。当一个对象不再被引用的时候,内存回收它占领的空间,以便空间被后来的新对象使用。事实上,除了释放没用的对象,垃圾收集也可以清除内存记录碎片。由于创建对象和垃圾收集器释放丢弃对象所占的内存空间,内存会出现碎片。碎片是分配给对象的内存块之间的空闲内存洞。碎片整理将所占用的堆内存移到堆的一端,JVM将整理出的内存分配给新的对象。   垃圾收集能自动释放内存空间,减轻编程的负担。这使Java 虚拟机具有一些优点。首先,它能使编程效率提高。在没有垃圾收集机制的时候,可能要花许多时间来解决一个难懂的存储器问题。在用Java语言编程的时候,靠垃圾收集机制可大大缩短时间。其次是它保护程序的完整性, 垃圾收集是Java语言安全性策略的一个重要部份。   垃圾收集的一个潜在的缺点是它的开销影响程序性能。Java虚拟机必须追踪运行程序中有用的对象, 而且最终释放没用的对象。这一个过程需要花费处理器的时间。其次垃圾收集算法的不完备性,早先采用的某些垃圾收集算法就不能保证100%收集到所有的废弃内存。当然随着垃圾收集算法的不断改进以及软硬件运行效率的不断提升,这些问题都可以迎刃而解。   垃圾收集的算法分析   Java语言规范没有明确地说明JVM使用哪种垃圾回收算法,但是任何一种垃圾收集算法一般要做2件基本的事情:(1)发现无用信息对象;(2)回收被无用对象占用的内存空间,使该空间可被程序再次使用。   大多数垃圾回收算法使用了根集(root set)这个概念;所谓根集就量正在执行的Java程序可以访问的引用变量的集合(包括局部变量、参数、类变量),程序可以使用引用变量访问对象的属性和调用对象的方法。垃圾收集首选需要确定从根开始哪些是可达的和哪些是不可达的,从根集可达的对象都是活动对象,它们不能作为垃圾被回收,这也包括从根集间接可达的对象。而根集通过任意路径不可达的对象符合垃圾收集的条件,应该被回收。下面介绍几个常用的算法。   1、 引用计数法(Reference Counting Collector)   引用计数法是唯一没有使用根集的垃圾回收的法,该算法使用引用计数器来区分存活对象和不再使用的对象。一般来说,堆中的每个对象对应一个引用计数器。当每一次创建一个对象并赋给一个变量时,引用计数器置为1。当对象被赋给任意变量时,引用计数器每次加1当对象出了作用域后(该对象丢弃不再使用),引用计数器减1,一旦引用计数器为0,对象就满足了垃圾收集的条件。   基于引用计数器的垃圾收集器运行较快,不会长时间中断程序执行,适宜地必须 实时运行的程序。但引用计数器增加了程序执行的开销,因为每次对象赋给新的变量,计数器加1,而每次现有对象出了作用域生,计数器减1。   2、tracing算法(Tracing Collector)   tracing算法是为了解决引用计数法的问题而提出,它使用了根集的概念。基于tracing算法的垃圾收集器从根集开始扫描,识别出哪些对象可达,哪些对象不可达,并用某种方式标记可达对象,例如对每个可达对象设置一个或多个位。在扫描识别过程中,基于tracing算法的垃圾收集也称为标记和清除(mark-and-sweep)垃圾收集器.   3、compacting算法(Compacting Collector)   为了解决堆碎片问题,基于tracing的垃圾回收吸收了Compacting算法的思想,在清除的过程中,算法将所有的对象移到堆的一端,堆的另一端就变成了一个相邻的空闲内存区,收集器会对它移动的所有对象的所有引用进行更新,使得这些引用在新的位置能识别原来 的对象。在基于Compacting算法的收集器的实现中,一般增加句柄和句柄表。     4、copying算法(Coping Collector)   该算法的提出是为了克服句柄的开销和解决堆碎片的垃圾回收。它开始时把堆分成 一个对象 面和多个空闲面, 程序从对象面为对象分配空间,当对象满了,基于coping算法的垃圾 收集就从根集中扫描活动对象,并将每个 活动对象复制到空闲面(使得活动对象所占的内存之间没有空闲洞),这样空闲面变成了对象面,原来的对象面变成了空闲面,程序会在新的对象面中分配内存。   一种典型的基于coping算法的垃圾回收是stop-and-copy算法,它将堆分成对象面和空闲区域面,在对象面与空闲区域面的切换过程中,程序暂停执行。   5、generation算法(Generational Collector)   stop-and-copy垃圾收集器的一个缺陷是收集器必须复制所有的活动对象,这增加了程序等待时间,这是coping算法低效的原因。在程序设计中有这样的规律:多数对象存在的时间比较短,少数的存在时间比较长。因此,generation算法将堆分成两个或多个,每个子堆作为对象的一代(generation)。由于多数对象存在的时间比较短,随着程序丢弃不使用的对象,垃圾收集器将从最年轻的子堆中收集这些对象。在分代式的垃圾收集器运行后,上次运行存活下来的对象移到下一最高代的子堆中,由于老一代的子堆不会经常被回收,因而节省了时间。   6、adaptive算法(Adaptive Collector)   在特定的情况下,一些垃圾收集算法会优于其它算法。基于Adaptive算法的垃圾收集器就是监控当前堆的使用情况,并将选择适当算法的垃圾收集器。 透视Java垃圾回收   1、命令行参数透视垃圾收集器的运行   2、使用System.gc()可以不管JVM使用的是哪一种垃圾回收的算法,都可以请求Java的垃圾回收。在命令行中有一个参数-verbosegc可以查看Java使用的堆内存的情况,它的格式如下: java -verbosegc classfile   可以看个例子: class TestGC … Continue reading