语源科技BlogJava-nod0620

java io以及unix io模型

nod0620 — Thu, 29 Sep 2011 05:15:00 GMT

摘要: IO分两个阶段： 1.通知内核准备数据。2.数据从内核缓冲区拷贝到应用缓冲区根据这2点IO类型可以分成： 1.阻塞IO，在两个阶段上面都是阻塞的。 2.非阻塞IO，在第1阶段，程序不断的轮询直到数据准备好，第2阶段还是阻塞的 3.IO复用，在第1阶段，当一个或者多个IO准备就绪时，通知程序，第2阶段还是阻塞的，在第1阶段还是轮询实现的，只是所有的IO都集中在一个地方，这个地方进... 阅读全文

nod0620 2011-09-29 13:15 发表评论

java 线程池

nod0620 — Tue, 20 Sep 2011 14:27:00 GMT

摘要: 图左边是线程池的类结构，右边是放入线程池执行的任务类结构ExecutorServiceExecutorService定义了线程池的基本的方法，AbstractExecutorService是个抽象类，实现了ExecutorService的部分，主要是实现了几个submit()方法，并且提供方法将提交进来的任务封装成FutureTask,ThreadPoolExecutor则实现线程池的管理Futu... 阅读全文

nod0620 2011-09-20 22:27 发表评论

java thread 之Lock

nod0620 — Sat, 17 Sep 2011 16:12:00 GMT

concurrent包里面有很多Lock的具体实现，其具体的实现都是基于AQS实现的

ReentrantLock
ReentrantLock是可重入的互斥锁，重点是重入和互斥，ReentrantLock 将由最近成功获得锁的线程所持有，当这个线程再次尝试拥有这个Lock时就是重入。互斥就是
在某一时间只有一个线程能持有Lock。
    public void lock() {
        sync.lock();
    }
获得锁方法，Sync是AQS的抽象子类，实现可重入和互斥的大部分功能。在Sync的子类中有FairSync和NonfairSync两种代表公平锁策略和非公平锁策略

Sync lock方法留给子类去实现，NonfairSync的实现：
        final void lock() {
            if (compareAndSetState(0, 1))
                setExclusiveOwnerThread(Thread.currentThread());
            else
                acquire(1);
        }
不管是不是有其他线程在AQS的阻塞的队列里面，如果当前线程能获得线程，就直接获得线程，不行的话执行AQS的acquire()方法，基本就是进入阻塞队列的命了。
关键点:AQS的acquire()中调用的tryAcquire(int arg)是留给子类实现的，是在进入阻塞队列前再尝试一次获取锁(lock()方法到这个点上面可能其他线程已经释放锁)

