導讀
本文是技術人面試系列實戰算法篇，面試中關于實戰算法都需要了解哪些内容？一文帶你詳細了解，歡迎收藏！
1、URL黑名單（布隆過濾器）
100億黑名單URL，每個64B，問這個黑名單要怎麼存？判斷一個URL是否在黑名單中
散清單：
如果把黑名單看成一個集合，将其存在hashmap中，貌似太大了，需要640G，明顯不科學。
布隆過濾器：
它實際上是一個很長的二進制矢量和一系列随機映射函數。
它可以用來判斷一個元素是否在一個集合中。它的優勢是隻需要占用很小的記憶體空間以及有着高效的查詢效率。對于布隆過濾器而言，它的本質是一個位數組：位數組就是數組的每個元素都隻占用1 bit，并且每個元素隻能是0或者1。
在數組中的每一位都是二進制位。布隆過濾器除了一個位數組，還有K個哈希函數。當一個元素加入布隆過濾器中的時候，會進行如下操作：
- 使用K個哈希函數對元素值進行K次計算，得到K個哈希值。
- 根據得到的哈希值，在位數組中把對應下标的值置為1。
2、詞頻統計（分檔案）
2GB記憶體在20億整數中找到出現次數最多的數
通常做法是使用哈希表對出現的每一個數做詞頻統計，哈希表的key是某個整數，value記錄整數出現的次數。本題的資料量是20億，有可能一個數出現20億次，則為了避免溢出，哈希表的key是32位（4B）,value也是32位（4B），那麼一條哈希表的記錄就需要占用8B。
當哈希表記錄數為2億個時，需要16億個位元組數（8*2億），需要至少1.6GB記憶體(16億/2^30,1GB==2^30個位元組==10億)。則20億個記錄，至少需要16GB的記憶體，不符合題目要求。
解決辦法是将20億個數的大檔案利用哈希函數分成16個小檔案，根據哈希函數可以把20億條資料均勻分布到16個檔案上，同一種數不可能被哈希函數分到不同的小檔案上，假設哈希函數夠好。然後對每一個小檔案用哈希函數來統計其中每種數出現的次數，這樣我們就得到16個檔案中出現次數最多的數，接着從16個數中選出次數最大的那個key即可。
3、未出現的數（bit數組）
40億個非負整數中找到沒有出現的數
對于原問題，如果使用哈希表來儲存出現過的數，那麼最壞情況下是40億個數都不相同，那麼哈希表則需要儲存40億條資料，一個32位整數需要4B，那麼40億*4B= 160億個位元組，一般大概10億個位元組的資料需要1G的空間，那麼大概需要16G的空間，這不符合要求。
我們換一種方式，申請一個bit數組，數組大小為4294967295，大概為40億bit，40億/8=5億位元組，那麼需要0.5G空間，bit數組的每個位置有兩種狀态0和1，那麼怎麼使用這個bit數組呢？呵呵，數組的長度剛好滿足我們整數的個數範圍，那麼數組的每個下标值對應4294967295中的一個數，逐個周遊40億個無符号數，例如，遇到20，則bitArray[20]=1；遇到666，則bitArray[666]=1,周遊完所有的數，将數組相應位置變為1。
40億個非負整數中找到一個沒有出現的數，記憶體限制10MB
10億個位元組的資料大概需要1GB空間處理，那麼10MB記憶體換算過來就是可以處理1千萬位元組的資料，也就是8千萬bit，對于40億非負整數如果申請bit數組的話，40億bit /0.8億bit=50，那麼這樣最少也得分50塊來處理，下面就以64塊來進行分析解答吧。
總結一下進階的解法：
1．根據10MB的記憶體限制，确定統計區間的大小，就是第二次周遊時的bitArr大小。
2．利用區間計數的方式，找到那個計數不足的區間，這個區間上肯定有沒出現的數。
3．對這個區間上的數做bit map映射，再周遊bit map，找到一個沒出現的數即可。
自己的想法
如果隻是找一個數，可以高位模運算，寫到64個不同的檔案，然後在最小的檔案中通過bitArray一次處理掉。
40億個無符号整數，1GB記憶體，找到所有出現兩次的數
對于原問題，可以用bit map的方式來表示數出現的情況。具體地說，是申請一個長度為4294967295×2的bit類型的數組bitArr，用2個位置表示一個數出現的詞頻，1B占用8個bit，是以長度為4294967295×2的bit類型的數組占用1GB空間。怎麼使用這個bitArr數組呢？周遊這40億個無符号數，如果初次遇到num，就把bitArr[num2+1]和bitArr[num2]設定為01，如果第二次遇到num，就把bitArr[num2+1]和bitArr[num2]設定為10，如果第三次遇到num，就把bitArr[num2+1]和bitArr[num2]設定為11。以後再遇到num，發現此時bitArr[num2+1]和bitArr[num2]已經被設定為11，就不再做任何設定。周遊完成後，再依次周遊bitArr，如果發現bitArr[i2+1]和bitArr[i2]設定為10，那麼i就是出現了兩次的數。
4、重複URL（分機器）
找到100億個URL中重複的URL
原問題的解法使用解決大資料問題的一種正常方法：把大檔案通過哈希函數配置設定到機器，或者通過哈希函數把大檔案拆成小檔案。一直進行這種劃分，直到劃分的結果滿足資源限制的要求。首先，你要向面試官詢問在資源上的限制有哪些，包括記憶體、計算時間等要求。在明确了限制要求之後，可以将每條URL通過哈希函數配置設定到若幹機器或者拆分成若幹小檔案，這裡的“若幹”由具體的資源限制來計算出精确的數量。
例如，将100億位元組的大檔案通過哈希函數配置設定到100台機器上，然後每一台機器分别統計分給自己的URL中是否有重複的URL，同時哈希函數的性質決定了同一條URL不可能分給不同的機器；或者在單機上将大檔案通過哈希函數拆成1000個小檔案，對每一個小檔案再利用哈希表周遊，找出重複的URL；或者在分給機器或拆完檔案之後，進行排序，排序過後再看是否有重複的URL出現。總之，牢記一點，很多大資料問題都離不開分流，要麼是哈希函數把大檔案的内容配置設定給不同的機器，要麼是哈希函數把大檔案拆成小檔案，然後處理每一個小數量的集合。
5、TOPK搜尋（小根堆）
海量搜尋詞彙，找到最熱TOP100詞彙的方法
最開始還是用哈希分流的思路來處理，把包含百億資料量的詞彙檔案分流到不同的機器上，具體多少台機器由面試官規定或者由更多的限制來決定。對每一台機器來說，如果分到的資料量依然很大，比如，記憶體不夠或其他問題，可以再用哈希函數把每台機器的分流檔案拆成更小的檔案處理。
處理每一個小檔案的時候，哈希表統計每種詞及其詞頻，哈希表記錄建立完成後，再周遊哈希表，周遊哈希表的過程中使用大小為100的小根堆來選出每一個小檔案的top100（整體未排序的top100）。每一個小檔案都有自己詞頻的小根堆（整體未排序的top100），将小根堆裡的詞按照詞頻排序，就得到了每個小檔案的排序後top100。然後把各個小檔案排序後的top100進行外排序或者繼續利用小根堆，就可以選出每台機器上的top100。不同機器之間的top100再進行外排序或者繼續利用小根堆，最終求出整個百億資料量中的top100。對于top K的問題，除哈希函數分流和用哈希表做詞頻統計之外，還經常用堆結構和外排序的手段進行處理。
6、中位數（單向二分查找）
10MB記憶體，找到100億整數的中位數
①記憶體夠：記憶體夠還慌什麼啊，直接把100億個全部排序了，你用冒泡都可以...然後找到中間那個就可以了。但是你以為面試官會給你記憶體？？
②記憶體不夠：題目說是整數，我們認為是帶符号的int,是以4位元組，占32位。
假設100億個數字儲存在一個大檔案中，依次讀一部分檔案到記憶體(不超過記憶體的限制)，将每個數字用二進制表示，比較二進制的最高位(第32位，符号位，0是正，1是負)，如果數字的最高位為0，則将這個數字寫入file_0檔案中；如果最高位為1，則将該數字寫入file_1檔案中。
進而将100億個數字分成了兩個檔案，假設file_0檔案中有60億個數字，file_1檔案中有40億個數字。那麼中位數就在file_0檔案中，并且是file_0檔案中所有數字排序之後的第10億個數字。（file_1中的數都是負數，file_0中的數都是正數，也即這裡一共隻有40億個負數，那麼排序之後的第50億個數一定位于file_0中）
現在，我們隻需要處理file_0檔案了（不需要再考慮file_1檔案）。對于file_0檔案，同樣采取上面的措施處理：将file_0檔案依次讀一部分到記憶體(不超記憶體限制)，将每個數字用二進制表示，比較二進制的次高位（第31位），如果數字的次高位為0，寫入file_0_0檔案中；如果次高位為1，寫入file_0_1檔案中。
現假設file_0_0檔案中有30億個數字，file_0_1中也有30億個數字，則中位數就是：file_0_0檔案中的數字從小到大排序之後的第10億個數字。
抛棄file_0_1檔案，繼續對file_0_0檔案根據次次高位(第30位)劃分，假設此次劃分的兩個檔案為：file_0_0_0中有5億個數字，file_0_0_1中有25億個數字，那麼中位數就是file_0_0_1檔案中的所有數字排序之後的 第5億個數。
按照上述思路，直到劃分的檔案可直接加載進記憶體時，就可以直接對數字進行快速排序，找出中位數了。
7、短域名系統（緩存）
設計短域名系統，将長URL轉化成短的URL.
（1）利用放号器，初始值為0，對于每一個短連結生成請求，都遞增放号器的值，再将此值轉換為62進制（a-zA-Z0-9），比如第一次請求時放号器的值為0，對應62進制為a，第二次請求時放号器的值為1，對應62進制為b，第10001次請求時放号器的值為10000，對應62進制為sBc。
（2）将短連結伺服器域名與放号器的62進制值進行字元串連接配接，即為短連結的URL，比如：t.cn/sBc。
（3）重定向過程：生成短連結之後，需要存儲短連結到長連結的映射關系，即sBc ->URL，浏覽器通路短連結伺服器時，根據URL Path取到原始的連結，然後進行302重定向。映射關系可使用K-V存儲，比如Redis或Memcache。
8、海量評論入庫（消息隊列）
假設有這麼一個場景，有一條新聞，新聞的評論量可能很大，如何設計評論的讀和寫
前端頁面直接給使用者展示、通過消息隊列異步方式入庫
讀可以進行讀寫分離、同時熱點評論定時加載到緩存
9、線上/并發使用者數（Redis）
顯示網站的使用者線上數的解決思路
維護線上使用者表
使用Redis統計
顯示網站并發使用者數
- 每當使用者通路服務時，把該使用者的ID寫入ZSORT隊列，權重為目前時間；
- 根據權重(即時間)計算一分鐘内該機構的使用者數Zrange；
- 删掉一分鐘以上過期的使用者Zrem；
10、熱門字元串（字首樹）
假設目前有1000w個記錄（這些查詢串的重複度比較高，雖然總數是1000w，但如果除去重複後，則不超過300w個）。請統計最熱門的10個查詢串，要求使用的記憶體不能超過1G。（一個查詢串的重複度越高，說明查詢它的使用者越多，也就越熱門。）
HashMap法
雖然字元串總數比較多，但去重後不超過300w，是以，可以考慮把所有字元串及出現次數儲存在一個HashMap中，所占用的空間為300w*(255+4)≈777M（其中，4 表示整數占用的4個位元組）。由此可見，1G的記憶體空間完全夠用。
思路如下：
首先，周遊字元串，若不在map中，直接存入map，value記為1；若在map中，則把對應的value加1，這一步時間複雜度O(N)。
接着周遊map，建構一個10個元素的小頂堆，若周遊到的字元串的出現次數大于堆頂字元串的出現次數，則進行替換，并将堆調整為小頂堆。
周遊結束後，堆中10個字元串就是出現次數最多的字元串。這一步時間複雜度O(Nlog10)。
字首樹法
當這些字元串有大量相同字首時，可以考慮使用字首樹來統計字元串出現的次數，樹的結點儲存字元串出現次數，0表示沒有出現。
思路如下：
在周遊字元串時，在字首樹中查找，如果找到，則把結點中儲存的字元串次數加1，否則為這個字元串建構新結點，建構完成後把葉子結點中字元串的出現次數置為1。
最後依然使用小頂堆來對字元串的出現次數進行排序。
11、紅包算法
線性切割法，一個區間切N-1刀。越早越多
二倍均值法，【0~剩餘金額 / 剩餘人數*2】中随機，相對均勻
12、手寫快排
public class QuickSort {
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
/* 正常快排 */
public static void quickSort1(int[] arr, int L , int R) {
if (L > R) return;
int M = partition(arr, L, R);
quickSort1(arr, L, M - 1);
quickSort1(arr, M + 1, R);
}
public static int partition(int[] arr, int L, int R) {
if (L > R) return -1;
if (L == R) return L;
int lessEqual = L - 1;
int index = L;
while (index < R) {
if (arr[index] <= arr[R])
swap(arr, index, ++lessEqual);
index++;
}
swap(arr, ++lessEqual, R);
return lessEqual;
}
/* 荷蘭國旗 */
public static void quickSort2(int[] arr, int L, int R) {
if (L > R) return;
int[] equalArea = netherlandsFlag(arr, L, R);
quickSort2(arr, L, equalArea[0] - 1);
quickSort2(arr, equalArea[1] + 1, R);
}
public static int[] netherlandsFlag(int[] arr, int L, int R) {
if (L > R) return new int[] { -1, -1 };
if (L == R) return new int[] { L, R };
int less = L - 1;
int more = R;
int index = L;
while (index < more) {
if (arr[index] == arr[R]) {
index++;
} else if (arr[index] < arr[R]) {
swap(arr, index++, ++less);
} else {
swap(arr, index, --more);
}
}
swap(arr, more, R);
return new int[] { less + 1, more };
}
// for test
public static void main(String[] args) {
int testTime = 1;
int maxSize = 10000000;
int maxValue = 100000;
boolean succeed = true;
long T1=0,T2=0;
for (int i = 0; i < testTime; i++) {
int[] arr1 = generateRandomArray(maxSize, maxValue);
int[] arr2 = copyArray(arr1);
int[] arr3 = copyArray(arr1);
// int[] arr1 = {9,8,7,6,5,4,3,2,1};
long t1 = System.currentTimeMillis();
quickSort1(arr1,0,arr1.length-1);
long t2 = System.currentTimeMillis();
quickSort2(arr2,0,arr2.length-1);
long t3 = System.currentTimeMillis();
T1 += (t2-t1);
T2 += (t3-t2);
if (!isEqual(arr1, arr2) || !isEqual(arr2, arr3)) {
succeed = false;
break;
}
}
System.out.println(T1+" "+T2);
// System.out.println(succeed ? "Nice!" : "Oops!");
}
private static int[] generateRandomArray(int maxSize, int maxValue) {
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) ((maxValue + 1) * Math.random())
- (int) (maxValue * Math.random());
}
return arr;
}
private static int[] copyArray(int[] arr) {
if (arr == null) return null;
int[] res = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
res[i] = arr[i];
}
return res;
}
private static boolean isEqual(int[] arr1, int[] arr2) {
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null))
return false;
if (arr1 == null && arr2 == null)
return true;
if (arr1.length != arr2.length)
return false;
for (int i = 0; i < arr1.length; i++)
if (arr1[i] != arr2[i])
return false;
return true;
}
private static void printArray(int[] arr) {
if (arr == null)
return;
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
} 13、手寫歸并
public static void merge(int[] arr, int L, int M, int R) {
int[] help = new int[R - L + 1];
int i = 0;
int p1 = L;
int p2 = M + 1;
while (p1 <= M && p2 <= R)
help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
while (p1 <= M)
help[i++] = arr[p1++];
while (p2 <= R)
help[i++] = arr[p2++];
for (i = 0; i < help.length; i++)
arr[L + i] = help[i];
}
public static void mergeSort(int[] arr, int L, int R) {
if (L == R)
return;
int mid = L + ((R - L) >> 1);
process(arr, L, mid);
process(arr, mid + 1, R);
merge(arr, L, mid, R);
}
public static void main(String[] args) {
int[] arr1 = {9,8,7,6,5,4,3,2,1};
mergeSort(arr, 0, arr.length - 1);
printArray(arr);
} 14、手寫堆排
// 堆排序額外空間複雜度O(1)
public static void heapSort(int[] arr) {
if (arr == null || arr.length < 2)
return;
for (int i = arr.length - 1; i >= 0; i--)
heapify(arr, i, arr.length);
int heapSize = arr.length;
swap(arr, 0, --heapSize);
// O(N*logN)
while (heapSize > 0) { // O(N)
heapify(arr, 0, heapSize); // O(logN)
swap(arr, 0, --heapSize); // O(1)
}
}
// arr[index]剛來的數，往上
public static void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
// arr[index]位置的數，能否往下移動
public static void heapify(int[] arr, int index, int heapSize) {
int left = index * 2 + 1; // 左孩子的下标
while (left < heapSize) { // 下方還有孩子的時候
// 兩個孩子中，誰的值大，把下标給largest
// 1）隻有左孩子，left -> largest
// 2) 同時有左孩子和右孩子，右孩子的值<= 左孩子的值，left -> largest
// 3) 同時有左孩子和右孩子并且右孩子的值> 左孩子的值， right -> largest
int largest = left+1 < heapSize && arr[left+1]> arr[left] ? left+1 : left;
// 父和較大的孩子之間，誰的值大，把下标給largest
largest = arr[largest] > arr[index] ? largest : index;
if (largest == index)
break;
swap(arr, largest, index);
index = largest;
left = index * 2 + 1;
}
}
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
public static void main(String[] args) {
int[] arr1 = {9,8,7,6,5,4,3,2,1};
heapSort(arr1);
printArray(arr1);
} 15、手寫單例
public class Singleton {
private volatile static Singleton singleton;
private Singleton() {}
public static Singleton getSingleton() {
if (singleton == null) {
synchronized (Singleton.class) {
if (singleton == null) {
singleton = new Singleton();
}
}
}
return singleton;
}
} 16、手寫LRUcache
// 基于linkedHashMap
public class LRUCache {
private LinkedHashMap<Integer,Integer> cache;
private int capacity; //容量大小
public LRUCache(int capacity) {
cache = new LinkedHashMap<>(capacity);
this.capacity = capacity;
}
public int get(int key) {
//緩存中不存在此key，直接傳回
if(!cache.containsKey(key)) {
return -1;
}
int res = cache.get(key);
cache.remove(key); //先從連結清單中删除
cache.put(key,res); //再把該節點放到連結清單末尾處
return res;
}
public void put(int key,int value) {
if(cache.containsKey(key)) {
cache.remove(key); //已經存在，在目前連結清單移除
}
if(capacity == cache.size()) {
//cache已滿，删除連結清單頭位置
Set<Integer> keySet = cache.keySet();
Iterator<Integer> iterator = keySet.iterator();
cache.remove(iterator.next());
}
cache.put(key,value); //插入到連結清單末尾
}
} //手寫雙向連結清單
class LRUCache {
class DNode {
DNode prev;
DNode next;
int val;
int key;
}
Map<Integer, DNode> map = new HashMap<>();
DNode head, tail;
int cap;
public LRUCache(int capacity) {
head = new DNode();
tail = new DNode();
head.next = tail;
tail.prev = head;
cap = capacity;
}
public int get(int key) {
if (map.containsKey(key)) {
DNode node = map.get(key);
removeNode(node);
addToHead(node);
return node.val;
} else {
return -1;
}
}
public void put(int key, int value) {
if (map.containsKey(key)) {
DNode node = map.get(key);
node.val = value;
removeNode(node);
addToHead(node);
} else {
DNode newNode = new DNode();
newNode.val = value;
newNode.key = key;
addToHead(newNode);
map.put(key, newNode);
if (map.size() > cap) {
map.remove(tail.prev.key);
removeNode(tail.prev);
}
}
}
public void removeNode(DNode node) {
DNode prevNode = node.prev;
DNode nextNode = node.next;
prevNode.next = nextNode;
nextNode.prev = prevNode;
}
public void addToHead(DNode node) {
DNode firstNode = head.next;
head.next = node;
node.prev = head;
node.next = firstNode;
firstNode.prev = node;
}
} 17、手寫線程池
package com.concurrent.pool;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
public class MySelfThreadPool {
//預設線程池中的線程的數量
private static final int WORK_NUM = 5;
//預設處理任務的數量
private static final int TASK_NUM = 100;
private int workNum;//線程數量
private int taskNum;//任務數量
private final Set<WorkThread> workThreads;//儲存線程的集合
private final BlockingQueue<Runnable> taskQueue;//阻塞有序隊列存放任務
public MySelfThreadPool() {
this(WORK_NUM, TASK_NUM);
}
public MySelfThreadPool(int workNum, int taskNum) {
if (workNum <= 0) workNum = WORK_NUM;
if (taskNum <= 0) taskNum = TASK_NUM;
taskQueue = new ArrayBlockingQueue<>(taskNum);
this.workNum = workNum;
this.taskNum = taskNum;
workThreads = new HashSet<>();
//啟動一定數量的線程數，從隊列中擷取任務處理
for (int i=0;i<workNum;i++) {
WorkThread workThread = new WorkThread("thead_"+i);
workThread.start();
workThreads.add(workThread);
}
}
public void execute(Runnable task) {
try {
taskQueue.put(task);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public void destroy() {
System.out.println("ready close thread pool...");
if (workThreads == null || workThreads.isEmpty()) return ;
for (WorkThread workThread : workThreads) {
workThread.stopWork();
workThread = null;//help gc
}
workThreads.clear();
}
private class WorkThread extends Thread{
public WorkThread(String name) {
super();
setName(name);
}
@Override
public void run() {
while (!interrupted()) {
try {
Runnable runnable = taskQueue.take();//擷取任務
if (runnable !=null) {
System.out.println(getName()+" readyexecute:"+runnable.toString());
runnable.run();//執行任務
}
runnable = null;//help gc
} catch (Exception e) {
interrupt();
e.printStackTrace();
}
}
}
public void stopWork() {
interrupt();
}
}
}
package com.concurrent.pool;
public class TestMySelfThreadPool {
private static final int TASK_NUM = 50;//任務的個數
public static void main(String[] args) {
MySelfThreadPool myPool = new MySelfThreadPool(3,50);
for (int i=0;i<TASK_NUM;i++) {
myPool.execute(new MyTask("task_"+i));
}
}
static class MyTask implements Runnable{
private String name;
public MyTask(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public void run() {
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("task :"+name+" end...");
}
@Override
public String toString() {
// TODO Auto-generated method stub
return "name = "+name;
}
}
} 18、手寫消費者生産者模式
public class Storage {
private static int MAX_VALUE = 100;
private List<Object> list = new ArrayList<>();
public void produce(int num) {
synchronized (list) {
while (list.size() + num > MAX_VALUE) {
System.out.println("暫時不能執行生産任務");
try {
list.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
for (int i = 0; i < num; i++) {
list.add(new Object());
}
System.out.println("已生産産品數"+num+" 倉庫容量"+list.size());
list.notifyAll();
}
}
public void consume(int num) {
synchronized (list) {
while (list.size() < num) {
System.out.println("暫時不能執行消費任務");
try {
list.wait();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
for (int i = 0; i < num; i++) {
list.remove(0);
}
System.out.println("已消費産品數"+num+" 倉庫容量" + list.size());
list.notifyAll();
}
}
}
public class Producer extends Thread {
private int num;
private Storage storage;
public Producer(Storage storage) {
this.storage = storage;
}
public void setNum(int num) {
this.num = num;
}
public void run() {
storage.produce(this.num);
}
}
public class Customer extends Thread {
private int num;
private Storage storage;
public Customer(Storage storage) {
this.storage = storage;
}
public void setNum(int num) {
this.num = num;
}
public void run() {
storage.consume(this.num);
}
}
public class Test {
public static void main(String[] args) {
Storage storage = new Storage();
Producer p1 = new Producer(storage);
Producer p2 = new Producer(storage);
Producer p3 = new Producer(storage);
Producer p4 = new Producer(storage);
Customer c1 = new Customer(storage);
Customer c2 = new Customer(storage);
Customer c3 = new Customer(storage);
p1.setNum(10);
p2.setNum(20);
p3.setNum(80);
c1.setNum(50);
c2.setNum(20);
c3.setNum(20);
c1.start();
c2.start();
c3.start();
p1.start();
p2.start();
p3.start();
}
} 19、手寫阻塞隊列
public class blockQueue {
private List<Integer> container = new ArrayList<>();
private volatile int size;
private volatile int capacity;
private Lock lock = new ReentrantLock();
private final Condition isNull = lock.newCondition();
private final Condition isFull = lock.newCondition();
blockQueue(int capacity) {
this.capacity = capacity;
}
public void add(int data) {
try {
lock.lock();
try {
while (size >= capacity) {
System.out.println("阻塞隊列滿了");
isFull.await();
}
} catch (Exception e) {
isFull.signal();
e.printStackTrace();
}
++size;
container.add(data);
isNull.signal();
} finally {
lock.unlock();
}
}
public int take() {
try {
lock.lock();
try {
while (size == 0) {
System.out.println("阻塞隊列空了");
isNull.await();
}
} catch (Exception e) {
isNull.signal();
e.printStackTrace();
}
--size;
int res = container.get(0);
container.remove(0);
isFull.signal();
return res;
} finally {
lock.unlock();
}
}
}
public static void main(String[] args) {
AxinBlockQueue queue = new AxinBlockQueue(5);
Thread t1 = new Thread(() -> {
for (int i = 0; i < 100; i++) {
queue.add(i);
System.out.println("塞入" + i);
try {
Thread.sleep(500);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
Thread t2 = new Thread(() -> {
for (; ; ) {
System.out.println("消費"+queue.take());
try {
Thread.sleep(800);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
});
t1.start();
t2.start();
} 20、手寫多線程交替列印ABC
package com.demo.test;
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.ReentrantLock;
public class syncPrinter implements Runnable{
// 列印次數
private static final int PRINT_COUNT = 10;
private final ReentrantLock reentrantLock;
private final Condition thisCondtion;
private final Condition nextCondtion;
private final char printChar;
public syncPrinter(ReentrantLock reentrantLock, Condition thisCondtion, Condition nextCondition, char printChar) {
this.reentrantLock = reentrantLock;
this.nextCondtion = nextCondition;
this.thisCondtion = thisCondtion;
this.printChar = printChar;
}
@Override
public void run() {
// 擷取列印鎖 進入臨界區
reentrantLock.lock();
try {
// 連續列印PRINT_COUNT次
for (int i = 0; i < PRINT_COUNT; i++) {
//列印字元
System.out.print(printChar);
// 使用nextCondition喚醒下一個線程
// 因為隻有一個線程在等待，是以signal或者signalAll都可以
nextCondtion.signal();
// 不是最後一次則通過thisCondtion等待被喚醒
// 必須要加判斷，不然雖然能夠列印10次，但10次後就會直接死鎖
if (i < PRINT_COUNT - 1) {
try {
// 本線程讓出鎖并等待喚醒
thisCondtion.await();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
} finally {
reentrantLock.unlock();
}
}
public static void main(String[] args) throws InterruptedException {
ReentrantLock lock = new ReentrantLock();
Condition conditionA = lock.newCondition();
Condition conditionB = lock.newCondition();
Condition conditionC = lock.newCondition();
Thread printA = new Thread(new syncPrinter(lock, conditionA, conditionB,'A'));
Thread printB = new Thread(new syncPrinter(lock, conditionB, conditionC,'B'));
Thread printC = new Thread(new syncPrinter(lock, conditionC, conditionA,'C'));
printA.start();
Thread.sleep(100);
printB.start();
Thread.sleep(100);
printC.start();
}
} 21、交替列印FooBar
//手太陰肺經 BLOCKING Queue
public class FooBar {
private int n;
private BlockingQueue<Integer> bar = new LinkedBlockingQueue<>(1);
private BlockingQueue<Integer> foo = new LinkedBlockingQueue<>(1);
public FooBar(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
foo.put(i);
printFoo.run();
bar.put(i);
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
bar.take();
printBar.run();
foo.take();
}
}
}
//手陽明大腸經CyclicBarrier 控制先後
class FooBar6 {
private int n;
public FooBar6(int n) {
this.n = n;
}
CyclicBarrier cb = new CyclicBarrier(2);
volatile boolean fin = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
while(!fin);
printFoo.run();
fin = false;
try {
cb.await();
} catch (BrokenBarrierException e) {}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
try {
cb.await();
} catch (BrokenBarrierException e) {}
printBar.run();
fin = true;
}
}
}
//手少陰心經 自旋 + 讓出CPU
class FooBar5 {
private int n;
public FooBar5(int n) {
this.n = n;
}
volatile boolean permitFoo = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; ) {
if(permitFoo) {
printFoo.run();
i++;
permitFoo = false;
}else{
Thread.yield();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; ) {
if(!permitFoo) {
printBar.run();
i++;
permitFoo = true;
}else{
Thread.yield();
}
}
}
}
//手少陽三焦經 可重入鎖 + Condition
class FooBar4 {
private int n;
public FooBar4(int n) {
this.n = n;
}
Lock lock = new ReentrantLock(true);
private final Condition foo = lock.newCondition();
volatile boolean flag = true;
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
lock.lock();
try {
while(!flag) {
foo.await();
}
printFoo.run();
flag = false;
foo.signal();
}finally {
lock.unlock();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n;i++) {
lock.lock();
try {
while(flag) {
foo.await();
}
printBar.run();
flag = true;
foo.signal();
}finally {
lock.unlock();
}
}
}
}
//手厥陰心包經 synchronized + 标志位 + 喚醒
class FooBar3 {
private int n;
// 标志位，控制執行順序，true執行printFoo，false執行printBar
private volatile boolean type = true;
private final Object foo= new Object(); // 鎖标志
public FooBar3(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (foo) {
while(!type){
foo.wait();
}
printFoo.run();
type = false;
foo.notifyAll();
}
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
synchronized (foo) {
while(type){
foo.wait();
}
printBar.run();
type = true;
foo.notifyAll();
}
}
}
}
//手太陽小腸經 信号量 适合控制順序
class FooBar2 {
private int n;
private Semaphore foo = new Semaphore(1);
private Semaphore bar = new Semaphore(0);
public FooBar2(int n) {
this.n = n;
}
public void foo(Runnable printFoo) throws InterruptedException {
for (int i = 0; i < n; i++) {
foo.acquire();
printFoo.run();
bar.release();
}
}
public void bar(Runnable printBar) throws InterruptedException {
for (int i = 0; i < n; i++) {
bar.acquire();
printBar.run();
foo.release();
}
}
} 作者:淘蘇
來源-微信公衆号:阿裡雲開發者
出處:https://mp.weixin.qq.com/s/IEzcsHn6SaoS96F1gTKcJQ