- 動(dòng)態(tài)規(guī)劃算法
一、基本概念
動(dòng)態(tài)規(guī)劃過(guò)程是：每次決策依賴(lài)于當(dāng)前狀態(tài)，又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來(lái)的，所以，這種多階段最優(yōu)化決策解決問(wèn)題的過(guò)程就稱(chēng)為動(dòng)態(tài)規(guī)劃。
二、基本思想與策略
基本思想與分治法類(lèi)似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他局部解。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。
由于動(dòng)態(tài)規(guī)劃解決的問(wèn)題多數(shù)有重疊子問(wèn)題這個(gè)特點(diǎn)，為減少重復(fù)計(jì)算，對(duì)每一個(gè)子問(wèn)題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。
與分治法最大的差別是：適合于用動(dòng)態(tài)規(guī)劃法求解的問(wèn)題，經(jīng)分解后得到的子問(wèn)題往往不是互相獨(dú)立的（即下一個(gè)子階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解）。
以上都過(guò)于理論，還是看看常見(jiàn)的動(dòng)態(tài)規(guī)劃問(wèn)題吧?。?！
三、常見(jiàn)動(dòng)態(tài)規(guī)劃問(wèn)題
1、找零錢(qián)問(wèn)題
有數(shù)組penny，penny中所有的值都為正數(shù)且不重復(fù)。每個(gè)值代表一種面值的貨幣，每種面值的貨幣可以使用任意張，再給定一個(gè)整數(shù)aim(小于等于1000)代表要找的錢(qián)數(shù)，求換錢(qián)有多少種方法。給定數(shù)組penny及它的大小(小于等于50)，同時(shí)給定一個(gè)整數(shù)aim，請(qǐng)返回有多少種方法可以湊成aim。測(cè)試樣例：[1,2,4],3,3返回：2
解析：設(shè)dp[n][m]為使用前n中貨幣湊成的m的種數(shù)，那么就會(huì)有兩種情況：
使用第n種貨幣：dp[n-1][m]+dp[n-1][m-peney[n]]
不用第n種貨幣：dp[n-1][m]，為什么不使用第n種貨幣呢，因?yàn)閜enney[n]>m。
這樣就可以求出當(dāng)m>=penney[n]時(shí) dp[n][m] = dp[n-1][m]+dp[n-1][m-peney[n]]，否則，dp[n][m] = dp[n-1][m]
代碼如下：
import java.util.*;
public class Exchange {
public int countWays(int[] penny, int n, int aim) {
// write code here
if(n==0||penny==null||aim<0){
return 0;
}
int[][] pd = new int[n][aim+1];
for(int i=0;i<n;i++){
pd[i][0] = 1;
}
for(int i=1;penny[0]*i<=aim;i++){
pd[0][penny[0]*i] = 1;
}
for(int i=1;i<n;i++){
for(int j=0;j<=aim;j++){
if(j>=penny[i]){
pd[i][j] = pd[i-1][j]+pd[i][j-penny[i]];
}else{
pd[i][j] = pd[i-1][j];
}
}
}
return pd[n-1][aim];
}
}
2、走方格問(wèn)題
有一個(gè)矩陣map，它每個(gè)格子有一個(gè)權(quán)值。從左上角的格子開(kāi)始每次只能向右或者向下走，最后到達(dá)右下角的位置，路徑上所有的數(shù)字累加起來(lái)就是路徑和，返回所有的路徑中最小的路徑和。給定一個(gè)矩陣map及它的行數(shù)n和列數(shù)m，請(qǐng)返回最小路徑和。保證行列數(shù)均小于等于100.測(cè)試樣例：[[1,2,3],[1,1,1]],2,3返回：4
解析：設(shè)dp[n][m]為走到n*m位置的路徑長(zhǎng)度，那么顯而易見(jiàn)dp[n][m] = min(dp[n-1][m],dp[n][m-1]);
代碼如下：
import java.util.*;
public class MinimumPath {
public int getMin(int[][] map, int n, int m) {
// write code here
int[][] dp = new int[n][m];
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
dp[i][0]+=map[j][0];
}
}
for(int i=0;i<m;i++){
for(int j=0;j<=i;j++){
dp[0][i]+=map[0][j];
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
dp[i][j] = min(dp[i][j-1]+map[i][j],dp[i-1][j]+map[i][j]);
}
}
return dp[n-1][m-1];
}
public int min(int a,int b){
if(a>b){
return b;
}else{
return a;
}
}
}
3、走臺(tái)階問(wèn)題
有n級(jí)臺(tái)階，一個(gè)人每次上一級(jí)或者兩級(jí)，問(wèn)有多少種走完n級(jí)臺(tái)階的方法。為了防止溢出，請(qǐng)將結(jié)果Mod 1000000007給定一個(gè)正整數(shù)int n，請(qǐng)返回一個(gè)數(shù)，代表上樓的方式數(shù)。保證n小于等于100000。測(cè)試樣例：1返回：1
解析：這是一個(gè)非常經(jīng)典的為題，設(shè)f(n)為上n級(jí)臺(tái)階的方法，要上到n級(jí)臺(tái)階的最后一步有兩種方式：從n-1級(jí)臺(tái)階走一步；從n-1級(jí)臺(tái)階走兩步，于是就有了這個(gè)公式f(n) = f(n-1)+f(n-2);
代碼如下：
import java.util.*;
public class GoUpstairs {
public int countWays(int n) {
// write code here
if(n<=2)
return n;
int f = 1%1000000007;
int s = 2%1000000007;
int t = 0;
for(int i=3;i<=n;i++){
t = (f+s)%1000000007;
f = s;
s = t;
}
return t;
}
}
4、最長(zhǎng)公共序列數(shù)
給定兩個(gè)字符串A和B，返回兩個(gè)字符串的最長(zhǎng)公共子序列的長(zhǎng)度。例如，A="1A2C3D4B56”，B="B1D23CA45B6A”，”123456"或者"12C4B6"都是最長(zhǎng)公共子序列。給定兩個(gè)字符串A和B，同時(shí)給定兩個(gè)串的長(zhǎng)度n和m，請(qǐng)返回最長(zhǎng)公共子序列的長(zhǎng)度。保證兩串長(zhǎng)度均小于等于300。測(cè)試樣例："1A2C3D4B56",10,"B1D23CA45B6A",12返回：6
解析：設(shè)dp[n][m] ，為A的前n個(gè)字符與B的前m個(gè)字符的公共序列長(zhǎng)度，則當(dāng)A[n]==B[m]的時(shí)候，dp[i][j] = max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1])，否則，dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
代碼如下：
import java.util.*;
public class LCS {
public int findLCS(String A, int n, String B, int m) {
// write code here
int[][] dp = new int[n][m];
char[] a = A.toCharArray();
char[] b = B.toCharArray();
for(int i=0;i<n;i++){
if(a[i]==b[0]){
dp[i][0] = 1;
for(int j=i+1;j<n;j++){
dp[j][0] = 1;
}
break;
}
}
for(int i=0;i<m;i++){
if(a[0]==b[i]){
dp[0][i] = 1;
for(int j=i+1;j<m;j++){
dp[0][j] = 1;
}
break;
}
}
for(int i=1;i<n;i++){
for(int j=1;j<m;j++){
if(a[i]==b[j]){
dp[i][j] = max(dp[i-1][j-1]+1,dp[i-1][j],dp[i][j-1]);
}else{
dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
}
}
}
return dp[n-1][m-1];
}
public int max(int a,int b,int c){
int max = a;
if(b>max)
max=b;
if(c>max)
max = c;
return max;
}
}
Java篇
- volatile關(guān)鍵字的作用
volatile這個(gè)關(guān)鍵字可能很多朋友都聽(tīng)說(shuō)過(guò)，或許也都用過(guò)。在Java 5之前，它是一個(gè)備受爭(zhēng)議的關(guān)鍵字，因?yàn)樵诔绦蛑惺褂盟鶗?huì)導(dǎo)致出人意料的結(jié)果。在Java 5之后，volatile關(guān)鍵字才得以重獲生機(jī)。
volatile 關(guān)鍵字作用是，使系統(tǒng)中所有線(xiàn)程對(duì)該關(guān)鍵字修飾的變量共享可見(jiàn)，可以禁止線(xiàn)程的工作內(nèi)存對(duì)volatile修飾的變量進(jìn)行緩存。
volatile 2個(gè)使用場(chǎng)景：
1.可見(jiàn)性:Java提供了volatile關(guān)鍵字來(lái)保證可見(jiàn)性。
當(dāng)一個(gè)共享變量被volatile修飾時(shí)，它會(huì)保證修改的值會(huì)立即被更新到主存，當(dāng)有其他線(xiàn)程需要讀取時(shí)，它會(huì)去內(nèi)存中讀取新值。
而普通的共享變量不能保證可見(jiàn)性，因?yàn)槠胀ü蚕碜兞勘恍薷闹?，什么時(shí)候被寫(xiě)入主存是不確定的，當(dāng)其他線(xiàn)程去讀取時(shí)，此時(shí)內(nèi)存中可能還是原來(lái)的舊值，因此無(wú)法保證可見(jiàn)性。
另外，通過(guò)synchronized和Lock也能夠保證可見(jiàn)性，synchronized和Lock能保證同一時(shí)刻只有一個(gè)線(xiàn)程獲取鎖然后執(zhí)行同步代碼，并且在釋放鎖之前會(huì)將對(duì)變量的修改刷新到主存當(dāng)中。因此可以保證可見(jiàn)性。
先看一段代碼，假如線(xiàn)程1先執(zhí)行，線(xiàn)程2后執(zhí)行：
//線(xiàn)程1
boolean stop = false;
while(!stop){
doSomething();
}
//線(xiàn)程2
stop = true;
這段代碼是很典型的一段代碼，很多人在中斷線(xiàn)程時(shí)可能都會(huì)采用這種標(biāo)記辦法。但是事實(shí)上，這段代碼會(huì)完全運(yùn)行正確么？即一定會(huì)將線(xiàn)程中斷么？不一定，也許在大多數(shù)時(shí)候，這個(gè)代碼能夠把線(xiàn)程中斷，但是也有可能會(huì)導(dǎo)致無(wú)法中斷線(xiàn)程（雖然這個(gè)可能性很小，但是只要一旦發(fā)生這種情況就會(huì)造成死循環(huán)了）。
下面解釋一下這段代碼為何有可能導(dǎo)致無(wú)法中斷線(xiàn)程。在前面已經(jīng)解釋過(guò)，每個(gè)線(xiàn)程在運(yùn)行過(guò)程中都有自己的工作內(nèi)存，那么線(xiàn)程1在運(yùn)行的時(shí)候，會(huì)將stop變量的值拷貝一份放在自己的工作內(nèi)存當(dāng)中。
那么當(dāng)線(xiàn)程2更改了stop變量的值之后，但是還沒(méi)來(lái)得及寫(xiě)入主存當(dāng)中，線(xiàn)程2轉(zhuǎn)去做其他事情了，那么線(xiàn)程1由于不知道線(xiàn)程2對(duì)stop變量的更改，因此還會(huì)一直循環(huán)下去。
但是用volatile修飾之后就變得不一樣了：
第一：使用volatile關(guān)鍵字會(huì)強(qiáng)制將修改的值立即寫(xiě)入主存；
第二：使用volatile關(guān)鍵字的話(huà)，當(dāng)線(xiàn)程2進(jìn)行修改時(shí)，會(huì)導(dǎo)致線(xiàn)程1的工作內(nèi)存中緩存變量stop的緩存行無(wú)效（反映到硬件層的話(huà)，就是CPU的L1或者L2緩存中對(duì)應(yīng)的緩存行無(wú)效）；
第三：由于線(xiàn)程1的工作內(nèi)存中緩存變量stop的緩存行無(wú)效，所以線(xiàn)程1再次讀取變量stop的值時(shí)會(huì)去主存讀取。
那么在線(xiàn)程2修改stop值時(shí)（當(dāng)然這里包括2個(gè)操作，修改線(xiàn)程2工作內(nèi)存中的值，然后將修改后的值寫(xiě)入內(nèi)存），會(huì)使得線(xiàn)程1的工作內(nèi)存中緩存變量stop的緩存行無(wú)效，然后線(xiàn)程1讀取時(shí)，發(fā)現(xiàn)自己的緩存行無(wú)效，它會(huì)等待緩存行對(duì)應(yīng)的主存地址被更新之后，然后去對(duì)應(yīng)的主存讀取最新的值。
那么線(xiàn)程1讀取到的就是最新的正確的值。
2.保證有序性
volatile boolean inited = false;
//線(xiàn)程1:
context = loadContext();
inited = true;
//線(xiàn)程2:
while(!inited ){
sleep()
}
doSomethingwithconfig(context);
確保context已經(jīng)初始化完成。
3.double check
class Singleton{
private volatile static Singleton instance = null;
private Singleton() {
}
public static Singleton getInstance() {
if(instance==null) {
synchronized (Singleton.class) {
if(instance==null)
instance = new Singleton();
}
}
return instance;
}
}
synchronize關(guān)鍵字的作用
Java 關(guān)鍵字volatile 與 synchronized 作用與區(qū)別
1，volatile
它所修飾的變量不保留拷貝，直接訪(fǎng)問(wèn)主內(nèi)存中的。
在Java內(nèi)存模型中，有main memory，每個(gè)線(xiàn)程也有自己的memory (例如寄存器)。為了性能，一個(gè)線(xiàn)程會(huì)在自己的memory中保持要訪(fǎng)問(wèn)的變量的副本。這樣就會(huì)出現(xiàn)同一個(gè)變 量在某個(gè)瞬間，在一個(gè)線(xiàn)程的memory中的值可能與另外一個(gè)線(xiàn)程memory中的值，或者main memory中的值不一致的情況。 一個(gè)變量聲明為volatile，就意味著這個(gè)變量是隨時(shí)會(huì)被其他線(xiàn)程修改的，因此不能將它c(diǎn)ache在線(xiàn)程memory中。
2，synchronized
當(dāng)它用來(lái)修飾一個(gè)方法或者一個(gè)代碼塊的時(shí)候，能夠保證在同一時(shí)刻最多只有一個(gè)線(xiàn)程執(zhí)行該段代碼。
一、當(dāng)兩個(gè)并發(fā)線(xiàn)程訪(fǎng)問(wèn)同一個(gè)對(duì)象object中的這個(gè)synchronized(this)同步代碼塊時(shí)，一個(gè)時(shí)間內(nèi)只能有一個(gè)線(xiàn)程得到執(zhí)行。另一個(gè)線(xiàn)程必須等待當(dāng)前線(xiàn)程執(zhí)行完這個(gè)代碼塊以后才能執(zhí)行該代碼塊。
二、然而，當(dāng)一個(gè)線(xiàn)程訪(fǎng)問(wèn)object的一個(gè)synchronized(this)同步代碼塊時(shí)，另一個(gè)線(xiàn)程仍然可以訪(fǎng)問(wèn)該object中的非synchronized(this)同步代碼塊。
三、尤其關(guān)鍵的是，當(dāng)一個(gè)線(xiàn)程訪(fǎng)問(wèn)object的一個(gè)synchronized(this)同步代碼塊時(shí)，其他線(xiàn)程對(duì)object中所有其它synchronized(this)同步代碼塊的訪(fǎng)問(wèn)將被阻塞。
四、當(dāng)一個(gè)線(xiàn)程訪(fǎng)問(wèn)object的一個(gè)synchronized(this)同步代碼塊時(shí)，它就獲得了這個(gè)object的對(duì)象鎖。結(jié)果，其它線(xiàn)程對(duì)該object對(duì)象所有同步代碼部分的訪(fǎng)問(wèn)都被暫時(shí)阻塞。
五、以上規(guī)則對(duì)其它對(duì)象鎖同樣適用.
區(qū)別：
一、volatile是變量修飾符，而synchronized則作用于一段代碼或方法。
二、volatile只是在線(xiàn)程內(nèi)存和“主”內(nèi)存間同步某個(gè)變量的值；而synchronized通過(guò)鎖定和解鎖某個(gè)監(jiān)視器同步所有變量的值。顯然synchronized要比volatile消耗更多資源。HashMap、HashTable、ConcurrentHashMap的區(qū)別
HashMap和HashTable的區(qū)別一種比較簡(jiǎn)單的回答是：
（1）HashMap是非線(xiàn)程安全的，HashTable是線(xiàn)程安全的。
（2）HashMap的鍵和值都允許有null存在，而HashTable則都不行。
（3）因?yàn)榫€(xiàn)程安全、哈希效率的問(wèn)題，HashMap效率比HashTable的要高。
但是如果繼續(xù)追問(wèn)：Java中的另一個(gè)線(xiàn)程安全的與HashMap功能極其類(lèi)似的類(lèi)是什么？
同樣是線(xiàn)程安全，它與HashTable在線(xiàn)程同步上有什么不同？帶著這些問(wèn)題，開(kāi)始今天的文章。
本文為原創(chuàng)，相關(guān)內(nèi)容會(huì)持續(xù)維護(hù)，轉(zhuǎn)載請(qǐng)標(biāo)明出處：http://blog.csdn.net/seu_calvin/article/details/52653711。
1． ****HashMap概述
Java中的數(shù)據(jù)存儲(chǔ)方式有兩種結(jié)構(gòu)，一種是數(shù)組，另一種就是鏈表，前者的特點(diǎn)是連續(xù)空間，尋址迅速，但是在增刪元素的時(shí)候會(huì)有較大幅度的移動(dòng)，所以數(shù)組的特點(diǎn)是查詢(xún)速度快，增刪較慢。
而鏈表由于空間不連續(xù)，尋址困難，增刪元素只需修改指針，所以鏈表的特點(diǎn)是查詢(xún)速度慢、增刪快。
那么有沒(méi)有一種數(shù)據(jù)結(jié)構(gòu)來(lái)綜合一下數(shù)組和鏈表以便發(fā)揮他們各自的優(yōu)勢(shì)？答案就是哈希表。哈希表的存儲(chǔ)結(jié)構(gòu)如下圖所示：
從上圖中，我們可以發(fā)現(xiàn)哈希表是由數(shù)組+鏈表組成的，一個(gè)長(zhǎng)度為16的數(shù)組中，每個(gè)元素存儲(chǔ)的是一個(gè)鏈表的頭結(jié)點(diǎn)，通過(guò)功能類(lèi)似于hash(key.hashCode())%len的操作，獲得要添加的元素所要存放的的數(shù)組位置。
HashMap的哈希算法實(shí)際操作是通過(guò)位運(yùn)算，比取模運(yùn)算效率更高，同樣能達(dá)到使其分布均勻的目的，后面會(huì)介紹。
鍵值對(duì)所存放的數(shù)據(jù)結(jié)構(gòu)其實(shí)是HashMap中定義的一個(gè)Entity內(nèi)部類(lèi)，數(shù)組來(lái)實(shí)現(xiàn)的，屬性有key、value和指向下一個(gè)Entity的next。
2． HashMap初始化
HashMap有兩種常用的構(gòu)造方法：
第一種是不需要參數(shù)的構(gòu)造方法：
static final int DEFAULT_INITIAL_CAPACITY = 16; //初始數(shù)組長(zhǎng)度為16
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量為2的30次方
//裝載因子用來(lái)衡量HashMap滿(mǎn)的程度
//計(jì)算HashMap的實(shí)時(shí)裝載因子的方法為：size/capacity
static final float DEFAULT_LOAD_FACTOR = 0.75f; //裝載因子
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
//默認(rèn)數(shù)組長(zhǎng)度為16
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
第二種是需要參數(shù)的構(gòu)造方法：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
// Find a power of 2 >= initialCapacity
int capacity = 1;
while (capacity < initialCapacity)
capacity <<= 1;
this.loadFactor = loadFactor;
threshold = (int)(capacity * loadFactor);
table = new Entry[capacity];
init();
}
從源碼可以看出，初始化的數(shù)組長(zhǎng)度為capacity，capacity的值總是2的N次方，大小比第一個(gè)參數(shù)稍大或相等。
- HashMap的put操作
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
3.1 put進(jìn)的key為null
從源碼中可以看出，HashMap是允許key為null的，會(huì)調(diào)用putForNullKey()方法：
private V putForNullKey(V value) {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(0, null, value, 0);
return null;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
if (size++ >= threshold)
resize(2 * table.length);
}
putForNullKey方法會(huì)遍歷以table[0]為鏈表頭的鏈表，如果存在key為null的KV，那么替換其value值并返回舊值。否則調(diào)用addEntry方法，這個(gè)方法也很簡(jiǎn)單，將[null,value]放在table[0]的位置，并將新加入的鍵值對(duì)封裝成一個(gè)Entity對(duì)象，將其next指向原table[0]處的Entity實(shí)例。
size表示HashMap中存放的所有鍵值對(duì)的數(shù)量。
threshold = capacity*loadFactor，最后幾行代碼表示當(dāng)HashMap的size大于threshold時(shí)會(huì)執(zhí)行resize操作，將HashMap擴(kuò)容為原來(lái)的2倍。擴(kuò)容需要重新計(jì)算每個(gè)元素在數(shù)組中的位置，indexFor()方法中的table.length參數(shù)也證明了這一點(diǎn)。
但是擴(kuò)容是一個(gè)非常消耗性能的操作，所以如果我們已經(jīng)預(yù)知HashMap中元素的個(gè)數(shù)，那么預(yù)設(shè)元素的個(gè)數(shù)能夠有效的提高HashMap的性能。比如說(shuō)我們有1000個(gè)元素，那么我們就該聲明new HashMap(2048)，因?yàn)樾枰紤]默認(rèn)的0.75的擴(kuò)容因子和數(shù)組數(shù)必須是2的N次方。若使用聲明new HashMap(1024)那么put過(guò)程中會(huì)進(jìn)行擴(kuò)容。
3.2 put進(jìn)的key不為null
將上述put方法中的相關(guān)代碼復(fù)制一下方便查看：
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
addEntry(hash, key, value, i);
return null;
}
從源碼可以看出，第1、2行計(jì)算將要put進(jìn)的鍵值對(duì)的數(shù)組的位置i。第4行判斷加入的key是否和以table[i]為鏈表頭的鏈表中所有的鍵值對(duì)有重復(fù)，若重復(fù)則替換value并返回舊值，若沒(méi)有重復(fù)則調(diào)用addEntry方法，上面對(duì)這個(gè)方法的邏輯已經(jīng)介紹過(guò)了。
至此HashMap的put操作已經(jīng)介紹完畢了。
- HashMap的get操作
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}
private V getForNullKey() {
for (Entry<K,V> e = table[0]; e != null; e = e.next) {
if (e.key == null)
return e.value;
}
return null;
}
如果了解了前面的put操作，那么這里的get操作邏輯就很容易理解了，源碼中的邏輯已經(jīng)非常非常清晰了。
需要注意的只有當(dāng)找不到對(duì)應(yīng)value時(shí)，返回的是null?；蛘遶alue本身就是null。這是可以通過(guò)containsKey()來(lái)具體判斷。
了解了上面HashMap的put和get操作原理，可以通過(guò)下面這個(gè)小例題進(jìn)行知識(shí)鞏固，題目是打印在數(shù)組中出現(xiàn)n/2以上的元素，我們便可以使用HashMap的特性來(lái)解決。
public class HashMapTest {
public static void main(String[] args) {
int [] a = {2,1,3,2,0,4,2,1,2,3,1,5,6,2,2,3};
Map<Integer, Integer> map = new HashMap<Integer,Integer>();
for(int i=0; i<a.length; i++){
if(map.containsKey(a[i])){
int tmp = map.get(a[i]);
tmp+=1;
map.put(a[i], tmp);
}else{
map.put(a[i], 1);
}
}
Set<Integer> set = map.keySet();
for (Integer s : set) {
if(map.get(s)>=a.length/2){
System.out.println(s);
}
}
}
}
5. ****HashMap和HashTable的對(duì)比
HashTable和HashMap采用相同的存儲(chǔ)機(jī)制，二者的實(shí)現(xiàn)基本一致，不同的是：
（1）HashMap是非線(xiàn)程安全的，HashTable是線(xiàn)程安全的，內(nèi)部的方法基本都經(jīng)過(guò)synchronized修飾。
（2）因?yàn)橥?、哈希性能等原因，性能肯定是HashMap更佳，因此HashTable已被淘汰。
（3） HashMap允許有null值的存在，而在HashTable中put進(jìn)的鍵值只要有一個(gè)null，直接拋出NullPointerException。
（4）HashMap默認(rèn)初始化數(shù)組的大小為16，HashTable為11。前者擴(kuò)容時(shí)乘2，使用位運(yùn)算取得哈希，效率高于取模。而后者為乘2加1，都是素?cái)?shù)和奇數(shù)，這樣取模哈希結(jié)果更均勻。
這里本來(lái)我沒(méi)有仔細(xì)看兩者的具體哈希算法過(guò)程，打算粗略比較一下區(qū)別就過(guò)的，但是最近師姐面試美團(tuán)移動(dòng)開(kāi)發(fā)時(shí)被問(wèn)到了稍微具體一些的算法過(guò)程，我也是醉了…不過(guò)還是恭喜師姐面試成功，起薪20W，真是羨慕，希望自己一年后找工作也能順順利利的。
言歸正傳，看下兩種集合的hash算法。看源碼也不難理解。
//HashMap的散列函數(shù)，這里傳入?yún)?shù)為鍵值對(duì)的key
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//返回hash值的索引，h & (length-1)操作等價(jià)于 hash % length操作， 但&操作性能更優(yōu)
static int indexFor(int h, int length) {
// length must be a non-zero power of 2
return h & (length-1);
}
//HashTable的散列函數(shù)直接在put方法里實(shí)現(xiàn)了
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
- HashTable和ConCurrentHashMap的對(duì)比
先對(duì)ConcurrentHashMap進(jìn)行一些介紹吧，它是線(xiàn)程安全的HashMap的實(shí)現(xiàn)。
HashTable里使用的是synchronized關(guān)鍵字，這其實(shí)是對(duì)對(duì)象加鎖，鎖住的都是對(duì)象整體，當(dāng)Hashtable的大小增加到一定的時(shí)候，性能會(huì)急劇下降，因?yàn)榈鷷r(shí)需要被鎖定很長(zhǎng)的時(shí)間。
ConcurrentHashMap算是對(duì)上述問(wèn)題的優(yōu)化，其構(gòu)造函數(shù)如下，默認(rèn)傳入的是16，0.75，16。
public ConcurrentHashMap(int paramInt1, float paramFloat, int paramInt2) {
//…
int i = 0;
int j = 1;
while (j < paramInt2) {
++i;
j <<= 1;
}
this.segmentShift = (32 - i);
this.segmentMask = (j - 1);
this.segments = Segment.newArray(j);
//…
int k = paramInt1 / j;
if (k * j < paramInt1)
++k;
int l = 1;
while (l < k)
l <<= 1;
for (int i1 = 0; i1 < this.segments.length; ++i1)
this.segments[i1] = new Segment(l, paramFloat);
}
public V put(K paramK, V paramV) {
if (paramV == null)
throw new NullPointerException();
int i = hash(paramK.hashCode()); //這里的hash函數(shù)和HashMap中的不一樣
return this.segments[(i >>> this.segmentShift & this.segmentMask)].put(paramK, i, paramV, false);
}
ConcurrentHashMap引入了分割(Segment)，上面代碼中的最后一行其實(shí)就可以理解為把一個(gè)大的Map拆分成N個(gè)小的HashTable，在put方法中，會(huì)根據(jù)hash(paramK.hashCode())來(lái)決定具體存放進(jìn)哪個(gè)Segment，如果查看Segment的put操作，我們會(huì)發(fā)現(xiàn)內(nèi)部使用的同步機(jī)制是基于lock操作的，這樣就可以對(duì)Map的一部分（Segment）進(jìn)行上鎖，這樣影響的只是將要放入同一個(gè)Segment的元素的put操作，保證同步的時(shí)候，鎖住的不是整個(gè)Map（HashTable就是這么做的），相對(duì)于HashTable提高了多線(xiàn)程環(huán)境下的性能，因此HashTable已經(jīng)被淘汰了。
- HashMap和ConCurrentHashMap的對(duì)比
最后對(duì)這倆兄弟做個(gè)區(qū)別總結(jié)吧：
（1）經(jīng)過(guò)4.2的分析，我們知道ConcurrentHashMap對(duì)整個(gè)桶數(shù)組進(jìn)行了分割分段(Segment)，然后在每一個(gè)分段上都用lock鎖進(jìn)行保護(hù)，相對(duì)于HashTable的syn關(guān)鍵字鎖的粒度更精細(xì)了一些，并發(fā)性能更好，而HashMap沒(méi)有鎖機(jī)制，不是線(xiàn)程安全的。
（2）HashMap的鍵值對(duì)允許有null，但是ConCurrentHashMap都不允許。
類(lèi)加載機(jī)制
類(lèi)裝載器就是尋找類(lèi)的字節(jié)碼文件，并構(gòu)造出類(lèi)在JVM內(nèi)部表示的對(duì)象組件。在Java中，類(lèi)裝載器把一個(gè)類(lèi)裝入JVM中，要經(jīng)過(guò)以下步驟：
(1) 裝載：查找和導(dǎo)入Class文件；
(2) 鏈接：把類(lèi)的二進(jìn)制數(shù)據(jù)合并到JRE中；
(a)校驗(yàn)：檢查載入Class文件數(shù)據(jù)的正確性；
(b)準(zhǔn)備：給類(lèi)的靜態(tài)變量分配存儲(chǔ)空間；
(c)解析：將符號(hào)引用轉(zhuǎn)成直接引用；
(3) 初始化：對(duì)類(lèi)的靜態(tài)變量，靜態(tài)代碼塊執(zhí)行初始化操作面向?qū)ο缶幊痰奶攸c(diǎn)
面向?qū)ο蟪绦蛟O(shè)計(jì)的基本特征有：
1，封裝性：封裝性是指將對(duì)象相關(guān)的信息和行為狀態(tài)捆綁成一個(gè)單元，即將對(duì)象封裝為一個(gè)具體的類(lèi)。封裝隱藏了對(duì)象的具體實(shí)現(xiàn)，當(dāng)要操縱對(duì)象時(shí)，只需調(diào)用其中的方法，而不用管方法的具體實(shí)現(xiàn)。
2，繼承性：一個(gè)類(lèi)繼承另一個(gè)類(lèi)，繼承者可以獲得被繼承類(lèi)的所有方法和屬性，并且可以根據(jù)實(shí)際的需要添加新的方法或者對(duì)被繼承類(lèi)中的方法進(jìn)行覆寫(xiě)，被繼承者稱(chēng)為父類(lèi)或者超類(lèi)，繼承者稱(chēng)為子類(lèi)或?qū)С鲱?lèi)，繼承提高了程序代碼的可重用性，Java中一個(gè)子類(lèi)只能繼承一個(gè)父類(lèi)，Object類(lèi)是所有類(lèi)的最終父類(lèi)。
3，多態(tài)性：多態(tài)性是指不同的對(duì)象對(duì)同一事物而做出的相同行為，一個(gè)類(lèi)A可以指向其自身類(lèi)和其導(dǎo)出類(lèi)，一個(gè)接口可以指向其接口實(shí)現(xiàn)類(lèi)，在方法參數(shù)中，使用多態(tài)可以提高參數(shù)的靈活性。Java虛擬機(jī)中的多態(tài)執(zhí)行機(jī)制
方法解析
Class文件的編譯過(guò)程中不包含傳統(tǒng)編譯中的連接步驟，一切方法調(diào)用在Class文件里面存儲(chǔ)的都只是符號(hào)引用，而不是方法在實(shí)際運(yùn)行時(shí)內(nèi)存布局中的入口地址。這個(gè)特性給Java帶來(lái)了更強(qiáng)大的動(dòng)態(tài)擴(kuò)展能力，使得可以在類(lèi)運(yùn)行期間才能確定某些目標(biāo)方法的直接引用，稱(chēng)為動(dòng)態(tài)連接，也有一部分方法的符號(hào)引用在類(lèi)加載階段或第一次使用時(shí)轉(zhuǎn)化為直接引用，這種轉(zhuǎn)化稱(chēng)為靜態(tài)解析。這在前面的“Java內(nèi)存區(qū)域與內(nèi)存溢出”一文中有提到。
靜態(tài)解析成立的前提是：方法在程序真正執(zhí)行前就有一個(gè)可確定的調(diào)用版本，并且這個(gè)方法的調(diào)用版本在運(yùn)行期是不可改變的。換句話(huà)說(shuō)，調(diào)用目標(biāo)在編譯器進(jìn)行編譯時(shí)就必須確定下來(lái)，這類(lèi)方法的調(diào)用稱(chēng)為解析。
在Java語(yǔ)言中，符合“編譯器可知，運(yùn)行期不可變”這個(gè)要求的方法主要有靜態(tài)方法和私有方法兩大類(lèi)，前者與類(lèi)型直接關(guān)聯(lián)，后者在外部不可被訪(fǎng)問(wèn)，這兩種方法都不可能通過(guò)繼承或別的方式重寫(xiě)出其他的版本，因此它們都適合在類(lèi)加載階段進(jìn)行解析。
Java虛擬機(jī)里共提供了四條方法調(diào)用字節(jié)指令，分別是：
invokestatic：調(diào)用靜態(tài)方法。
invokespecial：調(diào)用實(shí)例構(gòu)造器<init>方法、私有方法和父類(lèi)方法。
invokevirtual：調(diào)用所有的虛方法。
invokeinterface：調(diào)用接口方法，會(huì)在運(yùn)行時(shí)再確定一個(gè)實(shí)現(xiàn)此接口的對(duì)象。
只要能被invokestatic和invokespecial指令調(diào)用的方法，都可以在解析階段確定唯一的調(diào)用版本，符合這個(gè)條件的有靜態(tài)方法、私有方法、實(shí)例構(gòu)造器和父類(lèi)方法四類(lèi)，它們?cè)陬?lèi)加載時(shí)就會(huì)把符號(hào)引用解析為該方法的直接引用。這些方法可以稱(chēng)為非虛方法（還包括final方法），與之相反，其他方法就稱(chēng)為虛方法（final方法除外）。這里要特別說(shuō)明下final方法，雖然調(diào)用final方法使用的是invokevirtual指令，但是由于它無(wú)法覆蓋，沒(méi)有其他版本，所以也無(wú)需對(duì)方發(fā)接收者進(jìn)行多態(tài)選擇。Java語(yǔ)言規(guī)范中明確說(shuō)明了final方法是一種非虛方法。
解析調(diào)用一定是個(gè)靜態(tài)過(guò)程，在編譯期間就完全確定，在類(lèi)加載的解析階段就會(huì)把涉及的符號(hào)引用轉(zhuǎn)化為可確定的直接引用，不會(huì)延遲到運(yùn)行期再去完成。而分派調(diào)用則可能是靜態(tài)的也可能是動(dòng)態(tài)的，根據(jù)分派依據(jù)的宗量數(shù)（方法的調(diào)用者和方法的參數(shù)統(tǒng)稱(chēng)為方法的宗量）又可分為單分派和多分派。兩類(lèi)分派方式兩兩組合便構(gòu)成了靜態(tài)單分派、靜態(tài)多分派、動(dòng)態(tài)單分派、動(dòng)態(tài)多分派四種分派情況。
靜態(tài)分派
所有依賴(lài)靜態(tài)類(lèi)型來(lái)定位方法執(zhí)行版本的分派動(dòng)作，都稱(chēng)為靜態(tài)分派，靜態(tài)分派的最典型應(yīng)用就是多態(tài)性中的方法重載。靜態(tài)分派發(fā)生在編譯階段，因此確定靜態(tài)分配的動(dòng)作實(shí)際上不是由虛擬機(jī)來(lái)執(zhí)行的。下面通過(guò)一段方法重載的示例程序來(lái)更清晰地說(shuō)明這種分派機(jī)制：
class Human{
}
class Man extends Human{
}
class Woman extends Human{
}
public class StaticPai{
public void say(Human hum){
System.out.println("I am human");
}
public void say(Man hum){
System.out.println("I am man");
}
public void say(Woman hum){
System.out.println("I am woman");
}
public static void main(String[] args){
Human man = new Man();
Human woman = new Woman();
StaticPai sp = new StaticPai();
sp.say(man);
sp.say(woman);
}
}
上面代碼的執(zhí)行結(jié)果如下：
I am human I am human
以上結(jié)果的得出應(yīng)該不難分析。在分析為什么會(huì)選擇參數(shù)類(lèi)型為Human的重載方法去執(zhí)行之前，先看如下代碼：
Human man = new Man（）;
我們把上面代碼中的“Human”稱(chēng)為變量的靜態(tài)類(lèi)型，后面的“Man”稱(chēng)為變量的實(shí)際類(lèi)型。靜態(tài)類(lèi)型和實(shí)際類(lèi)型在程序中都可以發(fā)生一些變化，區(qū)別是靜態(tài)類(lèi)型的變化僅僅在使用時(shí)發(fā)生，變量本身的靜態(tài)類(lèi)型不會(huì)被改變，并且最終的靜態(tài)類(lèi)型是在編譯期可知的，而實(shí)際類(lèi)型變化的結(jié)果在運(yùn)行期才可確定。
回到上面的代碼分析中，在調(diào)用say（）方法時(shí)，方法的調(diào)用者（回憶上面關(guān)于宗量的定義，方法的調(diào)用者屬于宗量）都為sp的前提下，使用哪個(gè)重載版本，完全取決于傳入?yún)?shù)的數(shù)量和數(shù)據(jù)類(lèi)型（方法的參數(shù)也是數(shù)據(jù)宗量）。代碼中刻意定義了兩個(gè)靜態(tài)類(lèi)型相同、實(shí)際類(lèi)型不同的變量，可見(jiàn)編譯器（不是虛擬機(jī)，因?yàn)槿绻歉鶕?jù)靜態(tài)類(lèi)型做出的判斷，那么在編譯期就確定了）在重載時(shí)是通過(guò)參數(shù)的靜態(tài)類(lèi)型而不是實(shí)際類(lèi)型作為判定依據(jù)的。并且靜態(tài)類(lèi)型是編譯期可知的，所以在編譯階段，Javac編譯器就根據(jù)參數(shù)的靜態(tài)類(lèi)型決定使用哪個(gè)重載版本。這就是靜態(tài)分派最典型的應(yīng)用。
動(dòng)態(tài)分派
動(dòng)態(tài)分派與多態(tài)性的另一個(gè)重要體現(xiàn)——方法覆寫(xiě)有著很緊密的關(guān)系。向上轉(zhuǎn)型后調(diào)用子類(lèi)覆寫(xiě)的方法便是一個(gè)很好地說(shuō)明動(dòng)態(tài)分派的例子。這種情況很常見(jiàn)，因此這里不再用示例程序進(jìn)行分析。很顯然，在判斷執(zhí)行父類(lèi)中的方法還是子類(lèi)中覆蓋的方法時(shí)，如果用靜態(tài)類(lèi)型來(lái)判斷，那么無(wú)論怎么進(jìn)行向上轉(zhuǎn)型，都只會(huì)調(diào)用父類(lèi)中的方法，但實(shí)際情況是，根據(jù)對(duì)父類(lèi)實(shí)例化的子類(lèi)的不同，調(diào)用的是不同子類(lèi)中覆寫(xiě)的方法，很明顯，這里是要根據(jù)變量的實(shí)際類(lèi)型來(lái)分派方法的執(zhí)行版本的。而實(shí)際類(lèi)型的確定需要在程序運(yùn)行時(shí)才能確定下來(lái)，這種在運(yùn)行期根據(jù)實(shí)際類(lèi)型確定方法執(zhí)行版本的分派過(guò)程稱(chēng)為動(dòng)態(tài)分派。
單分派和多分派
前面給出：方法的接受者（亦即方法的調(diào)用者）與方法的參數(shù)統(tǒng)稱(chēng)為方法的宗量。但分派是根據(jù)一個(gè)宗量對(duì)目標(biāo)方法進(jìn)行選擇，多分派是根據(jù)多于一個(gè)宗量對(duì)目標(biāo)方法進(jìn)行選擇。
為了方便理解，下面給出一段示例代碼：
class Eat{
}
class Drink{
}
class Father{
public void doSomething(Eat arg){
System.out.println("爸爸在吃飯");
}
public void doSomething(Drink arg){
System.out.println("爸爸在喝水");
}
}
class Child extends Father{
public void doSomething(Eat arg){
System.out.println("兒子在吃飯");
}
public void doSomething(Drink arg){
System.out.println("兒子在喝水");
}
}
public class SingleDoublePai{
public static void main(String[] args){
Father father = new Father();
Father child = new Child();
father.doSomething(new Eat());
child.doSomething(new Drink());
}
}
運(yùn)行結(jié)果應(yīng)該很容易預(yù)測(cè)到，如下：
爸爸在吃飯
兒子在喝水
我們首先來(lái)看編譯階段編譯器的選擇過(guò)程，即靜態(tài)分派過(guò)程。這時(shí)候選擇目標(biāo)方法的依據(jù)有兩點(diǎn)：一是方法的接受者（即調(diào)用者）的靜態(tài)類(lèi)型是Father還是Child，二是方法參數(shù)類(lèi)型是Eat還是Drink。因?yàn)槭歉鶕?jù)兩個(gè)宗量進(jìn)行選擇，所以Java語(yǔ)言的靜態(tài)分派屬于多分派類(lèi)型。
再來(lái)看運(yùn)行階段虛擬機(jī)的選擇，即動(dòng)態(tài)分派過(guò)程。由于編譯期已經(jīng)了確定了目標(biāo)方法的參數(shù)類(lèi)型（編譯期根據(jù)參數(shù)的靜態(tài)類(lèi)型進(jìn)行靜態(tài)分派），因此唯一可以影響到虛擬機(jī)選擇的因素只有此方法的接受者的實(shí)際類(lèi)型是Father還是Child。因?yàn)橹挥幸粋€(gè)宗量作為選擇依據(jù)，所以Java語(yǔ)言的動(dòng)態(tài)分派屬于單分派類(lèi)型。
根據(jù)以上論證，我們可以總結(jié)如下：目前的Java語(yǔ)言（JDK1.6）是一門(mén)靜態(tài)多分派、動(dòng)態(tài)單分派的語(yǔ)言。
- 單例模式的優(yōu)缺點(diǎn)
1、優(yōu)點(diǎn)
提供了對(duì)唯一實(shí)例的受控訪(fǎng)問(wèn)。因?yàn)閱卫?lèi)封裝了它的唯一實(shí)例，所以它可以嚴(yán)格控制客戶(hù)怎樣以及何時(shí)訪(fǎng)問(wèn)它，并為設(shè)計(jì)及開(kāi)發(fā)團(tuán)隊(duì)提供了共享的概念。
由于在系統(tǒng)內(nèi)存中只存在一個(gè)對(duì)象，因此可以節(jié)約系統(tǒng)資源，對(duì)于一些需要頻繁創(chuàng)建和銷(xiāo)毀的對(duì)象，單例模式無(wú)疑可以提高系統(tǒng)的性能。
允許可變數(shù)目的實(shí)例。我們可以基于單例模式進(jìn)行擴(kuò)展，使用與單例控制相似的方法來(lái)獲得指定個(gè)數(shù)的對(duì)象實(shí)例。
2、缺點(diǎn)
由于單例模式中沒(méi)有抽象層，因此單例類(lèi)的擴(kuò)展有很大的困難。
單例類(lèi)的職責(zé)過(guò)重，在一定程度上違背了“單一職責(zé)原則”。因?yàn)閱卫?lèi)既充當(dāng)了工廠(chǎng)角色，提供了工廠(chǎng)方法，同時(shí)又充當(dāng)了產(chǎn)品角色，包含一些業(yè)務(wù)方法，將產(chǎn)品的創(chuàng)建和產(chǎn)品的本身的功能融合到一起。
濫用單例將帶來(lái)一些負(fù)面問(wèn)題，如為了節(jié)省資源將數(shù)據(jù)庫(kù)連接池對(duì)象設(shè)計(jì)為單例類(lèi)，可能會(huì)導(dǎo)致共享連接池對(duì)象的程序過(guò)多而出現(xiàn)連接池溢出；現(xiàn)在很多面向?qū)ο笳Z(yǔ)言(如Java、C#)的運(yùn)行環(huán)境都提供了自動(dòng)垃圾回收的技術(shù)，因此，如果實(shí)例化的對(duì)象長(zhǎng)時(shí)間不被利用，系統(tǒng)會(huì)認(rèn)為它是垃圾，會(huì)自動(dòng)銷(xiāo)毀并回收資源，下次利用時(shí)又將重新實(shí)例化，這將導(dǎo)致對(duì)象狀態(tài)的丟失。
Android篇
- Service和IntentService的區(qū)別
Android中的Service是用于后臺(tái)服務(wù)的，當(dāng)應(yīng)用程序被掛到后臺(tái)的時(shí)候，問(wèn)了保證應(yīng)用某些組件仍然可以工作而引入了Service這個(gè)概念，那么這里面要強(qiáng)調(diào)的是Service不是獨(dú)立的進(jìn)程，也不是獨(dú)立的線(xiàn)程，它是依賴(lài)于應(yīng)用程序的主線(xiàn)程的，也就是說(shuō)，在更多時(shí)候不建議在Service中編寫(xiě)耗時(shí)的邏輯和操作，否則會(huì)引起ANR。
那么我們當(dāng)我們編寫(xiě)的耗時(shí)邏輯，不得不被service來(lái)管理的時(shí)候，就需要引入IntentService，IntentService是繼承Service的，那么它包含了Service的全部特性，當(dāng)然也包含service的生命周期，那么與service不同的是，IntentService在執(zhí)行onCreate操作的時(shí)候，內(nèi)部開(kāi)了一個(gè)線(xiàn)程，去你執(zhí)行你的耗時(shí)操作。
這里我 需要解釋以下幾個(gè)方法，也許大家都已經(jīng)很清楚了，不過(guò)為了拋磚引玉，我還是要提一嘴。
Service中提供了一個(gè)方法：
public int onStartCommand(Intent intent, int flags, int startId) {
onStart(intent, startId);
return mStartCompatibility ? START_STICKY_COMPATIBILITY : START_STICKY;
}
這個(gè)方法的具體含義是，當(dāng)你的需要這個(gè)service啟動(dòng)的時(shí)候，或者調(diào)用這個(gè)servcie的時(shí)候，那么這個(gè)方法首先是要被回調(diào)的。
同時(shí)IntentService中提供了這么一個(gè)方法：
protected abstract void onHandleIntent(Intent intent);
這是一個(gè)抽象方法，也就是說(shuō)具體的實(shí)現(xiàn)需要被延伸到子類(lèi)。
子類(lèi)的聲明：
public class ChargeService extends IntentService
上面提到過(guò)IntentService是繼承Service的，那么這個(gè)子類(lèi)也肯定繼承service，那么onHandleIntent()方法是什么時(shí)候被調(diào)用的呢？讓我們具體看IntentService的內(nèi)部實(shí)現(xiàn)：
private final class ServiceHandler extends Handler {
public ServiceHandler(Looper looper) {
super(looper);
}
@Override
public void handleMessage(Message msg) {
onHandleIntent((Intent)msg.obj);
stopSelf(msg.arg1);
}
}
/**
* Creates an IntentService. Invoked by your subclass's constructor.
*
* @param name Used to name the worker thread, important only for debugging.
*/
public IntentService(String name) {
super();
mName = name;
}
/**
* Sets intent redelivery preferences. Usually called from the constructor
* with your preferred semantics.
*
* <p>If enabled is true,
* {@link #onStartCommand(Intent, int, int)} will return
* {@link Service#START_REDELIVER_INTENT}, so if this process dies before
* {@link #onHandleIntent(Intent)} returns, the process will be restarted
* and the intent redelivered. If multiple Intents have been sent, only
* the most recent one is guaranteed to be redelivered.
*
* <p>If enabled is false (the default),
* {@link #onStartCommand(Intent, int, int)} will return
* {@link Service#START_NOT_STICKY}, and if the process dies, the Intent
* dies along with it.
*/
public void setIntentRedelivery(boolean enabled) {
mRedelivery = enabled;
}
@Override
public void onCreate() {
// TODO: It would be nice to have an option to hold a partial wakelock
// during processing, and to have a static startService(Context, Intent)
// method that would launch the service & hand off a wakelock.
super.onCreate();
HandlerThread thread = new HandlerThread("IntentService[" + mName + "]");
thread.start();
mServiceLooper = thread.getLooper();
mServiceHandler = new ServiceHandler(mServiceLooper);
}
@Override
public void onStart(Intent intent, int startId) {
Message msg = mServiceHandler.obtainMessage();
msg.arg1 = startId;
msg.obj = intent;
mServiceHandler.sendMessage(msg);
}
在這里我們可以清楚的看到其實(shí)IntentService在執(zhí)行onCreate的方法的時(shí)候，其實(shí)開(kāi)了一個(gè)線(xiàn)程HandlerThread,并獲得了當(dāng)前線(xiàn)程隊(duì)列管理的looper，并且在onStart的時(shí)候，把消息置入了消息隊(duì)列，
@Override
public void handleMessage(Message msg) {
onHandleIntent((Intent)msg.obj);
stopSelf(msg.arg1);
}
在消息被handler接受并且回調(diào)的時(shí)候，執(zhí)行了onHandlerIntent方法，該方法的實(shí)現(xiàn)是子類(lèi)去做的。
結(jié)論：
IntentService是通過(guò)Handler looper message的方式實(shí)現(xiàn)了一個(gè)多線(xiàn)程的操作，同時(shí)耗時(shí)操作也可以被這個(gè)線(xiàn)程管理和執(zhí)行，同時(shí)不會(huì)產(chǎn)生ANR的情況。
- 自定義View的幾種方式
總結(jié)來(lái)說(shuō)，自定義控件的實(shí)現(xiàn)有三種方式，分別是：組合控件、自繪控件和繼承控件。下面將分別對(duì)這三種方式進(jìn)行介紹。
（一）組合控件
組合控件，顧名思義就是將一些小的控件組合起來(lái)形成一個(gè)新的控件，這些小的控件多是系統(tǒng)自帶的控件。比如很多應(yīng)用中普遍使用的標(biāo)題欄控件，其實(shí)用的就是組合控件，那么下面將通過(guò)實(shí)現(xiàn)一個(gè)簡(jiǎn)單的標(biāo)題欄自定義控件來(lái)說(shuō)說(shuō)組合控件的用法。
1、新建一個(gè)Android項(xiàng)目，創(chuàng)建自定義標(biāo)題欄的布局文件title_bar.xml：
<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:layout_width="match_parent"
android:layout_height="wrap_content"
android:background="#0000ff" >
<Button
android:id="@+id/left_btn"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_centerVertical="true"
android:layout_margin="5dp"
android:background="@drawable/back1_64" />
<TextView
android:id="@+id/title_tv"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_centerInParent="true"
android:text="這是標(biāo)題"
android:textColor="#ffffff"
android:textSize="20sp" />
</RelativeLayout>
可見(jiàn)這個(gè)標(biāo)題欄控件還是比較簡(jiǎn)單的，其中在左邊有一個(gè)返回按鈕，背景是一張事先準(zhǔn)備好的圖片back1_64.png，標(biāo)題欄中間是標(biāo)題文字。
2、創(chuàng)建一個(gè)類(lèi)TitleView，繼承自RelativeLayout：
public class TitleView extends RelativeLayout {
// 返回按鈕控件
private Button mLeftBtn;
// 標(biāo)題Tv
private TextView mTitleTv;
public TitleView(Context context, AttributeSet attrs) {
super(context, attrs);
// 加載布局
LayoutInflater.from(context).inflate(R.layout.title_bar, this);
// 獲取控件
mLeftBtn = (Button) findViewById(R.id.left_btn);
mTitleTv = (TextView) findViewById(R.id.title_tv);
}
// 為左側(cè)返回按鈕添加自定義點(diǎn)擊事件
public void setLeftButtonListener(OnClickListener listener) {
mLeftBtn.setOnClickListener(listener);
}
// 設(shè)置標(biāo)題的方法
public void setTitleText(String title) {
mTitleTv.setText(title);
}
}
在TitleView中主要是為自定義的標(biāo)題欄加載了布局，為返回按鈕添加事件監(jiān)聽(tīng)方法，并提供了設(shè)置標(biāo)題文本的方法。
3、在activity_main.xml中引入自定義的標(biāo)題欄：
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/main_layout"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:orientation="vertical" >
<com.example.test.TitleView
android:id="@+id/title_bar"
android:layout_width="match_parent"
android:layout_height="wrap_content" >
</com.example.test.TitleView>
</LinearLayout>
4、在MainActivity中獲取自定義的標(biāo)題欄，并且為返回按鈕添加自定義點(diǎn)擊事件：
private TitleView mTitleBar;
mTitleBar = (TitleView) findViewById(R.id.title_bar);
mTitleBar.setLeftButtonListener(new OnClickListener() {
@Override
public void onClick(View v) {
Toast.makeText(MainActivity.this, "點(diǎn)擊了返回按鈕", Toast.LENGTH_SHORT)
.show();
finish();
}
});
5、運(yùn)行效果如下：
這樣就用組合的方式實(shí)現(xiàn)了自定義標(biāo)題欄，其實(shí)經(jīng)過(guò)更多的組合還可以創(chuàng)建出功能更為復(fù)雜的自定義控件，比如自定義搜索欄等。
（二）自繪控件
自繪控件的內(nèi)容都是自己繪制出來(lái)的，在View的onDraw方法中完成繪制。下面就實(shí)現(xiàn)一個(gè)簡(jiǎn)單的計(jì)數(shù)器，每點(diǎn)擊它一次，計(jì)數(shù)值就加1并顯示出來(lái)。
1、創(chuàng)建CounterView類(lèi)，繼承自View，實(shí)現(xiàn)OnClickListener接口：
public class CounterView extends View implements OnClickListener {
// 定義畫(huà)筆
private Paint mPaint;
// 用于獲取文字的寬和高
private Rect mBounds;
// 計(jì)數(shù)值，每點(diǎn)擊一次本控件，其值增加1
private int mCount;
public CounterView(Context context, AttributeSet attrs) {
super(context, attrs);
// 初始化畫(huà)筆、Rect
mPaint = new Paint(Paint.ANTI_ALIAS_FLAG);
mBounds = new Rect();
// 本控件的點(diǎn)擊事件
setOnClickListener(this);
}
@Override
protected void onDraw(Canvas canvas) {
super.onDraw(canvas);
mPaint.setColor(Color.BLUE);
// 繪制一個(gè)填充色為藍(lán)色的矩形
canvas.drawRect(0, 0, getWidth(), getHeight(), mPaint);
mPaint.setColor(Color.YELLOW);
mPaint.setTextSize(50);
String text = String.valueOf(mCount);
// 獲取文字的寬和高
mPaint.getTextBounds(text, 0, text.length(), mBounds);
float textWidth = mBounds.width();
float textHeight = mBounds.height();
// 繪制字符串
canvas.drawText(text, getWidth() / 2 - textWidth / 2, getHeight() / 2
+ textHeight / 2, mPaint);
}
@Override
public void onClick(View v) {
mCount ++;
// 重繪
invalidate();
}
}
2、在activity_main.xml中引入該自定義布局：
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/main_layout"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:orientation="vertical" >
<com.example.test.CounterView
android:id="@+id/counter_view"
android:layout_width="100dp"
android:layout_height="100dp"
android:layout_gravity="center_horizontal|top"
android:layout_margin="20dp" />
</LinearLayout>
3、運(yùn)行效果如下：
（三）繼承控件
就是繼承已有的控件，創(chuàng)建新控件，保留繼承的父控件的特性，并且還可以引入新特性。下面就以支持橫向滑動(dòng)刪除列表項(xiàng)的自定義ListView的實(shí)現(xiàn)來(lái)介紹。
1、創(chuàng)建刪除按鈕布局delete_btn.xml，這個(gè)布局是在橫向滑動(dòng)列表項(xiàng)后顯示的：
<?xml version="1.0" encoding="utf-8"?>
<Button xmlns:android="http://schemas.android.com/apk/res/android"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:background="#FF0000"
android:padding="5dp"
android:text="刪除"
android:textColor="#FFFFFF"
android:textSize="16sp" >
</Button>
2、創(chuàng)建CustomListView類(lèi)，繼承自L(fǎng)istView，并實(shí)現(xiàn)了OnTouchListener和OnGestureListener接口：
public class CustomListView extends ListView implements OnTouchListener,
OnGestureListener {
// 手勢(shì)動(dòng)作探測(cè)器
private GestureDetector mGestureDetector;
// 刪除事件監(jiān)聽(tīng)器
public interface OnDeleteListener {
void onDelete(int index);
}
private OnDeleteListener mOnDeleteListener;
// 刪除按鈕
private View mDeleteBtn;
// 列表項(xiàng)布局
private ViewGroup mItemLayout;
// 選擇的列表項(xiàng)
private int mSelectedItem;
// 當(dāng)前刪除按鈕是否顯示出來(lái)了
private boolean isDeleteShown;
public CustomListView(Context context, AttributeSet attrs) {
super(context, attrs);
// 創(chuàng)建手勢(shì)監(jiān)聽(tīng)器對(duì)象
mGestureDetector = new GestureDetector(getContext(), this);
// 監(jiān)聽(tīng)onTouch事件
setOnTouchListener(this);
}
// 設(shè)置刪除監(jiān)聽(tīng)事件
public void setOnDeleteListener(OnDeleteListener listener) {
mOnDeleteListener = listener;
}
// 觸摸監(jiān)聽(tīng)事件
@Override
public boolean onTouch(View v, MotionEvent event) {
if (isDeleteShown) {
hideDelete();
return false;
} else {
return mGestureDetector.onTouchEvent(event);
}
}
@Override
public boolean onDown(MotionEvent e) {
if (!isDeleteShown) {
mSelectedItem = pointToPosition((int) e.getX(), (int) e.getY());
}
return false;
}
@Override
public boolean onFling(MotionEvent e1, MotionEvent e2, float velocityX,
float velocityY) {
// 如果當(dāng)前刪除按鈕沒(méi)有顯示出來(lái)，并且x方向滑動(dòng)的速度大于y方向的滑動(dòng)速度
if (!isDeleteShown && Math.abs(velocityX) > Math.abs(velocityY)) {
mDeleteBtn = LayoutInflater.from(getContext()).inflate(
R.layout.delete_btn, null);
mDeleteBtn.setOnClickListener(new OnClickListener() {
@Override
public void onClick(View v) {
mItemLayout.removeView(mDeleteBtn);
mDeleteBtn = null;
isDeleteShown = false;
mOnDeleteListener.onDelete(mSelectedItem);
}
});
mItemLayout = (ViewGroup) getChildAt(mSelectedItem
- getFirstVisiblePosition());
RelativeLayout.LayoutParams params = new RelativeLayout.LayoutParams(
LayoutParams.WRAP_CONTENT, LayoutParams.WRAP_CONTENT);
params.addRule(RelativeLayout.ALIGN_PARENT_RIGHT);
params.addRule(RelativeLayout.CENTER_VERTICAL);
mItemLayout.addView(mDeleteBtn, params);
isDeleteShown = true;
}
return false;
}
// 隱藏刪除按鈕
public void hideDelete() {
mItemLayout.removeView(mDeleteBtn);
mDeleteBtn = null;
isDeleteShown = false;
}
public boolean isDeleteShown() {
return isDeleteShown;
}
/**
* 后面幾個(gè)方法本例中沒(méi)有用到
*/
@Override
public void onShowPress(MotionEvent e) {
}
@Override
public boolean onSingleTapUp(MotionEvent e) {
return false;
}
@Override
public boolean onScroll(MotionEvent e1, MotionEvent e2, float distanceX,
float distanceY) {
return false;
}
@Override
public void onLongPress(MotionEvent e) {
}
}
3、定義列表項(xiàng)布局custom_listview_item.xml，它的結(jié)構(gòu)很簡(jiǎn)單，只包含了一個(gè)TextView：
<?xml version="1.0" encoding="utf-8"?>
<RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:descendantFocusability="blocksDescendants" >
<TextView
android:id="@+id/content_tv"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:layout_centerVertical="true"
android:layout_margin="30dp"
android:gravity="center_vertical|left" />
</RelativeLayout>
4、定義適配器類(lèi)CustomListViewAdapter，繼承自ArrayAdapter<String>：
public class CustomListViewAdapter extends ArrayAdapter<String> {
public CustomListViewAdapter(Context context, int textViewResourceId,
List<String> objects) {
super(context, textViewResourceId, objects);
}
@Override
public View getView(int position, View convertView, ViewGroup parent) {
View view;
if (convertView == null) {
view = LayoutInflater.from(getContext()).inflate(
R.layout.custom_listview_item, null);
} else {
view = convertView;
}
TextView contentTv = (TextView) view.findViewById(R.id.content_tv);
contentTv.setText(getItem(position));
return view;
}
}
5、在activity_main.xml中引入自定義的ListView：
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
android:id="@+id/main_layout"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:orientation="vertical" >
<com.example.test.CustomListView
android:id="@+id/custom_lv"
android:layout_width="match_parent"
android:layout_height="wrap_content" />
</LinearLayout>
6、在MainActivity中對(duì)列表做初始化、設(shè)置列表項(xiàng)刪除按鈕點(diǎn)擊事件等處理：
public class MainActivity extends Activity {
// 自定義Lv
private CustomListView mCustomLv;
// 自定義適配器
private CustomListViewAdapter mAdapter;
// 內(nèi)容列表
private List<String> contentList = new ArrayList<String>();
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
requestWindowFeature(Window.FEATURE_NO_TITLE);
setContentView(R.layout.activity_main);
initContentList();
mCustomLv = (CustomListView) findViewById(R.id.custom_lv);
mCustomLv.setOnDeleteListener(new OnDeleteListener() {
@Override
public void onDelete(int index) {
contentList.remove(index);
mAdapter.notifyDataSetChanged();
}
});
mAdapter = new CustomListViewAdapter(this, 0, contentList);
mCustomLv.setAdapter(mAdapter);
}
// 初始化內(nèi)容列表
private void initContentList() {
for (int i = 0; i < 20; i++) {
contentList.add("內(nèi)容項(xiàng)" + i);
}
}
@Override
public void onBackPressed() {
if (mCustomLv.isDeleteShown()) {
mCustomLv.hideDelete();
return;
}
super.onBackPressed();
}
}
7、運(yùn)行效果如下：
為啥要序列化
序列化的原因基本三種情況：
1.永久性保存對(duì)象，保存對(duì)象的字節(jié)序列到本地文件中；
2.對(duì)象在網(wǎng)絡(luò)中傳遞；
3.對(duì)象在IPC間傳遞。觸摸事件傳遞流程
Touch事件的一系列傳遞流程都是dispatchTouchEvent()來(lái)控制的，事件將由上而下依次傳遞。在向下傳遞的過(guò)程中onInterceptTouchEvent()
返回true，即事件被攔截了，事件則停止向下傳遞，由當(dāng)前View的onTouchEvent()處理。傳遞到最底層的View，就由他的onTouchEvent()處理，
若處理成功則返回true，處理失敗則返回false，事件依次向上傳遞，每個(gè)View都調(diào)用自己的onTouchEvent()來(lái)處理。
事件的傳向性具有當(dāng)前系列事件的“記憶”功能，即當(dāng)事件向下傳時(shí)其下級(jí)View處理不成功，當(dāng)前系列內(nèi)其將不再向下傳遞。如何設(shè)計(jì)緩存模塊
內(nèi)存層：（手機(jī)內(nèi)存）
內(nèi)存緩存相對(duì)于磁盤(pán)緩存而言，速度要來(lái)的快很多，但缺點(diǎn)容量較小且會(huì)被系統(tǒng)回收，這里的實(shí)現(xiàn)用到了LruCache。
LruCache這個(gè)類(lèi)是Android3.1版本中提供的，如果你是在更早的Android版本中開(kāi)發(fā)，則需要導(dǎo)入android-support-v4的jar包。
磁盤(pán)層：（SD卡）
相比內(nèi)存緩存而言速度要來(lái)得慢很多，但容量很大，用到了DiskLruCache類(lèi)。
DiskLruCache是非Google官方編寫(xiě)，但獲得官方認(rèn)證的硬盤(pán)緩存類(lèi)，該類(lèi)沒(méi)有限定在Android內(nèi)，所以理論上java應(yīng)用也可以使用DiskLreCache來(lái)緩存。
網(wǎng)絡(luò)層：（移動(dòng)網(wǎng)絡(luò)，無(wú)線(xiàn)網(wǎng)絡(luò)）
這里的網(wǎng)絡(luò)訪(fǎng)問(wèn)實(shí)現(xiàn)用到了開(kāi)源框架Volley。
開(kāi)源框架Volley是2013年Google大會(huì)發(fā)布的，Volley是Android平臺(tái)上的網(wǎng)絡(luò)通信庫(kù)，能使網(wǎng)絡(luò)通信更快，更簡(jiǎn)單，更健壯。它的設(shè)計(jì)目標(biāo)就是非常適合去進(jìn)行數(shù)據(jù)量不大，但通信頻繁的網(wǎng)絡(luò)操作，而對(duì)于大數(shù)據(jù)量的網(wǎng)絡(luò)操作，比如說(shuō)下載文件等，Volley的表現(xiàn)就會(huì)非常糟糕。如何做持久化
一、SharedPreferences
二、內(nèi)部存儲(chǔ)（存儲(chǔ)到手機(jī)內(nèi)部存儲(chǔ)空間）存儲(chǔ)目錄為data/data/package/files/
三、sdcard存儲(chǔ)
四、SQLite
五、網(wǎng)絡(luò)存儲(chǔ)