NonfairSync的tryAcquire(int arg)调用的nonfairTryAcquire()实现:
        final boolean nonfairTryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {//关键点1
                if (compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;//关键点2
                if (nextc < 0) // overflow
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
关键点1：state为0，没有线程请求锁，直接分配给本线程
关键点2. 如果本线程已经得到锁，state加1，即重入。

FairSync的实现:
    final void lock() {
            acquire(1);//关键点1
        }
    protected final boolean tryAcquire(int acquires) {
            final Thread current = Thread.currentThread();
            int c = getState();
            if (c == 0) {
                if (isFirst(current) && //关键点2
                    compareAndSetState(0, acquires)) {
                    setExclusiveOwnerThread(current);
                    return true;
                }
            }
            else if (current == getExclusiveOwnerThread()) {
                int nextc = c + acquires;
                if (nextc < 0)
                    throw new Error("Maximum lock count exceeded");
                setState(nextc);
                return true;
            }
            return false;
        }
关键点1：公平策略，没有给当前线程优惠
关键点2：判断当前线程有没有在阻塞队列的第一位，没在第一位不往下继续执行，这样先给阻塞队列的线程机会，这样做速度比较慢，吞吐量比较小

    public boolean tryLock() {
        return sync.nonfairTryAcquire(1);
    }
tryLock尝试获得锁，不能获得话就直接返回，没有公平策略一说。

unlock
    public void unlock() {
        sync.release(1);
    }

    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }
tryRelease()留给AQS子类执行：
        protected final boolean tryRelease(int releases) {
            int c = getState() - releases;
            if (Thread.currentThread() != getExclusiveOwnerThread())
                throw new IllegalMonitorStateException();
            boolean free = false;
            if (c == 0) {
                free = true;
                setExclusiveOwnerThread(null);
            }
            setState(c);
            return free;
        }
如果state被减后还不为0，表示这个锁被一个线程重入后还没有完全释放，release()方法后面不会执行，也就是不会执行unpark阻塞队列中的线程.

ReentrantReadWriteLock
ReentrantReadWriteLock内部有两个锁：互斥可重入的WriteLock和共享的ReadLock
内部实现中state字段的高16位代表的是read count，低16位代表的是write count
AQS的实现也有NonfairSync和FairSync之分：
主要区别是同时有读写线程时候对待读写线程策略不同。
NonfairSync:
final boolean writerShouldBlock(Thread current) {
            return false; // writers can always barge
        }
        final boolean readerShouldBlock(Thread current) {
            /* As a heuristic to avoid indefinite writer starvation,
             * block if the thread that momentarily appears to be head
             * of queue, if one exists, is a waiting writer. This is
             * only a probablistic effect since a new reader will not
             * block if there is a waiting writer behind other enabled
             * readers that have not yet drained from the queue.
             */
            return apparentlyFirstQueuedIsExclusive();
        }
write永远都不阻塞，read的话看阻塞队列header之后的node是不是write的，如果是就阻塞，可以避免read一直运行导致的write饥饿。
FairSync：
      final boolean writerShouldBlock(Thread current) {
            // only proceed if queue is empty or current thread at head
            return !isFirst(current);
        }
        final boolean readerShouldBlock(Thread current) {
            // only proceed if queue is empty or current thread at head
            return !isFirst(current);
        }
write和read都有判断是不是阻塞队列header后的第一个node。

对于ReadLock
     public void lock() {
            sync.acquireShared(1);
        }
调用AQS的acquireShared()，其中会执行留给AQS子类实现的tryAcquireShared():
protected final int tryAcquireShared(int unused) {
            /*
             * Walkthrough:
             * 1. If write lock held by another thread, fail
             * 2. If count saturated, throw error
             * 3. Otherwise, this thread is eligible for
             *    lock wrt state, so ask if it should block
             *    because of queue policy. If not, try
             *    to grant by CASing state and updating count.
             *    Note that step does not check for reentrant
             *    acquires, which is postponed to full version
             *    to avoid having to check hold count in
             *    the more typical non-reentrant case.
             * 4. If step 3 fails either because thread
             *    apparently not eligible or CAS fails,
             *    chain to version with full retry loop.
             */
            Thread current = Thread.currentThread();
            int c = getState();
            if (exclusiveCount(c) != 0 &&
                getExclusiveOwnerThread() != current)
                return -1;
            if (sharedCount(c) == MAX_COUNT)
                throw new Error("Maximum lock count exceeded");
            if (!readerShouldBlock(current) &&
                compareAndSetState(c, c + SHARED_UNIT)) {
                HoldCounter rh = cachedHoldCounter;
                if (rh == null || rh.tid != current.getId())
                    cachedHoldCounter = rh = readHolds.get();
                rh.count++;
                return 1;
            }
            return fullTryAcquireShared(current);
        }
策略是以下的几点：
1.如果当前write持有锁，直接返回-1.
2.没有write持有锁，判断是否需要阻塞读请求，之后原子更新read count
3.上面成功后就返回1，不成功的话在循环中试着读取：
     final int fullTryAcquireShared(Thread current) {
            /*
             * This code is in part redundant with that in
             * tryAcquireShared but is simpler overall by not
             * complicating tryAcquireShared with interactions between
             * retries and lazily reading hold counts.
             */
            HoldCounter rh = cachedHoldCounter;
            if (rh == null || rh.tid != current.getId())
                rh = readHolds.get();
            for (;;) {
                int c = getState();
                int w = exclusiveCount(c);
                if ((w != 0 && getExclusiveOwnerThread() != current) ||
                    ((rh.count | w) == 0 && readerShouldBlock(current)))
                    return -1;
                if (sharedCount(c) == MAX_COUNT)
                    throw new Error("Maximum lock count exceeded");
                if (compareAndSetState(c, c + SHARED_UNIT)) {
                    cachedHoldCounter = rh; // cache for release
                    rh.count++;
                    return 1;
                }
            }
        }
unLock方法就是将read count 减1，然后查看阻塞队列有没有线程需要unpark

WriteLock的实现和ReetrantLock的实现是一致的
Semaphore
Semaphore是信号量的概念，主要控制同一时间内对访问资源的线程数的控制。底层实现是AQS的
acquireShared()和releaseShared().

CountDownLatch
CountDownLatch在完成一组正在其他线程中执行的操作之前，允许线程等待直到他们完成操作
await()方法一直等到state=0，初始时CountDownLatch初始化state为传入的数值，一个线程
执行操作完成的话执行countDown()方法将state减1，直到为0，await()方法不再阻塞。

CyclicBarrier
当一组线程调用CyclicBarrier.await()方法，就会阻塞在那里，当最后一个线程进入调用此方法时，就执行
一个公共的Runnable.原理是：初始化时有count属性，当前面count-1个线程到来都condition.await()，第count个
线程来就执行公共Runnable，然后执行condition.signAll()方法来使得其他线程从阻塞中解脱出来.

nod0620 2011-09-18 00:12 发表评论

java thread 之AQS

nod0620 — Thu, 15 Sep 2011 14:57:00 GMT

摘要: JDK1.5引入了Doug Lea大神的concurrent框架，其中AbstractQueuedSynchronizer是concurrent框架的基本，从大神的paper中可以看到1.传统的synchronized不能进行中段，这个不合适2.如果将concurrent重心放在少数竞争下优化锁，而在其他情况下放任缓慢执行的策略是不正确的3.需要可预测的维护效率，即使在同步竞争激烈的情况下，理想中... 阅读全文

nod0620 2011-09-15 22:57 发表评论

java thread

nod0620 — Wed, 14 Sep 2011 08:53:00 GMT

线程状态
jdk中线程状态分为:new,runnable,blocked,waiting,timed_waiting,dead.其中new为刚创建还没有开始执行的状态，
而runnable状态分为可以执行和正在执行，可以执行是因为可能要等cpu时间片等。blocked状态是指线程在阻塞等待监视器的锁。waiting是指执行了Object.wait()，Thread.join()等方法进入waiting状态；timed_waiting是指带时间数的waiting状态，在时间到达之前都是在waiting状态，dead状态是指结束任务的线程状态，再也不能回到runnable状态了。

在线程中有waiting set和ready set概念。
当一个对象执行Object.wait()/Object.join()，该线程进入waiting set，同时需要释放监视器的锁。监视器也是一个普通对象，在加上一些关键语法后，就能成为监视器。
当一个对象执行Object.notify()时，是在waiting set选择一个thread进入ready set，当这个thread能获得这个监视器的锁时候，就可以进入runnable状态，否则就待在ready set，notifyAll()是通知waiting set里面的所有线程，然后选择其中的一个，不确定是哪一个，线程的优先级也只是一个提示和指导。
Object.wait(time)/Object.join(time)方法这些都是在时间限制到达之前thread在waiting set，时间到期之后自动进入ready set。
Thread.sleep()/Thread.yield()执行时thread都不会放弃监视器的锁，只是进入ready set，Thread.sleep()只是在指定的时间内休眠，得不到任何的资源.Thread.yield()只是提示thread工作差不多完成了，可以让步给其他Thread，这个让步不保证完成，这个也只对同等级的线程有效。

监视器
java使用监视器来表示同步锁，在Java里面，任何一个Object Reference都可以作为同步锁，只要使用synchronized：

public static final Object signal = new Object();
f1(){
synchronized(signal){

}
}

在jvm内部synchronized会被表示成monitorenter和monitorexit;在一个时间段，只有一个线程能持有monitor，也就是在monitorenter里面，也就达到了同步的目的.当想获得一个类变量锁的时候，可以使用这个类的class类。

内存模型
在jvm规范中规定java内存模型是java thread work memory和java main memory两部分
每个thread一个thread memory，初始为空，必要时和main memory通信

规范规定了工作内存和主内存之间通信的8个行为：use, assign, load, store,read,write, lock, and unlock
use:使用一个线程工作内存中的变量，看成线程的行为
assign:设置一个线程工作内存中的变量，设置的值来自线程执行引擎，看成线程的行为
read：把主内存的值读到线程工作内存当中，看成主内存的行为
load：在read之后执行，真正的把值读到到工作内存当中，看成线程的行为
store：保存工作内存的值，等下在执行write后传输给主内存，看成线程的行为

write：在store后执行，看成主内存的行为

lock和unlock是获取监视器锁和释放锁的行为，是第三方synchronized行为

这样的内存模型就会有问题：
线程工作内存是独立的，在工作内存A的变量被工作内存B看到需要经过A-->主内存-->B的程度，那么什么时候进行工作内存到主内存的通信呢？
这里需要涉及到缓存一致性模型，即工作内存(缓存)什么时候刷新和读取主内存必须遵循一定的规则才可以。
java使用释放一致性模型:在释放锁的时候写入主内存
也就是当synchronized表示的方法或者运行块执行结束时监视器锁释放后，里面涉及的所有变量(局部变量除外)的值都写入了主内存，当变量被其他线程看到的话，其值是最新的。
那么方法或运行块未进行同步，可能有两方面的问题:
1.方法的执行顺序是未定的
2.即使方法的执行顺序是相同的，由于工作内存的值未写到主内存中也有可能有问题

thread在jvm当中执行的顺序和代码中看到的顺序可能是不一样的，为了性能优化等代码可能进行重排序，所有jmm定义了
线程的执行顺序模型：happens-before模型，规则如下:
1.一个线程当中，先出现的指令happens-before后出现的指令
2.构造器的里面指令happens-before创建对象的指令
3.对于一个监视器，unlock happens-before 想去得锁的指令
4.对于volatile的变量，write happens-before read
5.A call to start() on a thread happens-before any actions in the started thread.
6.All actions in a thread happen-before any other thread successfully returns from a
join() on that thread.

happens-before模型保证了JMM内存模型的访问方式。
对于synchronized我们可以认为他符合了上面的第3点
对于volatile变量，保证了在线程每次修改后马上反映到主内存当中，也就是可见性。

1.All instance fields, static fields and array elements are stored in heap memory.存放在java堆内
2.

nod0620 2011-09-14 16:53 发表评论

linux纪录

nod0620 — Wed, 07 Sep 2011 09:46:00 GMT

1./proc下面提供很多关于系统的信息，很多内核信息可以在此文件夹下面看到
2.echo,显示文本行
3.whereis command 显示command在哪里，whatis command 显示command是什么
4.free显示内存信息
5.history 显示历史指令
6.locale 显示当前系统的语言设置
7.ps 显示进程消息。 ps aux | grep xxx
8.sysctl可以用来设置核心的参数，默认的文件是/etc/sysctl.conf
9.top显示进程消息，主要是查看系统的一些关键性能指标
10.vmstat显示虚拟内存统计信息
11.pgrep 查找符合条件的进程
12.exit 退出ssh或者终端
13.pidof 显示当前正在运行的程序的进程id
14.kill PID；pkill process_name；killall comm 杀死全部同名进程
15.symlinks 管理和维护符号链接
16.chkconfig 设置和检查系统的服务设置
17.查看所有的shell命令，可以进行修改
18.export 设置和显示环境变量
19.find 查找文件命令
20.wc统计文件的行数，字数，字节数，文件名
21.grep 正则表达式搜索 grep xxx 文件xxx；-i 忽略大小写；-数字显示匹配行的上下数字行；-b 在每行前显示字符偏移量 -n 显示行数
22.tar -cvf 压缩;tar -xvf 解压

linux监控：

http://agapple.iteye.com/blog/1156719
ps详解：
http://blog.chinaunix.net/space.php?uid=20053649&do=blog&id=161862
top详解：

http://bbs.linuxtone.org/thread-1684-1-1.html
mpstat

http://hi.baidu.com/kqzjhack/blog/item/20e1bb6744f9dd36aa184c44.html

http://www.ixpub.net/thread-645961-1-1.html

nod0620 2011-09-07 17:46 发表评论

hashcode

nod0620 — Wed, 07 Sep 2011 07:11:00 GMT

hashcode几点规定：

在 Java 应用程序执行期间，在对同一对象多次调用 hashCode 方法时，必须一致地返回相同的整数，前提是将对象进行 equals 比较时所用的信息没有被修改。
如果根据 equals(Object) 方法，两个对象是相等的，那么对这两个对象中的每个对象调用 hashCode 方法都必须生成相同的整数结果。
如果根据 equals(Object) 方法，两个对象不相等，那么对这两个对象中的任一对象上调用 hashCode 方法不要求一定生成不同的整数结果。

HashMap使用分离链接法，就是在hashcode冲突的时候在hashcode对应的槽位使用链表，查找的时候先hashcode找到槽位，然后equals()方法找到链表中对应的对象。
jdk的容量是2^n次，找到槽位使用位与的方式代替模的方式提高性能
装载因子是装载的对象和hash表总数量的比值，记为λ，这个代表平均链表的长度，在一次不成功要查找的平均节点为

λ,一次成功的查找则为1+λ/2

分离链接法之外还有线性探测法和平方探测法，双散列等探测法

探测法不是在冲突的时候利用链表进行存储，而是在冲突的位置往后查找一个空位置进行存储

线性探测法会遇到一次聚焦的问题，就是一个冲突的位置后面连续的位置都不为空

那么可以进行平方探测法消除一次聚焦的问题，虽然我们引进了二次聚焦的较小影响的问题，流行的函数为f(i)=i^2。

这个时候hash表的容量必须为素数，这样在表一半为空时，才能总数插入一个元素
如果容量为非素数的时候，备选位置要少很多

网上讨论hashmap的个数为素数或者2^n次问题，是没有分清分离链接法和探测法，只有在探测法的时候，素数才是最有效的

nod0620 2011-09-07 15:11 发表评论

项目小结

nod0620 — Wed, 31 Aug 2011 07:50:00 GMT

去年年底和今年上半年，做了一个类似微博的sns的项目—求购项目，有求购消息，评论消息和好友关系，也和项目组的同学一起讨论了项目的设计，不敢说架构，因为好多底层的存储，分库分表的功能我厂的其它团队已经完成。

表设计

1.求购消息主要是图片和文字的说明，这个其实可以看成是个微博每个用户发表feed的表，但有些不同，这个下文再说，这里我们叫photo表，下面所说的图片就是求购消息。
考虑到求购消息比较多，所以需要进行分表，假设分8个表。由于业务的需求是：可以查看单张图片，可以看一个用户的图片列表，问题来了，我们按什么进行分表？
看下表结构:

id是图片的id，要查询单张图片的话，需要能快速的定位到哪一张表，而查询一个用户的图片列表的话，需要快速找到这个用户所有的图片，那么这个用户的图片应该是放在
一个表里面的，即通过user_id能路由到一张表，从而从这张表里面取得这个用户所有的图片。通过上面分析：如果选择user_id对表数量取模的值为选择存储的第几个表，
那么一个user_id所有的图片都在一张表里面了，这里对id就有要求，id对表数量取模的值要和user_id对表数量取模的值一致。
这样做的结果是，id的值不是连续的，有些许的浪费，如果user_id分布不均的话，对于每个表的数据量也会分布不均

2.评论表
对图片进行评论，对于单个图片来说有评论列表，对于单个用户来说，他能看到所有对他图片进行评论的评论列表，所以采用了两套表的方案，对于用photo_id分表的
的comment表，以及针对user_id分表的comment_u表

3.好友关系表
这个类似于微薄里面的关注或者粉丝表,和评论表一样，这里需要两套表，一个是关注表，一个是粉丝表

Feed流

当一个人关注另外一个人的时候，那么被关注的人发表的图片是能被另外一个人看到的，这和微博的feed流是一样的。
这里有两种方式实现，push模式(推模式)，pull模式(拉模式)。push模式：当一个用户发表图片的时候，检索这个用户的
粉丝表，为每个粉丝插入一条feed。pull模式：当一个用户发表图片的时候，只是存一份数据，当一个用户查看他的关注的用户的feed的时候，需要先检索关注表，然后检索每一个关注用户有没有新发的feed。

push和pull模式各有利弊，当使用push模式的时候，如果一个用户(名人)的粉丝过多的话，那么每个粉丝插入一条feed对存储的压力就太大了(100000粉丝话，插入100000)，存储空间浪费也非常的严重。
pull模式的话，如果一个用户关注过多的时候，查询该用户的关注列表也是有很大的代价的

项目用的是pull模式，注意到求购项目的特殊性，一般只是看最新的求购的消息，假设某个用户当前有1000条新feed，这个用户也不能完全的看完，所以认为只要取得最新的消息里面的若干条，其余的消息的话可以在历史feed列表里面看到或者下一次看到，这里就有个timeline的概念。当次取得最新消息后，需要把这个时间点保存，下次查询的时候，从这个时间点进行查询。

项目具体的做法：
1.查询用户的关注列表
2.从cache中取出timeline
3.timeline为空的话，直接取出旧的feed 30条，更新timeline，其中最新的一条的创建时间为timeline
4.timeline不为空的话，取得timeline之后的feed，最大值为30条，查过30条，取得的是最旧的30条，更新timeline，其中最新的一条的创建时间为timeline。

第4步其实和微博的做法是不同的，假设有1000条feed，微博是一次性刷出来，而这个是一次刷出30条，这里有个博弈在里面：
一次刷新30条，刷新的次数多了，查询多了，但是一次1000条的单次查询压力大了，还有多少人看了30条之后继续刷新看的？所以我们采取降低单次刷新的代价，这样对服务器峰值的压力也就下来了

其它

还有很多优化的点没有说出来，比如路由表取模的时候，是用位与操作的(18%16==18&15)
还有各个能用到cache的地方尽量使用cache，对于读写的话，可以增加读写队列.
对于扩展，性能，后续考虑的：
当单个用户关注数超过一定数目，这个用户就需要特别的对待，比如用户关注单独的变成一张表，减少关注表的压力
对用户活跃度进行分析，活跃用户的feed使用pull和push模式相结合的模式
对于粉丝数很多的用户，可以单独成表，发的feed可以先push给一部分用户，让一部分用户先看到feed.

nod0620 2011-08-31 15:50 发表评论

二叉查找树复习简记

nod0620 — Mon, 29 Aug 2011 09:38:00 GMT

remove

remove分成三种情况，没有孩子节点的节点(即页子),单个孩子节点的节点，两个孩子节点的节点

1)页子节点可以直接删除

