一直对多线程有恐惧，在实现共享锁和排它锁之后，感觉好了很多。
共享锁 就是查询的时候，如果没有修改，可以支持多线程查询；
排它锁 就是修改的时候，锁定共享锁，停止查询，同时，锁定排它锁，只允许一个线程进行修改，修改完成后，再解开共享锁；
心路历程： 一开始的想法是，绝对不调用 sleep ，要用到sleep 的地方我觉得都可以用 notify() 和 wait() 替换，sleep（T） 我觉得T 的大小压根是无法算出来的，如果非要用sleep 我觉得T 的时间应该是一个动态的值，这个值是通过函数的执行时间的一个平均值（每N次执行算一个 平均值出来） 但个人觉得还是不如notify() 和wait(); 我为了简单，操作的是一颗字典树代替B树；如何实现读支持多线程，写单线程呢！ 当各种查询和修改的操作以多线程的方式提交给线程池的时候，程序会从阻塞队列里面不断的取任务，当前面取到的任务是 查询的时候，不要管他，没有修改表结构，直接丢给一个线程，当取到的下任务是一个修改或者更新的任务时，首先必须等待前面的查询全部查询完，然后再停掉阻塞队列不断的添加任务， 要让我修改完成之后，再唤醒阻塞队列添加任务；由于我不知道如何停掉线程池的阻塞队列添加任务，所以干脆自己模拟线程池这个过程；（理论上这个方法是可行的） 主要的卡是在notify() 和 wait()的理解上面，这两个方法执行时都必须在 锁里面； 所以在查询的代码里面，你不能wait() 那样会变成单线程；
1 insert; 2 remove; 3 query; -1 stopRun
package com.trafree; import java.io.File;
import java.io.IOException;
import java.util.*;
import java.util.concurrent.atomic.AtomicInteger; /**
* Created by on_the_way on 2014/12/31.
*/
public class AboutThread { public static boolean insert(String str) {
int len = str.length();
Trie p = root;
for (int i = 0; i < len; i++) {
int num = str.charAt(i) - 'a';
if (p.next[num] == null) {
p.next[num] = new Trie();
}
p = p.next[num];
}
if (p.end) return false;
return p.end = true;
} public static boolean remove(String str) {
int len = str.length();
Trie p = root;
for (int i = 0; i < len; i++) {
int num = str.charAt(i) - 'a';
if (p.next[num] == null) {
return false;
}
p = p.next[num];
}
if (!p.end) {
return false;
}
p.end = false;
return true;
} public static boolean query(String str) {
int len = str.length();
Trie p = root;
for (int i = 0; i < len; i++) {
int num = str.charAt(i) - 'a';
if (p.next[num] == null) {
return false;
}
p = p.next[num];
}
return p.end;
} public static Trie root = new Trie(); public static class Trie {
public Trie next[] = new Trie[26];
public boolean end; public Trie() {
for (int i = 0; i < 26; i++) {
this.next[i] = null;
}
this.end = false;
}
} public static class Consumer implements Runnable {
public void run() {
try {
MyThread.process();
} catch (Exception e) {
e.printStackTrace();
}
}
} public static class MyThread implements Runnable { public int sequence;
public int action;
public String str;
public boolean res; public static Object lock1 = new Object();
public static Object lock2 = new Object();
public static Object lock3 = new Object(); public static boolean needNotify1 = false;
public static boolean needNotify2 = false;
public static boolean needNotify3 = false;
public static boolean runModify = false; public static AtomicInteger queryNum = new AtomicInteger(0);
public static Queue<MyThread> pool = new LinkedList<MyThread>(); public MyThread(int sequence, int action, String str) {
this.sequence = sequence;
this.action = action;
this.str = str;
this.res = false;
} public static void process() throws InterruptedException { boolean needBreak = false;
while (true) {
if( pool.size() == 0 && needBreak ){
break;
}
synchronized (lock1) {
if (pool.size() == 0) {
needNotify1 = true;
lock1.wait();
}
}
synchronized (lock3) {
if (runModify) {
needNotify3 = true;
lock3.wait();
}
}
MyThread myThread = pool.poll(); if (myThread.action == -1){
needBreak = true;continue;
}
if (myThread.action == 1 || myThread.action == 2) {
synchronized (lock2) {
if (queryNum.get() != 0) {
needNotify2 = true;
runModify = true;
lock2.wait();
new Thread(myThread).start();
} else {
runModify = true;
new Thread(myThread).start();
}
}
} else {
queryNum.incrementAndGet();
new Thread(myThread).start();
}
}
} public void run() {
if (this.action == 1) {
this.res = insert(this.str);
synchronized (lock3) {
needNotify1 = false;
runModify = false;
if( needNotify3 )lock3.notify();
}
System.out.println(sequence+" "+action+" "+str+" "+res);
} else if (this.action == 2) {
this.res = remove(this.str);
synchronized (lock3) {
needNotify1 = false;
runModify = false;
if( needNotify3 )lock3.notify();
}
System.out.println(sequence+" "+action+" " + str+" "+res);
} else {
this.res = query(str);
System.out.println(sequence+" "+action+" "+str+" "+res);
synchronized (lock2) {
if (queryNum.decrementAndGet() == 0 ) {
if(needNotify2)lock2.notify();
}
}
}
} } public static void main(String arg[]) throws IOException { File file = new File("F:" + File.separator + "in.txt");
Scanner cin = new Scanner(file);
int N = cin.nextInt();
int M = cin.nextInt(); for (int i = 0; i < N; i++) {
insert(cin.next());
} new Thread(new Consumer()).start();
for (int i = 0; i < M; i++) {
MyThread myThread = new MyThread(i, cin.nextInt(), cin.next());
synchronized (MyThread.lock1) {
MyThread.pool.add(myThread);
if (MyThread.needNotify1) {
MyThread.needNotify1 = false;
MyThread.lock1.notify();
}
}
}
}
}
40 45
what
make
you
so
beautiful
have
think
cell
green
red
java
hand
forum
discuss
online
contests
teaching
exercise
contest
recent
icpc
authors
ranklist
problem
achive
exams
university
judge
register
new
fortunately
old
behind
locked
the
feature
find
by
alphabet
more
3 what
3 more
3 old
3 find
3 exams
3 achive
3 icpc
3 recent
3 ranklist
2 ranklist
3 ranklist
1 ranklist
3 ranklist
3 find
3 alphabet
2 find
2 find
3 find
2 alphabet
1 alphabet
3 alphabet
3 find
1 find
3 find
3 what
3 more
3 old
3 find
3 exams
3 achive
3 icpc
3 recent
3 ranklist
3 ranklist
3 what
3 more
3 old
3 find
3 exams
3 achive
3 icpc
3 recent
3 ranklist
3 ranklist
-1 end