2)单个孩子节点的节点删除了，让其下的孩子节点直接和其父亲节点相连(就是孩子节点和祖父节点相连)

3)两个孩子节点的节点，为了保持排序状态，需要拿到这个节点的左子树的最大节点或者右子树的最小节点，得到这个节点的数据代替要删除的节点，

然后删除这个左子树的最大节点或者右子树的最小节点，因为左子树的最大节点没有右节点(有右节点的话，他就不是最大的了),同理，右子树的最小节点

没有左节点，所以要删除的这个节点只有一个或者没有孩子节点，只需要进行1)或者2)就完成了。

AVL树

在插入节点时通过旋转(rotation)解决问题:

  /**
     * 插入一个元素到树里面，可能破坏了高度差，需要找到一个节点a，该节点左子树和右子树被破坏了，则需要对这个节点(平衡因子)
     *
     * 树进行平衡，有四种情况:
     *
     * 1.a节点的左儿子的左子树插入
     *
     * 2.a节点的左儿子的右子树插入
     *
     * 3.a节点的右儿子的左子树插入
     *
     * 4.a节点的右儿子的右子树插入
     *
     *
     * 1.4两种情况需要进行一次旋转
     *
     * 2.3两种情况需要进行两次旋转
     *
     * 旋转的目的是为了使插入节点的树的高度降低1，所以只要求旋转平衡因子为根的树就可以了
    */

在删除节点的时候：

    /**
     * 删除一个节点，找到平衡因子，他的左子树高度和右子树高度如果相差2的话，就需要旋转，而且旋转后，平衡因子的节点为根的树的高度肯定会
     *
     * 下降1，这样平衡因子所在的树的高度下降1，也有可能需要进行旋转调整，这样调整一直到根节点
     *
     */

代码如下：

package struct;

/**
* @author chenxiaohui
* @version 创建时间：2011-8-26
*
*
*/
public class AvlTree {
    /**
     *
     * avl树:树中每个节点的左子树和右子树的高度最多差1的二叉查找树
     *
     *
     *
     */

    public int height(AvlNode node) {
        return node != null ? node.height : -1;
    }

    /**
     *
     *
     * 插入一个元素到树里面，可能破坏了高度差，需要找到一个节点a，该节点左子树和右子树被破坏了，则需要对这个节点(平衡因子)
     *
     * 树进行平衡，有四种情况:
     *
     * 1.a节点的左儿子的左子树插入
     *
     * 2.a节点的左儿子的右子树插入
     *
     * 3.a节点的右儿子的左子树插入
     *
     * 4.a节点的右儿子的右子树插入
     *
     *
     * 1.4两种情况需要进行一次旋转
     *
     * 2.3两种情况需要进行两次旋转
     *
     * @param t
     * @param tree
     * @return
     */

    public AvlNode insert(int t, AvlNode tree) {

        if (tree == null)
            return new AvlNode(t);

        int cmp = compare(t, tree.element);

        if (cmp < 0) {
            // 左子树
            tree.leftChild = insert(t, tree.leftChild);

            // 因为左子树插入了节点，那么左子树比右子树高,根据avl树的性质，插入了节点
            // 要么高度差为1，要么高度差为2，所以当相差为2时，需要进行树的调整
            if ((height(tree.leftChild) - height(tree.reightChild)) == 2) {

                // 当t比树左子树的元素还小的话，就是在树的左子树的左边插入节点，成为左子树的左子树，需要一次旋转
                if (compare(t, tree.leftChild.element) < 0) {

                    tree = rotateLeftChild(tree);
                } else {
                    // 当t比树左子树的元素还大的话，就是在树的左子树的右边插入节点，成为左子树的右子树，需要两次旋转
                    tree = doubleRotateLeftChild(tree);
                }
            }

        } else if (cmp > 0) {
            // 右子树
            tree.reightChild = insert(t, tree.reightChild);

            if ((height(tree.reightChild) - height(tree.leftChild)) == 2) {
                // 当t比树右子树的元素还大的话，就是在树的右子树的右边插入节点，成为右子树的右子树，需要一次旋转
                if (compare(t, tree.reightChild.element) > 0) {
                    tree = rotateRightChild(tree);
                } else {
                    // 当t比树右子树的元素还小的话，就是在树的右子树的左边插入节点，成为右子树的左子树，需要两次旋转
                    tree = doubleRotateRightChild(tree);
                }
            }

        } else {
            // 树里面有这个树

        }
        tree.height = Math
                .max(height(tree.leftChild), height(tree.reightChild)) + 1;
        return tree;

    }

    /**
     * 第1种情况需要进行顺时针旋转(右旋转)
     *
     * @param k2
     * @return
     */
    private AvlNode rotateLeftChild(AvlNode k2) {

        AvlNode k1 = k2.leftChild;

        k2.leftChild = k1.reightChild;
        k1.reightChild = k2;

        k2.height = Math.max(height(k2.leftChild), height(k2.reightChild)) + 1;
        k1.height = Math.max(height(k1.leftChild), height(k2)) + 1;
        return k1;

    }

    /**
     *
     * 第4种情况需要进行逆时针旋转(左旋转)
     *
     * @param k2
     * @return
     */
    private AvlNode rotateRightChild(AvlNode k2) {

        AvlNode k1 = k2.reightChild;

        k2.reightChild = k1.leftChild;
        k1.leftChild = k2;

        k2.height = Math.max(height(k2.leftChild), height(k2.reightChild)) + 1;
        k1.height = Math.max(height(k1.reightChild), height(k2)) + 1;
        return k1;

    }

    /**
     * 第2种情况需要进行(右-左旋转)
     *
     * @param k3
     * @return
     */
    private AvlNode doubleRotateLeftChild(AvlNode k3) {
        AvlNode k1 = k3.leftChild;
        k3.leftChild = rotateRightChild(k1);
        return rotateLeftChild(k3);
    }

    /**
     * 第3种情况需要进行(左-右旋转)
     *
     * @param k3
     * @return
     */

    private AvlNode doubleRotateRightChild(AvlNode k3) {
        AvlNode k1 = k3.reightChild;
        k3.reightChild = rotateLeftChild(k1);
        return rotateRightChild(k3);
    }

    public int compare(int a, int b) {
        return a - b;
    }

    static class AvlNode {

        private int element;
        private int height;
        private AvlNode leftChild;
        private AvlNode reightChild;

        AvlNode(int element) {
            this(element, null, null);
        }

        AvlNode(int element, AvlNode left, AvlNode right) {
            this.element = element;
            this.leftChild = left;
            this.reightChild = right;
        }

    }

    public void sysout(AvlNode node) {
        if (node != null) {

            AvlNode a = node.leftChild;
            sysout(a);
            for (int i = 0; i < node.height; i++) {
                System.out.print("     ");
            }
            System.out.print(node.element);
            System.out.print("\n");
            AvlNode b = node.reightChild;
            sysout(b);
        }
    }

    /**
     * 删除一个节点，找到平衡因子，他的左子树高度和右子树高度如果相差2的话，就需要旋转，而且旋转后，平衡因子的节点为根的树的高度肯定会
     *
     * 下降1，这样平衡因子所在的树的高度下降1，也有可能需要进行旋转调整，这样调整一直到根节点
     *
     * @param t
     * @param tree
     * @return
     */
    public AvlNode delete(int t, AvlNode tree) {

        if (tree == null)
            return null;

        int cmp = compare(t, tree.element);

        if (cmp < 0) {
            tree.leftChild = delete(t, tree.leftChild);

            if ((height(tree.reightChild) - height(tree.leftChild)) == 2) {
                if (tree.leftChild == null) {
                    tree = rotateRightChild(tree);
                } else {
                    tree = doubleRotateRightChild(tree);

                }

            }
        } else if (cmp > 0) {
            tree.reightChild = delete(t, tree.reightChild);

            if ((height(tree.leftChild) - height(tree.reightChild)) == 2) {
                if (tree.reightChild == null) {
                    tree = rotateLeftChild(tree);
                } else {
                    tree = doubleRotateLeftChild(tree);
                }
            }
        } else if (cmp == 0) {
            tree = null;
        }

        if (tree != null) {
            tree.height = Math.max(height(tree.leftChild),
                    height(tree.reightChild)) + 1;
        }
        return tree;

    }

    public static void main(String[] args) {
        AvlTree avlTree = new AvlTree();
        AvlNode node = new AvlNode(20);
        /*
         * Random random = new Random(); for (int i = 0; i < 10; i++) { int y =
         * random.nextInt(100) + 1; node = avlTree.insert(y, node); }
         */

        node = avlTree.insert(8, node);
        node = avlTree.insert(3, node);
        node = avlTree.insert(10, node);
        node = avlTree.insert(2, node);
        node = avlTree.insert(5, node);
        node = avlTree.insert(30, node);

        node = avlTree.insert(50, node);
        node = avlTree.insert(6, node);
        node = avlTree.insert(20, node);
        node = avlTree.insert(35, node);
        node = avlTree.insert(43, node);
        node = avlTree.insert(60, node);
        node = avlTree.insert(18, node);
        node = avlTree.insert(26, node);
        node = avlTree.insert(33, node);
        node = avlTree.insert(40, node);
        node = avlTree.insert(45, node);
        node = avlTree.insert(62, node);

        // avlTree.sysout(node);

        node = avlTree.delete(2, node);
        avlTree.sysout(node);

    }
}

nod0620 2011-08-29 17:38 发表评论

classloader记录

nod0620 — Wed, 24 Aug 2011 02:40:00 GMT

classloader是一个双亲委派模型的结构.

一般是如上图结构

Bootstrap ClassLoader/启动类加载器
他的parent为null, 主要负责'sun.boot.class.path'系统属性指定的或 -Xbootclasspath 选项指定的jar包装入工作.

Bootstrap ClassLoader是jvm控制的，不是java语言层面编写的，默认加载jdk_home/jre/lib/下面的jar包和其他相关的东西，如jdk的核心包rt.jar就是在这里被加载的

Extension ClassLoader/扩展类加载器
主要负责jdk_home/jre/lib/ext目录下('java.ext.dirs'系统属性指定)的jar包或 -Djava.ext.dirs 指定目录下的jar包装入工作,他的parent为 Bootstrap ClassLoader

System ClassLoader/系统类加载器
主要负责java -classpath/-Djava.class.path所指的目录下的类与jar包装入工作.一般我们会配置环境变量classpath，这个就是载入classpath指定的路径下jar和class,
平常我们指定一个"."号，就是指定从当前目录下开始搜索class类.parent为 Extension ClassLoader.

User Custom ClassLoader/用户自定义类加载器(java.lang.ClassLoader的子类)
在程序运行期间, 通过java.lang.ClassLoader的子类加载class文件.

classloader要加载class先从底向上传递给父亲加载类，最顶层的classloader如果能够加载就加载进来，不行的话，就自上而下传递，只到一个classloader能进行类的加载，
如果没有一个classloader能加载的话，就会抛出ClassNotFoundException或者NoClassDefFoundError异常，这个就是双亲委派模式

classloader这种模式保证了不同的classloader之间类不会相互的影响，那么也保证了好的类不会被恶意的类所破坏，这个也是jvm沙箱模式安全的一个保证

在不同classloader的同名的类实例不能互相沟通，类型转换，instanceof，如果这样做，则会抛出ClassCastException.所以抛出ClassCastException的原因不止和继承，实现有关系，
还和classloader有关系.

当运行时发现一个新class要load时，除代码已指定由哪classloader的实例load外，先由调用者的classloader所在的classloader tree去load，如果super类/interface类对于这个树是新的也一起会被load。这是caller classloader的概念.

双亲委派可以被打破，全权负责也可被打破，所以运行时决定类来自哪里，还是由classloader树和load class的代码是怎样而决定。

Thread Context ClassLoader：线程上下文classloader，是hold住了一ClassLoader的实例，这个holder在线程运行流程里可以到达隐式传递classloader。这个classloader是一个不会主动load的实例，就是说在这个线程运行下遇到新类这个classloader不会主动去load，只有自己用显式代码或你看不见的jar里用显式代码用这个

classloader loadClass()或Class.forName()，才会生效。因此，caller classloader和 thread context classloader，在执行到你的代码时，已定。并且执行流程的不同，到你代码时的入口也不同，被放置入thread的thread context classloader和Caller ClassLoader不一定一样，因此是不稳定的

需要稳定的话，就要保证在设计时就考虑到各种入口和用法的情况，然后得到确定的classloader存在 thread context classloader或者第三方的class loader中，tomcat的类加载体系就是这样做的.

nod0620 2011-08-24 10:40 发表评论