Go文件操作

目錄

  • 示例1: 打開和關閉文件
  • 示例2: 打開文件並讀取內容
  • 示例3: 一次性讀取文件
  • 示例4: 帶緩衝的Reader讀文件
  • 示例5: 創建文件並寫入內容
  • 示例6: 寫文件的四種方式
  • 示例7: 把一個文件內容寫入到另一個文件
  • 示例8:使用bufio獲取用戶輸入
  • 示例9: 判斷文件或目錄是否存在
  • 示例10: 拷貝文件、圖片音視頻
  • 示例11: 遍歷目錄
    • 遍歷目錄
    • 僅遍歷目錄,忽略文件
  • 示例12: 修改文件名
  • 示例13:創建目錄
  • 示例14:刪除文件

對於文件,我們並不陌生,文件是數據源(保存數據的地方)的一種,比如大家經常使用的word文檔,txt文件,Excel文件…等等都是文件。文件最主要的作用就是保存數據,它既可以保存一張圖片,也可以保存視頻,聲音……
文件在程序中是以流的形式來操作的。

:數據在數據源(文件)和程序(內存)之間經歷的路徑
輸出流:數據從程序(內存)到數據源(文件)的路徑
輸入流:數據從數據源(文件)到程序(內存)的路徑
輸入與輸出都是相對於內存而言的,從內存向外流就是輸出,從外部向內存流就是輸入

在Go中,我們操作文件的方法在os包中,會經常使用到os.File結構體 Go語言標準庫文檔

示例1: 打開和關閉文件

package main

import (
    "fmt"
    "os"
)

func main() {

    //打開文件(/Users/xxx/Go/src/file.txt)
    //概念說明:file的叫法
    //1.file 叫 file對象
    //2.file 叫 file指針
    //3.file 叫 file文件句柄
    file, err := os.Open("/Users/itbsl/Go/src/file.txt")
    if err != nil {
        fmt.Println("文件打開失敗,原因是:", err)
        //os.Exit(0)
    }
    defer func() {
        //文件及時關閉
        err = file.Close()
        if err != nil {
            fmt.Println("文件關閉失敗,原因是", err)
        }
    }()
}

示例2: 打開文件並讀取內容

使用Read()函數按照字節讀

package main

import (
	"fmt"
	"io"
	"os"
)

func main() {

	file, err := os.Open("./test.txt")
	if err != nil {
		fmt.Printf("open file failed, err:%v\n", err)
		return
	}
	defer func() {
		err = file.Close()
		if err != nil {
			fmt.Printf("close file failed, err:%v\n", err)
		}
	}()

	var content []byte
	var tmp = make([]byte, 128)
	for {
		n, err := file.Read(tmp)
		//為什麼是tmp[:n]而不是tmp[:]?
		//因為當讀取到最後一行的內容長度不足tmp的長度的時候
		//新讀取的內容只會覆蓋前半部分上次讀取到的tmp的內容,
		//後半部分還是上一次讀取的內容,如果用tmp[:]就會導致
		//後半部分久內容又會被重新賦值一次,這其實是錯誤的
		content = append(content, tmp[:n]...)
		if err == io.EOF {//讀到文件末尾
			break
		}
	}
	fmt.Printf("讀取出來的內容為:\n")
	fmt.Printf("%q\n", string(content))
}

示例3: 一次性讀取文件

讀取文件內容並显示在終端,將文件內容一次性讀取到終端,適用於文件不大的情況。

package main

import (
    "fmt"
    "io/ioutil"
)

func main() {

    //打開文件,文件路徑相對於GOPATH開始,或者寫全路徑(/Users/xxx/Go/src/file.txt)
    file, err := ioutil.ReadFile("src/file.txt")
    if err != nil {
        fmt.Println("文件打開失敗,原因是:", err)
    }

    fmt.Printf("%s", string(file))
}

示例4: 帶緩衝的Reader讀文件

讀取文件的內容並显示在終端(帶緩衝區的方式),使用os.Open, file.Close,bufio.NewReader,reader.ReadString函數和方法。適合讀取大文件
1.使用ReadBytes方法
代碼1:

package main

import (
	"bufio"
	"fmt"
	"io"
	"log"
	"os"
)

func main() {

	file, err := os.Open("./test.txt")
	if err != nil {
		log.Fatalf("open file failed, err: %v\n", err)
	}
	defer func() {
		err = file.Close()
		if err != nil {
			log.Fatalf("close file failed, err: %v\n", err)
		}
	}()

	//定義變量result用來存儲讀取結果
	var result string
	//創建一個帶有緩衝區的reader
	reader := bufio.NewReader(file)
	for {
		buf, err := reader.ReadBytes('\n')
		if err != nil && err == io.EOF { //EOF代表文件的末尾
			//注意:為什麼要判斷err是否等於io.EOF?
			//因為存在這種情況,文件有內容的最後那一行尾部沒有換行
			//當使用ReadBytes或者ReadString方法按照'\n'換行讀取時,讀到尾部沒有換行的這種情況時就會報io.EOF錯誤
			//此時buf是讀取到了內容的,如果忽略掉了,那麼最終的讀取結果會少了最後一行的內容
			result += string(buf)
			break
		}
		result += string(buf)
	}
	fmt.Println(result)
}

代碼2:

package main

import (
	"bufio"
	"fmt"
	"io"
	"log"
	"os"
)

func main() {

	file, err := os.Open("./test.txt")
	if err != nil {
		log.Fatalf("open file failed, err: %v\n", err)
	}
	defer func() {
		err = file.Close()
		if err != nil {
			log.Fatalf("close file failed, err: %v\n", err)
		}
	}()

	//定義變量result用來存儲讀取結果
	var result string
	//創建一個帶有緩衝區的reader
	reader := bufio.NewReader(file)
	for {
		buf, err := reader.ReadBytes('\n')
		if err != nil {
			if err == io.EOF { //EOF代表文件的末尾
			//注意:為什麼要判斷err是否等於io.EOF?
			//因為存在這種情況,文件有內容的最後那一行尾部沒有換行
			//當使用ReadBytes或者ReadString方法按照'\n'換行讀取時,讀到尾部沒有換行的這種情況時就會報io.EOF錯誤
			//此時buf是讀取到了內容的,如果忽略掉了,那麼最終的讀取結果會少了最後一行的內容
				result += string(buf)
				break
			} else {
				log.Fatalf("ReadBytes failed, err: %v\n", err)
			}
		}
		result += string(buf)
	}
	fmt.Println(result)
}

2.ReadString方法

package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
)

func main() {

    //打開文件
    file, err := os.Open("./files/test.txt")
    if err != nil {
        fmt.Println("文件打開失敗,原因是:", err)
        return
    }

    //當函數退出時,要及時的關閉file
    defer func() {
        //文件及時關閉
        err = file.Close()
        if err != nil {
            fmt.Println("文件關閉失敗,原因是", err)
        }
    }()

    //創建一個 *Reader,是帶緩衝的
    reader := bufio.NewReader(file)
    var result string
    //循環讀取文件內容
    for {
        str, err := reader.ReadString('\n') //讀到一個換行就結束
        result += str
        if err == io.EOF {//io.EOF代表文件的末尾
            //注意:如果文件最後一行文字沒有換行,則會一直讀取到文件末尾,
            //所以即使是判斷讀到了文件末尾,也要把讀取的內容輸出一下
            break
        }
    }
    fmt.Println(result)
}

示例5: 創建文件並寫入內容

第二個參數:文件代開模式(可以組合);第三個參數:權限控制(如0755)

package main

import (
	"fmt"
	"os"
)

func main() {

	//1.創建文件file.txt
	file, err := os.OpenFile("src/file.txt", os.O_WRONLY | os.O_CREATE, 0755)
	if err != nil {
		fmt.Println("文件打開/創建失敗,原因是:", err)
		return
	}

	defer func() {
		err  = file.Close()
		if err != nil {
			fmt.Println("文件關閉失敗,原因是:", err)
		}
	}()

	//寫入數據
	var str = "暗黑西遊獅駝嶺,斗戰勝佛孫悟空。\n"

	for i := 0; i < 5; i++ {
		file.WriteString(str)
	}
}

示例6: 寫文件的四種方式

1.使用WriteAt()搭配Seek()方法實現寫文件功能

package main

import (
	"io"
	"log"
	"os"
)

func main() {

	file, err := os.OpenFile("./test.txt", os.O_RDWR|os.O_CREATE, 0755)
	if err != nil {
		log.Fatalf("open file failed, err: %v\n", err)
	}
	defer func() {
		err = file.Close()
		if err != nil {
			log.Fatalf("close file failed, err: %v\n", err)
		}
	}()
    //Seek(): 修改文件的讀寫指針位置.
    //參數1: 偏移量. 正:向文件尾部偏移, 負:向文件頭部偏移
    //參數2: 偏移起始位置
    //       io.SeekStart: 文件起始位置
    //       io.SeekCurrent: 文件當前位置
    //       io.SeekEnd: 文件結尾位置
    //返回值:表示從文件起始位置,到當前文件讀寫指針位置的偏移量。
    //WriteAt(): 在文件指定偏移位置,寫入[]byte,通常搭配Seek()
    //參數1: 待寫入的數據
    //參數2: 偏移量
    //返回: 實際寫出的字節數
	for i := 0; i < 5; i++ {
		offset, _ := file.Seek(-3, io.SeekEnd)
		_, _ = file.WriteAt([]byte("你好"), offset)
	}
}

注意: 由於使用的OpenFile函數打開的文件,所以在選擇打開模式的時候不能選擇os.O_APPEND模式,因為該模式表示的是在文件末尾追加,這與WriteAt在指定的位置寫是想衝突的,雖然我在測試的時候加上os.O_APPEND模式並沒有報錯,但是代碼執行完之後發現,想要寫入的內容並沒有真正的寫入到文件中。
寫入前

寫入后

2.一次性寫文件

package main

import (
	"io/ioutil"
	"log"
)

func main() {
	str := "hello樹先生"
	//如果文件已存在,則會清空原來的內容,寫入新內容,如果文件不存在,則會創建文件並寫入內容
	err := ioutil.WriteFile("./test.txt", []byte(str), 0755)
	if err != nil {
		log.Fatalf("寫入文件錯誤,錯誤為:%v\n", err)
	}
}

3.使用帶緩衝的方式寫文件

package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {

	//1.創建文件file.txt
	file, err := os.OpenFile("src/file.txt", os.O_WRONLY | os.O_CREATE | os.O_TRUNC, 0755)
	defer func() {
		err  = file.Close()
		if err != nil {
			fmt.Println("文件關閉失敗,原因是:", err)
		}
	}()

	if err != nil {
		fmt.Println("文件創建失敗,原因是:", err)
		return
	}

	//寫入數據
	var str = "你好,世界\n"

	//寫入時,使用帶緩存的*Writer
	writer := bufio.NewWriter(file)

	for i := 0; i < 5; i++ {
		writer.WriteString(str)
	}

	//因為writer是帶緩存的,因此在調用writeString方法時,其實內容是先寫入到緩存
	//因此需要調用Flush方法,將緩存數據寫入到文件中,否則文件中會丟失數據
	writer.Flush()
}

示例7: 把一個文件內容寫入到另一個文件

package main

import (
    "fmt"
    "io/ioutil"
)

func main() {

    //打開文件,文件路徑相對於GOPATH開始,或者寫全路徑(/Users/xxx/Go/src/file.txt)
    data, err := ioutil.ReadFile("src/1.txt")
    if err != nil {
        fmt.Println("文件打開失敗,原因是:", err)
    }

    err = ioutil.WriteFile("src/2.txt", data, 0755)

    if err != nil {
        fmt.Println("文件寫入失敗,原因是:", err)
    }
}

示例8:使用bufio獲取用戶輸入

package main

import (
    "bufio"
    "fmt"
    "os"
)

func main() {
    var s string
    var reader = bufio.NewReader(os.Stdin)
    s, _ = reader.ReadString('\n')
    fmt.Printf("讀取到的內容為:%s\n", s)
}

示例9: 判斷文件或目錄是否存在

Go判斷文件或文件夾是否存在的方法為使用os.Stat()函數返回的錯誤值進行判斷:
(1)如果返回的錯誤為nil,說明文件或文件夾存在
(2)如果返回的類型使用os.IsNotExist()判斷為true,說明文件或文件夾不存在
(3)如果返回的錯誤為其它類型,則不確定是否存在

package main

import (
	"fmt"
	"os"
)

func main() {

	isExist, err := isFileExists("src/sfile.txt")
	if err != nil {
		fmt.Println("發生錯誤:", err)
	}

	if isExist {
		fmt.Println("存在")
	} else {
		fmt.Println("不存在")
	}
}

//判斷文件或者目錄是否存在
func isFileExists(path string) (bool, error) {

	_, err := os.Stat(path)
	if err == nil {
		return true, nil
	}
	if os.IsNotExist(err) {
		return false, nil
	}
	return false, err
}

示例10: 拷貝文件、圖片音視頻

io.Copy方法

package main

import (
	"fmt"
	"io"
	"os"
)
func CopyFile(srcFileName string, dstFileName string) (int64, error) {

	//源文件處理
	srcFile, err := os.Open(srcFileName)
	defer func() {
		err = srcFile.Close()
		if err != nil {
			fmt.Println("源文件關閉失敗,原因是:", err)
		}
	}()

	if err != nil {
		fmt.Println("源文件打開失敗,原因是:", err)
		return 0, err
	}

	//目標文件處理
	dstFile, err := os.OpenFile(dstFileName, os.O_CREATE | os.O_WRONLY, 0755)
	defer func() {
		err = dstFile.Close()
		if err != nil {
			fmt.Println("目標文件關閉失敗,原因是:", err)
		}
	}()
	if err != nil {
		fmt.Println("目標文件打開失敗,原因是:", err)
		return 0, err
	}

	return io.Copy(dstFile, srcFile)
}

func main() {

	result, err := CopyFile("src/dst.jpeg", "src/哈哈.jpeg")

	if err == nil {
		fmt.Println("拷貝成功!拷貝的字節數為: ", result)
	}
}

對於大文件,我們還可以採用下面的方式

package main

import (
	"io"
	"log"
	"os"
)

func CopyFile(srcFileName string, dstFileName string) {
	//打開源文件
	srcFile, err := os.Open(srcFileName)
	if err != nil {
		log.Fatalf("源文件讀取失敗,原因是:%v\n", err)
	}
	defer func() {
		err = srcFile.Close()
		if err != nil {
			log.Fatalf("源文件關閉失敗,原因是:%v\n", err)
		}
	}()

	//創建目標文件,稍後會向這個目標文件寫入拷貝內容
	distFile, err := os.Create(dstFileName)
	if err != nil {
		log.Fatalf("目標文件創建失敗,原因是:%v\n", err)
	}
	defer func() {
		err = distFile.Close()
		if err != nil {
			log.Fatalf("目標文件關閉失敗,原因是:%v\n", err)
		}
	}()
	//定義指定長度的字節切片,每次最多讀取指定長度
	var tmp = make([]byte, 1024*4)
	//循環讀取並寫入
	for {
		n, err := srcFile.Read(tmp)
		n, _ = distFile.Write(tmp[:n])
		if err != nil {
			if err == io.EOF {//讀到了文件末尾,並且寫入完畢,任務完成返回(關閉文件的操作由defer來完成)
				return
			} else {
				log.Fatalf("拷貝過程中發生錯誤,錯誤原因為:%v\n", err)
			}
		}
	}
}

func main() {
	CopyFile("./worm.mp4", "./dist.mp4")
}

示例11: 遍歷目錄

遍歷目錄

package main

//我們讀寫的文件一般存放於目錄中.因此,有時需要指定到某一個目錄下,根據目錄存儲的狀況
//再進行文件的特定操作.接下來我們看看目錄的基本操作方法.
import (
	"fmt"
	"log"
	"os"
)
//打開目錄
//打開目錄我們也使用OpenFile函數,但要指定不同的參數來通知系統,要打開的是一個目錄文件.
//func OpenFile(name string, flag int, perm FileMode) (file *File, err error)
//參數1: name,表示要打開的目錄名稱.使用絕對路徑較多
//參數2: flag,表示打開文件的讀寫模式
//參數3: perm,表示打開權限.但對於目錄來說有所不同,通常傳os.ModeDir.
//返回值:由於是操作目錄,所以file是指向目錄的文件指針.err中保存錯誤信息

//讀目錄內容
//這與讀文件有所不同.目錄中存放的是文件名和子目錄名.所以使用Readdir函數
//func (f *File) Readdir(n int) (fi []FileInfo, err error)
//如果n>0,Readdir函數會返回一個最多n個成員的切片。這時,如果Readdir返回一個空切片,
//它會返回一個非nil的錯誤說明原因。如果到達了目錄f的結尾,返回值err會是io.EOF。
//
//如果n<=0,Readdir函數返回目錄中剩餘所有文件對象的FileInfo構成的切片。
//此時,如果Readdir調用成功(讀取所有內容直到結尾),它會返回該切片和nil的錯誤值。
//如果在到達結尾前遇到錯誤,會返回之前成功讀取的FileInfo構成的切片和該錯誤。

func main() {
	//不推薦,因為通過查看ioutil.ReadDir()函數可知,官方使用的是os.Open()函數打開的目錄
	//file, err := os.OpenFile("./dir", os.O_RDWR, os.ModeDir)
	file, err := os.Open("./dir")
	if err != nil {
		log.Fatalf("文件打開失敗,原因是:%v\n", err)
	}
	defer func() {
		err = file.Close()
		if err != nil {
			log.Fatalf("文件關閉失敗,原因是:%v\n", err)
		}
	}()
	//Readdir方法返回一個FileInfo接口類型的切片和一個error類型的錯誤
	infos, err := file.Readdir(-1)
	for _, info := range infos {
		fmt.Printf("%v, %v\n", info.Name(), info.IsDir())
	}
}

僅遍歷目錄,忽略文件

方法1:使用os包

package main

import (
    "fmt"
    "os"
)

var dirNames = make([]string, 0, 50)
var pathSeparator = string(os.PathSeparator)
func traverseDir(filePath string) error {
    file, err := os.Open(filePath)
    if err != nil {
        return err
    }
    fileInfo, err := file.Readdir(0)
    if err != nil {
        return err
    }

    for _, value := range fileInfo {
        if value.IsDir() {
            dirNames = append(dirNames, value.Name())
            err = traverseDir(filePath+pathSeparator+value.Name())
            if err != nil {
                return err
            }
        }
    }
    return err
}

func main() {

    var filePath = "./dir"
    err := traverseDir(filePath)
    if err != nil {
        fmt.Println(err)
    }
    fmt.Println(dirNames)
}

方法2:使用ioutil包

package main

import (
    "fmt"
    "io/ioutil"
    "os"
)

var dirNames = make([]string, 0, 50)
var pathSeparator = string(os.PathSeparator)
func traverseDir(filePath string) error {
    fileInfos, err := ioutil.ReadDir(filePath)
    if err != nil {
        return err
    }
    for _, fileInfo :=range fileInfos {
        if fileInfo.IsDir() {
            dirNames = append(dirNames, fileInfo.Name())
            err =  traverseDir(filePath+pathSeparator+fileInfo.Name())
            if err != nil {
                return err
            }
        }
    }
    return err
}

func main() {

    var filePath = "./dir"
    err := traverseDir(filePath)
    if err != nil {
        fmt.Println(err)
    }
    fmt.Println(dirNames)
}

示例12: 修改文件名

package main

import (
    "fmt"
    "io/ioutil"
    "os"
    "strings"
)

var pathSeparator = string(os.PathSeparator)
//重命名文件
func renameFileName(filePath string, old string, new string) error {
    files, err := ioutil.ReadDir(filePath)
    if err != nil {
        return err
    }
    for _, fileInfo := range files {
        if !fileInfo.IsDir() {
            err = os.Rename(filePath + pathSeparator + fileInfo.Name(),
                filePath + pathSeparator + strings.Replace(fileInfo.Name(), old, new, -1),
            )
            if err != nil {
                return err
            }
        }
    }
    return err
}

func main() {
    var filePath = "./dir"
    err := renameFileName(filePath, "f", "kkk")
    if err != nil {
        fmt.Printf("錯誤: %v\n", err)
    }
}

示例13:創建目錄

package main

import (
	"fmt"
	"os"
)

func main() {
	//Mkdir使用指定的權限和名稱創建一個目錄。如果出錯,會返回*PathError底層類型的錯誤。
	err := os.Mkdir("./foo", 0755)
	if os.IsExist(err) {
		fmt.Println("目錄已存在")
		return
	}

	//MkdirAll使用指定的權限和名稱創建一個目錄,包括任何必要的上級目錄,並返回nil,否則返回錯誤。
	//權限位perm會應用在每一個被本函數創建的目錄上。如果path指定了一個已經存在的目錄,MkdirAll不做任何操作並返回nil。
	err = os.MkdirAll("./foo/bar", 0755)
	if err != nil {
		fmt.Printf("%v\n", err)
		return
	}
}

示例14:刪除文件

package main

import (
	"fmt"
	"os"
)

func main() {
	//Remove刪除name指定的文件或目錄。如果出錯,會返回*PathError底層類型的錯誤。
	//該方法不能刪除非空目錄,如果想刪除目錄以及目錄下的所有文件,可以使用RemoveAll
	err := os.Remove("./def")
	if os.IsNotExist(err) {
		fmt.Println("您要刪除的文件或目錄不存在")
		return
	}
	if err != nil {
		fmt.Println(err)
	}

	//RemoveAll刪除path指定的文件,或目錄及它包含的任何下級對象。
	//它會嘗試刪除所有東西,除非遇到錯誤並返回。
	//如果path指定的對象不存在,RemoveAll會返回nil而不返回錯誤。
	err = os.RemoveAll("./def")
	if err != nil {
		fmt.Println(err)
	}
}

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計最專業,超強功能平台可客製化

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家公司費用怎麼算?

【原創】Linux中斷子系統(二)-通用框架處理

背景

  • Read the fucking source code! –By 魯迅
  • A picture is worth a thousand words. –By 高爾基

說明:

  1. Kernel版本:4.14
  2. ARM64處理器,Contex-A53,雙核
  3. 使用工具:Source Insight 3.5, Visio

1. 概述

【原創】Linux中斷子系統(一)-中斷控制器及驅動分析講到了底層硬件GIC驅動,以及Arch-Specific的中斷代碼,本文將研究下通用的中斷處理的過程,屬於硬件無關層。當然,我還是建議你看一下上篇文章。

這篇文章會解答兩個問題:

  1. 用戶是怎麼使用中斷的(中斷註冊)?
  2. 外設觸發中斷信號時,最終是怎麼調用到中斷handler的(中斷處理)?

2. 數據結構分析

先來看一下總的數據結構,核心是圍繞着struct irq_desc來展開:

  • Linux內核的中斷處理,圍繞着中斷描述符結構struct irq_desc展開,內核提供了兩種中斷描述符組織形式:

    1. 打開CONFIG_SPARSE_IRQ宏(中斷編號不連續),中斷描述符以radix-tree來組織,用戶在初始化時進行動態分配,然後再插入radix-tree中;
    2. 關閉CONFIG_SPARSE_IRQ宏(中斷編號連續),中斷描述符以數組的形式組織,並且已經分配好;
    3. 不管哪種形式,最終都可以通過linux irq號來找到對應的中斷描述符;
  • 圖的左側灰色部分,主要在中斷控制器驅動中進行初始化設置,包括各個結構中函數指針的指向等,其中struct irq_chip用於對中斷控制器的硬件操作,struct irq_domain與中斷控制器對應,完成的工作是硬件中斷號到Linux irq的映射;

  • 圖的上側灰色部分,中斷描述符的創建(這裏指CONFIG_SPARSE_IRQ),主要在獲取設備中斷信息的過程中完成的,從而讓設備樹中的中斷能與具體的中斷描述符irq_desc匹配;

  • 圖中剩餘部分,在設備申請註冊中斷的過程中進行設置,比如struct irqactionhandler的設置,這個用於指向我們設備驅動程序中的中斷處理函數了;

中斷的處理主要有以下幾個功能模塊:

  1. 硬件中斷號到Linux irq中斷號的映射,並創建好irq_desc中斷描述符;
  2. 中斷註冊時,先獲取設備的中斷號,根據中斷號找到對應的irq_desc,並將設備的中斷處理函數添加到irq_desc中;
  3. 設備觸發中斷信號時,根據硬件中斷號得到Linux irq中斷號,找到對應的irq_desc,最終調用到設備的中斷處理函數;

上述的描述比較簡單,更詳細的過程,往下看吧。

3. 流程分析

3.1 中斷註冊

這一次,讓我們以問題的方式來展開:
先來讓我們回答第一個問題:用戶是怎麼使用中斷的?

  1. 熟悉設備驅動的同學應該都清楚,經常會在驅動程序中調用request_irq()接口或者request_threaded_irq()接口來註冊設備的中斷處理函數;
  2. request_irq()/request_threaded_irq接口中,都需要用到irq,也就是中斷號,那麼這个中斷號是從哪裡來的呢?它是Linux irq,它又是如何映射到具體的硬件設備的中斷號的呢?

先來看第二個問題:設備硬件中斷號到Linux irq中斷號的映射

  • 硬件設備的中斷信息都在設備樹device tree中進行了描述,在系統啟動過程中,這些信息都已經加載到內存中並得到了解析;
  • 驅動中通常會使用platform_get_irqirq_of_parse_and_map接口,去根據設備樹的信息去創建映射關係(硬件中斷號到linux irq中斷號映射);
  • 【原創】Linux中斷子系統(一)-中斷控制器及驅動分析提到過struct irq_domain用於完成映射工作,因此在irq_create_fwspec_mapping接口中,會先去找到匹配的irq domain,再去回調該irq domain中的函數集,通常irq domain都是在中斷控制器驅動中初始化的,以ARM GICv2為例,最終回調到gic_irq_domain_hierarchy_ops中的函數;
  • 如果已經創建好了映射,那麼可以直接進行返回linux irq中斷號了,否則的話需要irq_domain_alloc_irqs來創建映射關係;
  • irq_domain_alloc_irqs完成兩個工作:
    1. 針對linux irq中斷號創建一個irq_desc中斷描述符;
    2. 調用domain->ops->alloc函數來完成映射,在ARM GICv2驅動中對應gic_irq_domain_alloc函數,這個函數很關鍵,所以下文介紹一下;

gic_irq_domain_alloc函數如下:

  • gic_irq_domain_translate:負責解析出設備樹中描述的中斷號和中斷觸發類型(邊緣觸發、電平觸發等);
  • gic_irq_domain_map:將硬件中斷號和linux中斷號綁定到一個結構中,也就完成了映射,此外還綁定了irq_desc結構中的其他字段,最重要的是設置了irq_desc->handle_irq的函數指針,這個最終是中斷響應時往上執行的入口,這個是關鍵,下文講述中斷處理過程時還會提到;
  • 根據硬件中斷號的範圍設置irq_desc->handle_irq的指針,共享中斷入口為handle_fasteoi_irq,私有中斷入口為handle_percpu_devid_irq

上述函數執行完成后,完成了兩大工作:

  1. 硬件中斷號與Linux中斷號完成映射,併為Linux中斷號創建了irq_desc中斷描述符;
  2. 數據結構的綁定及初始化,關鍵的地方是設置了中斷處理往上執行的入口;

再看第一個問題:中斷是怎麼來註冊的?

設備驅動中,獲取到了irq中斷號后,通常就會採用request_irq/request_threaded_irq來註冊中斷,其中request_irq用於註冊普通處理的中斷,request_threaded_irq用於註冊線程化處理的中斷;

在講具體的註冊流程前,先看一下主要的中斷標誌位:

#define IRQF_SHARED		0x00000080              //多個設備共享一个中斷號,需要外設硬件支持
#define IRQF_PROBE_SHARED	0x00000100              //中斷處理程序允許sharing mismatch發生
#define __IRQF_TIMER		0x00000200              //時鐘中斷
#define IRQF_PERCPU		0x00000400              //屬於特定CPU的中斷
#define IRQF_NOBALANCING	0x00000800              //禁止在CPU之間進行中斷均衡處理
#define IRQF_IRQPOLL		0x00001000              //中斷被用作輪訓
#define IRQF_ONESHOT		0x00002000              //一次性觸發的中斷,不能嵌套,1)在硬件中斷處理完成后才能打開中斷;2)在中斷線程化中保持關閉狀態,直到該中斷源上的所有thread_fn函數都執行完
#define IRQF_NO_SUSPEND		0x00004000              //系統休眠喚醒操作中,不關閉該中斷
#define IRQF_FORCE_RESUME	0x00008000              //系統喚醒過程中必須強制打開該中斷
#define IRQF_NO_THREAD		0x00010000              //禁止中斷線程化
#define IRQF_EARLY_RESUME	0x00020000              //系統喚醒過程中在syscore階段resume,而不用等到設備resume階段
#define IRQF_COND_SUSPEND	0x00040000              //與NO_SUSPEND的用戶共享中斷時,執行本設備的中斷處理函數

  • request_irq也是調用request_threaded_irq,只是在傳參的時候,線程處理函數thread_fn函數設置成NULL;
  • 由於在硬件中斷號和Linux中斷號完成映射后,irq_desc已經創建好,可以通過irq_to_desc接口去獲取對應的irq_desc
  • 創建irqaction,並初始化該結構體中的各個字段,其中包括傳入的中斷處理函數賦值給對應的字段;
  • __setup_irq用於完成中斷的相關設置,包括中斷線程化的處理:
    1. 中斷線程化用於減少系統關中斷的時間,增強系統的實時性;
    2. ARM64默認開啟了CONFIG_IRQ_FORCED_THREADING,引導參數傳入threadirqs時,則除了IRQF_NO_THREAD外的中斷,其他的都將強制線程化處理;
    3. 中斷線程化會為每个中斷都創建一個內核線程,如果中斷進行共享,對應irqaction將連接成鏈表,每個irqaction都有thread_mask位圖字段,當所有共享中斷都處理完成后才能unmask中斷,解除中斷屏蔽;

3.2 中斷處理

當完成中斷的註冊后,所有結構的組織關係都已經建立好,剩下的工作就是當信號來臨時,進行中斷的處理工作。

來回顧一下【原創】Linux中斷子系統(一)-中斷控制器及驅動分析中的Arch-specific處理流程:

  • 中斷收到之後,首先會跳轉到異常向量表的入口處,進而逐級進行回調處理,最終調用到generic_handle_irq來進行中斷處理。

generic_handle_irq處理如下圖:

  • generic_handle_irq函數最終會調用到desc->handle_irq(),這個也就是對應到上文中在建立映射關係的過程中,調用irq_domain_set_info函數,設置好了函數指針,也就是handle_fasteoi_irqhandle_percpu_devid_irq
  • handle_fasteoi_irq:處理共享中斷,並且遍歷irqaction鏈表,逐個調用action->handler()函數,這個函數正是設備驅動程序調用request_irq/request_threaded_irq接口註冊的中斷處理函數,此外如果中斷線程化處理的話,還會調用__irq_wake_thread()喚醒內核線程;
  • handle_percpu_devid_irq:處理per-CPU中斷處理,在這個過程中會分別調用中斷控制器的處理函數進行硬件操作,該函數調用action->handler()來進行中斷處理;

來看看中斷線程化處理后的喚醒流程吧__handle_irq_event_percpu->__irq_wake_thread

  • __handle_irq_event_percpu->__irq_wake_thread將喚醒irq_thread中斷內核線程;
  • irq_thread內核線程,將根據是否為強制中斷線程化對函數指針handler_fn進行初始化,以便後續進行調用;
  • irq_thread內核線程將while(!irq_wait_for_interrupt)循環進行中斷的處理,當滿足條件時,執行handler_fn,在該函數中最終調用action->thread_fn,也就是完成了中斷的處理;
  • irq_wait_for_interrupt函數,將會判斷中斷線程的喚醒條件,如果滿足了,則將當前任務設置成TASK_RUNNING狀態,並返回0,這樣就能執行中斷的處理,否則就調用schedule()進行調度,讓出CPU,並將任務設置成TASK_INTERRUPTIBLE可中斷睡眠狀態;

3.3 總結

中斷的處理,總體來說可以分為兩部分來看:

  1. 從上到下:圍繞irq_desc中斷描述符建立好連接關係,這個過程就包括:中斷源信息的解析(設備樹),硬件中斷號到Linux中斷號的映射關係、irq_desc結構的分配及初始化(內部各個結構的組織關係)、中斷的註冊(填充irq_desc結構,包括handler處理函數)等,總而言之,就是完成靜態關係創建,為中斷處理做好準備;
  2. 從下到上,當外設觸發中斷信號時,中斷控制器接收到信號併發送到處理器,此時處理器進行異常模式切換,並逐步從處理器架構相關代碼逐級回調。如果涉及到中斷線程化,則還需要進行中斷內核線程的喚醒操作,最終完成中斷處理函數的執行。

歡迎關注個人公眾號,不定期分享Linux內核機制文章

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※超省錢租車方案

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

※推薦台中搬家公司優質服務,可到府估價

為.netcore助力–WebApiClient正式發布core版本

1 前言

WebApiClient已成熟穩定,發布了WebApiClient.JIT和WebApiClient.AOT兩個nuget包,累計近10w次下載。我對它的高可擴展性設計相當滿意和自豪,但WebApiClient並不因此而停下腳步,在一年前,我產生了編寫其core版本的想法,將asp.netcore服務端先進的思想融入到core版本,在性能與擴展性上得到進一步升華。
對應的,給它叫了WebApiClientCore的名字,為了對得起名字裏面的Core字,我在框架設計、性能優化上佔用整體開發時間一半以上。

2 框架設計

IActionInvoker

WebApiClient時還沒有IActionInvoker概念,對應的執行邏輯直接在ApiActionContext上實現。現在我覺得,Context應該是一個狀態數據類,而不能也成為一個執行者,因為一個執行者的實例可以無限次地執行多個Context實例。

Refit則更簡單粗暴,將所有實現都在一個RequestBuilderImplementation的類上:你們只要也只能使用我內置的Attribute聲明,一切執行在我這個類裡面包辦,因為我是一個萬能類。

Core版本增加了IActionInvoker概念,從中Context分開,用於執行Context,職責分明。在實現上又分為多種Invoker:Task聲明返回執行者ActionInvoker、ITask聲明返回處理處理者ActionTask,以及聚合的MultiplexedActionInvoker。

Middleware思想

WebApiClient時在處理各個特性、參數驗證、返回值驗證時沒有使用Middleware思想,特別是在處理響應結果和異常短路邏輯難以維護。

Refit還是簡單粗暴,將所有特性的解釋實現都在這個RequestBuilderImplementation的類上,因為我還是一個萬能類。

Core版本增加中間件Builder,將請求前的相關Attribute的執行編排Build為一個請求處理委託,將請求后相關Attribute的執行編排Build為一個響應處理委託,然後把兩個委託與真實http請求串在一起,Build出一個完整的請求響應委託。

得益於Middleware,流程中的請求前參數值驗證、結果處理特性短路、異常短路、請求后結果值驗和無條件執行IApiFilterAtrribue等這些複雜的流程變成簡單的管道處理;另外接口也變成支持服務端響應多種格式內容,每種格式內容在一個IApiReturnAttribute上實現和處理,比如請求為Accept: application/json, application/xml,不管服務器返回xml或json都能處理。

/// <summary>
/// 創建執行委託
/// </summary>
/// <param name="apiAction">action描述器</param>
/// <returns></returns>
public static Func<ApiRequestContext, Task<ApiResponseContext>> Build(ApiActionDescriptor apiAction)
{
    var requestHandler = BuildRequestHandler(apiAction);
    var responseHandler = BuildResponseHandler(apiAction);

    return async request =>
    {
        await requestHandler(request).ConfigureAwait(false);
        var response = await HttpRequest.SendAsync(request).ConfigureAwait(false);
        await responseHandler(response).ConfigureAwait(false);
        return response;
    };
}

Context思想

WebApiClient只有一個ApiActionContext,其Result和Exception屬性在請求前就可以訪問或設置,但實際上就算設置了值,流程也不會短路和中斷,屬於設計失誤。

Refit沒有相關Context概念,因為它不提供給用戶自定義擴展Attribute的能力,它內置的Attribute也沒有執行能力,一個RequestBuilderImplementation類夠了。

Core版本將設計了多個Context概念,不同階段有不同的Context,如同asp.netcore不同Filter的Context也不同一樣。對於一個Action,請求階段對應是ApiRequestContext,響應階段是ApiResponseContext;對於Action的參數,對應是ApiParameterContext。每種Context裏面都包含核心的HttpContext屬性,HttpContext包含請求消息、響應消息和接口配置選項等。

Interface思想

輸入WebApiClientCore命名空間,會發現定義了很多Interface,這些Interface都是為了用戶實現自定義特性用的,當然內置的所有特性,都是實現了這些接口而已。如果一個特性實現了多個接口,它就有多種能力,比如內置的HeaderAttribute,它既可以修飾於Interface和Method,也可以修飾參數。

WebApiClientCore的Attribute描述的邏輯,是由Attribute自我實現,所以整個請求的數據裝配邏輯是分散為各個Attribute上,用什麼Attribute就有什麼邏輯,包含框架之外的非內置的自定義Attribute。

Refit的內置Attribute只有欲描述邏輯,沒有實現邏輯,實現邏輯由RequestBuilderImplementation包辦,所以它不需要接口也沒有接口。

3 性能優化

更快的字符串替換

像[HttpGet(“objects/{id}”)]這樣的path參數,在restful中常常遇到,通過Span優化,Core版本在替換path參數值cpu佔用時間降低為原版本的十分之一。

更快的json序列化

得益於Sytem.Text.Json,json序列化和反序列化上性能顯明提升。

更少的緩衝區分配

WebApiClientCore使用了可回收復用的IBufferWriter,在json序列化得到json、json裝配為HttpContent只申請一次Buffer,而且HttpContent在發送之後,這個Buffer被回收復用。IBufferWriter還於用表單的uri編碼,編碼產生的Buffer不用申請新的內存內容,直接寫入表單的HttpContent。

更少的編碼操作

WebApiClientCore的json不再使用utf16的string中間類型,直接將對象序列化為網絡請求需要的utf8編碼二進制json;表單的key和Value編碼時,也不產生string中間類型,而是編碼后的二進制數據內容,然後寫入表單的IBufferWriter。

更快的緩存查找

WebApiClient創建代理類實例來執行一個請求時,要查找兩次緩存:通過接口類型查找字典緩存的接口代理類,然後實例化代理類;在ApiInterceptor裏面通過MethodInfo查找字典緩存的ApiActionDescriptor。

Refit執行同樣邏輯也使用了兩次字典緩存,接口和接口代理類安全字典緩存TypeMapping,接口和接口方法描述的字典緩存interfaceHttpMethods。

WebApiClientCore取消了字典緩存,使用靜態泛型類的字段作緩存,因為字段訪問遠比字典查找高效。同時通過巧妙的設計,在代理類攔截方法執行時,直接回傳IActionInvoker替換原來的MethodInfo,IActionInvoker包含了ApiActionDescriptor,而IActionInvoker與代理類型都一起緩存在靜態泛型類的字段,減少了一次必須的字典緩存查找過程。

性能對比

排除掉真實的網絡請求IO等待時間,WebApiClientCore使用的cpu時間僅僅為WebApiClient.JIT和Refit的三分之一。

BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18362.836 (1903/May2019Update/19H1)
Intel Core i3-4150 CPU 3.50GHz (Haswell), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=3.1.202
  [Host]     : .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT
  DefaultJob : .NET Core 3.1.4 (CoreCLR 4.700.20.20201, CoreFX 4.700.20.22101), X64 RyuJIT
Method Mean Error StdDev
HttpClient_GetAsync 3.146 μs 0.0396 μs 0.0370 μs
WebApiClientCore_GetAsync 12.421 μs 0.2324 μs 0.2174 μs
Refit_GetAsync 43.241 μs 0.6713 μs 0.6279 μs
Method Mean Error StdDev
HttpClient_PostJsonAsync 5.263 μs 0.0784 μs 0.0733 μs
WebApiClientCore_PostJsonAsync 13.823 μs 0.1874 μs 0.1753 μs
Refit_PostJsonAsync 45.218 μs 0.8166 μs 0.7639 μs

4 Nuget包與文檔

Nuget包

<PackageReference Include="WebApiClientCore" Version="1.0.*" />

項目地址與文檔

點擊項目鏈接,帶你GET到N種使用技能,不求star,只求提供良好建議。

https://github.com/dotnetcore/WebApiClient

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※回頭車貨運收費標準

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

疫情之後還有氣候戰役 歐盟十國環境部長公開信:復甦方案要綠色政綱

環境資訊中心綜合外電;黃鈺婷、鄒敏惠 編譯;趙家緯 審校

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※超省錢租車方案

※別再煩惱如何寫文案,掌握八大原則!

※回頭車貨運收費標準

※教你寫出一流的銷售文案?

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

網頁設計最專業,超強功能平台可客製化

流氓鄰居!新研究:中國築壩攔水重創湄公河下游國水情

摘錄自2020年4月14日自由時報報導

中國近年積極對鄰國恩威並施,手段繁多,彰顯該國地緣政治方面的野心,最新一份研究指出,中國在湄公河上游瀾滄江築壩攔水的做法,加劇湄公河下游國家越南、泰國、柬埔寨、寮國及緬甸的旱情,進一步重創其經濟。

根據《美國之音》報導,研究人員透過特殊技術建立「表面濕度指數模型」,發現自2012年中國瀾滄江糯扎渡水電站開始運作後,當局又興建了多座大壩,導致該河流自然流量受到很大限制,進而影響下游國家。

這份報告的共同作者,美國「Eyes on Earth」公司獨立研究員貝斯特(Alan Basist)表示,簡而言之,中方的說法就是在雨季時擋水、在旱季放水,試圖穩定生產水電,然而,這次研究卻找到與其說法不符的證據。

貝斯特舉去年的數據為例,2019年湄公河下游水位降至過去半世紀最低點時,上游卻有著高於平均值的表面濕度,代表該處存在高於過往同期自然流量。他說,一過中國攔水區域後,下游的泰國、越南的水平面卻低於平均值,代表中國在上游的限制加劇了下游國家的乾旱。

土地水文
生物多樣性
土地利用
國際新聞
中國新聞
中國
攔水壩
湄公河
水庫

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※推薦台中搬家公司優質服務,可到府估價

學者:野火致觀光客減少 有助控制澳洲疫情

摘錄自2020年4月13日中央社報導

一位澳洲學者說,幾個月前的森林大火雖然造成重大傷亡和損失,但減少可能染疫的觀光客到訪,意外地降低2019新型冠狀病毒(COVID-19,武漢肺炎)疫情對澳洲的衝擊。

澳洲國立大學傳染病教授柯里諾(Peter Collignon)說,要是沒有這場災難,澳洲的新型冠狀病毒疫情恐怕一發不可收拾。澳洲觀光及交通業界論壇組織(Tourism and Transport Forum)執行長奧斯蒙(Margy Osmond)表示,早在武漢肺炎疫情爆發之前,澳洲觀光業本就因為森林大火而受到重創。

澳洲衛生部最新的數據顯示,截至澳洲東部標準時間(AEST)13日下午3時止,澳洲2019冠狀病毒疾病確診病例24小時內增加46例,累計達6359例,其中61人死亡。確診人數最多的新南威爾斯州有2863個病例,約占45%。全國有36萬2000多人已接受病毒檢測。

生活環境
國際新聞
澳洲
澳洲野火
地方觀光
控制疫情
武漢肺炎
動物與大環境變遷

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計最專業,超強功能平台可客製化

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家公司費用怎麼算?

中國傳統市場照賣 澳:全球健康威脅

摘錄自2020年4月15日自由時報報導

武漢肺炎疫情被認為起源自中國傳統市場販售的野味,最早傳出疫情的武漢市華南海鮮批發市場目前仍被關閉。但另一個武漢市最大的傳統市場「白沙洲大市場」,不僅在封城期間維持基本的運作,解封後也很快就恢復疫情爆發前的熱絡景況。

為防堵疫情因市場活動二度爆發,民眾必須持有健康認證「綠碼」、量測體溫後才能進入白沙洲大市場,載貨的車輛也需經過消毒。白沙洲大市場販賣蔬菜、魚貨、冷藏雞肉與當季食品,當地攤販指出,該市場禁止宰殺雞、豬、羊等家禽畜,必須在專門的屠宰場完成宰殺後,再送至市場販賣。

澳洲總理莫里森14日指出,他難以理解世衛組織竟坐視中國的傳統市場繼續營運,並表示這不是第一次出現源自市場的病毒,稱傳統市場為「全球健康威脅」。

但世衛組織上週表示,傳統市場為中國人民重要的收入與食物來源,不支持中國關閉所有傳統市場,且中國目前只允許傳統市場銷售安全的食物,衛生水準已經提升。世衛組織特使納巴羅也於14日受訪時說,為防止下一次的全球大流行,世衛組織建議各國應該關閉「危險的」傳統市場,但也強調,世衛組織無法強制任何國家關閉市場。

生活環境
國際新聞
中國新聞
中國
武漢
傳統市場
食品安全

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※超省錢租車方案

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

※推薦台中搬家公司優質服務,可到府估價

仰賴自然卻摧毀自然 珍古德:導致病毒大爆發

摘錄自2020年4月14日自由時報報導

世界著名的英國靈長類動物學家珍古德(Jane Goodall)11日於電話訪談中指出,武漢肺炎(COVID-19)的大爆發是由於人類長期以來對自然的漠視和對動物的不尊重。

《法新社》報導,珍古德認為,病毒的大流行從很久以前就被預言了。以砍伐森林為例,動物棲地減少,不同物種被迫靠近,因而互相傳染疾病,久之,當生活空間少到牠們不得已向人類居住地接近時,人類便被傳染。她補充:「當然,野生動物的捕食也是原因之一,特別是中國和非洲。」

她進一步表示,中國禁止野生動物市場是一件好事,「希望是永久性的」,且期待亞洲其他國家能夠跟進。但珍古德也明白,在非洲會相對難以實施該禁令,因為許多民眾賴以為生,「當人們沒有其他管道養活自己和家人時,你不可能直接禁止他做(野生動物買賣)。」

土地水文
土地利用
國際新聞
珍古德
冠狀病毒
災害

本站聲明:網站內容來源環境資訊中心https://e-info.org.tw/,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※回頭車貨運收費標準

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家遵守搬運三大原則,讓您的家具不再被破壞!

HashMap解析(主要JDK1.8,附帶1.7出現的問題以及區別)

按問題的形式來吧,這些大多是我自己總結的,如有錯誤請及時指正謝謝

1.你了解HashMap么,可以說說么?

  首先,HashMap是一種數據結構,可以快速的幫我們存取數據。它的底層數據結構在1.7和1.8有了一些變化,1.7版本及以前他是數組+鏈表的形式,1.8及以後數組+鏈表+紅黑樹,如果鏈表長度大於等於8就會轉化為紅黑樹,如果長度降至6紅黑樹會轉化為鏈表紅黑樹的出現解決了因為鏈表過長導致查詢速度變慢的問題,因為鏈表的查詢時間複雜度是O(n),而紅黑樹的查詢時間複雜度是O(logn)。

2.它的數組+鏈表是怎麼實現的?

  

 

 

 這個代碼是1.8的(1.7是Entry,就是名字不一樣),其實我們每一個放進去的(key,value)到最後都會封裝成這樣的Node對象。Hashmap的數組就是以一系列這樣的Node對象構成的數組,鏈表就是把next指向下一個Node對象。

 

 

3.為什麼要有鏈表,紅黑樹?只有數組不可以么?

首先我們要知道什麼是Hash算法。

這裏放出一段官方的話:

 

Hash,一般翻譯做散列、雜湊,或音譯為哈希,是把任意長度的輸入(又叫做預映射pre-image)通過散列算法變換成固定長度的輸出,該輸出就是散列值。這種轉換是一種壓縮映射,也就是,散列值的空間通常遠小於輸入的空間,不同的輸入可能會散列成相同的輸出,所以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數。

 

簡單點來說:就是把一個大数字經過運算變為固定範圍的輸出,最簡單的算法就是對你的數組長度取模。

但是這樣就會出現一個問題,你這麼算難免會出現算出來的数字是一樣的:

比如數組長度為16,我們要放入数字1和17,那麼他們經過對數組長度取模后位置是一樣的,這樣就產生了Hash衝突。我們就可以在數組下拉出一個鏈表去存儲這個数字

4.知道哪些常見的解決hash衝突算法么?

1、開放定址法(就是往下找空餘地方)
     用開放定址法解決衝突的做法是:當衝突發生時,使用某種探查(亦稱探測)技術在散列表中形成一個探查(測)序列。沿此序列逐個單元地查找,直到找到給定 的關鍵字,或者碰到一個開放的地址(即該地址單元為空)為止(若要插入,在探查到開放的地址,則可將待插入的新結點存人該地址單元)。查找時探查到開放的 地址則表明表中無待查的關鍵字,即查找失敗。

2、 再哈希法(再進行hash直到無衝突)
再哈希法又叫雙哈希法,有多個不同的Hash函數,當發生衝突時,使用第二個,第三個,….,等哈希函數
計算地址,直到無衝突。雖然不易發生聚集,但是增加了計算時間。

3、拉鏈法(hashmap用的)

鏈地址法的基本思想是:每個哈希表節點都有一個next指針,多個哈希表節點可以用next指針構成一個單向鏈表,被分配到同一個索引上的多個結點用單向鏈表連接起來

4、建立公共溢出區: 
這種方法的基本思想是:將哈希表分為基本表和溢出表兩部分,凡是和基本表發生衝突的元素,一律填入溢出表

5.為什麼閾值就是8和6呢?中間的7是有什麼作用的呢?直接就是紅黑樹不可以么?

HashMap中有這樣一段註釋(主要看数字):

/* * Because TreeNodes are about twice the size of regular nodes, we * use them only when 鏈表s contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain 鏈表s. In * usages with well-distributed user hashCodes, tree 鏈表s are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in 鏈表s follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million */

TreeNodes佔用空間是普通Nodes的兩倍(相較於鏈表結構,鏈表只有指向下一個節點的指針,二叉樹則需要左右指針,分別指向左節點和右節點),所以只有當鏈表包含足夠多的節點時才會轉成TreeNodes(考慮到時間和空間的權衡),而是否足夠多就是由TREEIFY_THRESHOLD的值決定的。當紅黑樹中節點數變少時,又會轉成普通的鏈表。並且我們查看源碼的時候發現,鏈表長度達到8就轉成紅黑樹,當長度降到6就轉成普通鏈表。

這樣就解釋了為什麼不是一開始就將其轉換為TreeNodes,而是需要一定節點數才轉為TreeNodes,說白了就是trade-off,空間和時間的權衡。

當hashCode離散性很好的時候,樹型鏈表用到的概率非常小,因為數據均勻分佈在每個鏈表中,幾乎不會有鏈表中鏈表長度會達到閾值。但是在隨機hashCode下,離散性可能會變差,然而JDK又不能阻止用戶實現這種不好的hash算法,因此就可能導致不均勻的數據分佈。不過理想情況下隨機hashCode算法下所有鏈表中節點的分佈頻率會遵循泊松分佈,我們可以看到,一個鏈表中鏈表長度達到8個元素的概率為0.00000006,幾乎是不可能事件。這種不可能事件都發生了,說明鏈表中的節點數很多,查找起來效率不高。至於7,是為了作為緩衝,可以有效防止鏈表和樹頻繁轉換。

之所以選擇8,不是拍拍屁股決定的,而是根據概率統計決定的。由此可見,發展30年的Java每一項改動和優化都是非常嚴謹和科學的。

泊松分佈適合於描述單位時間(或空間)內隨機事件發生的次數。如某一服務設施在一定時間內到達的人數,電話交換機接到呼叫的次數,汽車站台的候客人數,機器出現的故障數,自然災害發生的次數,一塊產品上的缺陷數,顯微鏡下單位分區內的細菌分佈數等等。如果有興趣的,可以研究一下,概率是怎麼算出來的!

個人總結:

  1. 選擇8是因為空間和時間的權衡,再一個是因為鏈表中節點的分佈頻率會遵循泊松分佈,達到8的概率很小
  2. 選擇7是為了作為緩衝,可以有效防止鏈表和樹頻繁轉換
  3. 你的紅黑樹查詢時間複雜度低,但你的維持平衡的操作代價是大的,所以不會直接是紅黑樹(這一點是個人理解)

6.HashMap的初始容量,加載因子,擴容增量是多少?如果加載因子變大變小會怎麼樣?

HashMap的初始容量16,加載因子為0.75,擴容增量是原容量的1倍。如果HashMap的容量為16,一次擴容后容量為32。HashMap擴容是指元素個數(包括數組和鏈表+紅黑樹中)超過了16*0.75=12(容量×加載因子)之後開始擴容。

這個就是源碼里的聲明

//默認初始容量
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //最大容量
static final int MAXIMUM_CAPACITY = 1 << 30; //加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

加載因子越大,填滿的元素越多,空間利用率越高,但衝突的機會加大了。
反之,加載因子越小,填滿的元素越少,衝突的機會減小,但空間浪費多了(因為需要經常擴容)。

所以這是一個時間和空間的均衡。

7. 如果我默認初始大小為100,那麼元素個數到達75會擴容么?

這個問題我以前見到過,所以拿出來說一下。

首先HashMap的構造方法有四個

    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); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }
  
  public HashMap(Map<!--? extends K, ? extends V--> m) {       this.loadFactor = DEFAULT_LOAD_FACTOR;       putMapEntries(m, false);   }  

簡單點來說就是你可以自定義加載因子和初始容量。但是這個初始容量不是說你設置多少就是多少,他是會有個計算的,到最後Hashmap的容量一定是2的n次方

 

 

 簡單說一下putMapEntries

final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { //獲取該map的實際長度
        int s = m.size(); if (s > 0) { //判斷table是否初始化,如果沒有初始化
            if (table == null) { // pre-size
                /**求出需要的容量,因為實際使用的長度=容量*0.75得來的,+1是因為小數相除,基本都不會是整數,容量大小不能為小數的,後面轉換為int,多餘的小數就要被丟掉,所以+1,例如,map實際長度22,22/0.75=29.3,所需要的容量肯定為30,有人會問如果剛剛好除得整數呢,除得整數的話,容量大小多1也沒什麼影響**/
                float ft = ((float)s / loadFactor) + 1.0F; //判斷該容量大小是否超出上限。
                int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); /**對臨界值進行初始化,tableSizeFor(t)這個方法會返回大於t值的,且離其最近的2次冪,例如t為29,則返回的值是32**/
                if (t > threshold) threshold = tableSizeFor(t); } //如果table已經初始化,則進行擴容操作,resize()就是擴容。
            else if (s > threshold) resize(); //遍歷,把map中的數據轉到hashMap中。
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }

 

所以說這個答案就是不會擴容的,因為你初始它的容量是100,tableSizeFor也會自動變成128,128×0.75是93遠遠大於75.

8. HashMap中為什麼數組的長度為2的冪次方?

主要是為了計算hash值時散列性更好。

我們看一下HashMap的數組下標如何計算的

 

// 將(數組的長度-1)和hash值進行按位與操作:
i = (n - 1) & hash  // i為數組對應位置的索引 n為當前數組的大小

假定HashMap的長度為默認的16,則n – 1為15,也就是二進制的01111

可以說,Hash算法最終得到的index結果完全取決於hashCode的最後幾位。

那麼說為什麼別的数字不行呢?

假設,HashMap的長度為10,則n-1為9,也就是二進制的1001

我們來試一個hashCode:1110時,通過Hash算法得到的最終的index是8

 

再比如說:1000得到的index也是8。

也就是說,即使我們把倒數第二、三位的0、1變換,得到的index仍舊是8,說明有些index結果出現的幾率變大!

這樣,顯然不符合Hash算法均勻分佈的要求。

反觀,長度16或其他2的冪次方,Length – 1的值的二進制所有的位均為1,這種情況下,Index的結果等於hashCode的最後幾位。只要輸入的hashCode本身符合均勻分佈,Hash算法的結果就是均勻的。

一句話,HashMap的長度為2的冪次方的原因是為了減少Hash碰撞,盡量使Hash算法的結果均勻分佈。

9.put方法

在講解put方法之前,先看看hash方法,看怎麼計算哈希值的。

    static final int hash(Object key) { int h; /**先獲取到key的hashCode,然後進行移位再進行異或運算,為什麼這麼複雜,不用想肯定是為了減少hash衝突**/
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

put方法實際調用了putVal方法

    public V put(K key, V value) { /**四個參數,第一個hash值,第四個參數表示如果該key存在值,如果為null的話,則插入新的value,最後一個參數,在hashMap中沒有用,可以不用管,使用默認的即可**/
        return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //tab 哈希數組,p 該哈希桶的首節點,n hashMap的長度,i 計算出的數組下標
        Node<K,V>[] tab; Node<K,V> p; int n, i; //獲取長度並進行擴容,使用的是懶加載,table一開始是沒有加載的,等put后才開始加載
        if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /**如果計算出的該哈希桶的位置沒有值,則把新插入的key-value放到此處,此處就算沒有插入成功,也就是發生哈希衝突時也會把哈希桶的首節點賦予p**/
        if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //發生哈希衝突的幾種情況
        else { // e 臨時節點的作用, k 存放該當前節點的key 
            Node<K,V> e; K k; //第一種,插入的key-value的hash值,key都與當前節點的相等,e = p,則表示為首節點
            if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //第二種,hash值不等於首節點,判斷該p是否屬於紅黑樹的節點
            else if (p instanceof TreeNode) /**為紅黑樹的節點,則在紅黑樹中進行添加,如果該節點已經存在,則返回該節點(不為null),該值很重要,用來判斷put操作是否成功,如果添加成功返回null**/ e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //第三種,hash值不等於首節點,不為紅黑樹的節點,則為鏈表的節點
            else { //遍歷該鏈表
                for (int binCount = 0; ; ++binCount) { //如果找到尾部,則表明添加的key-value沒有重複,在尾部進行添加
                    if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //判斷是否要轉換為紅黑樹結構
                        if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } //如果鏈表中有重複的key,e則為當前重複的節點,結束循環
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //有重複的key,則用待插入值進行覆蓋,返回舊值。
            if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //到了此步驟,則表明待插入的key-value是沒有key的重複,因為插入成功e節點的值為null //修改次數+1
        ++modCount; //實際長度+1,判斷是否大於臨界值,大於則擴容
        if (++size > threshold) resize(); afterNodeInsertion(evict); //添加成功
        return null; }

大概如下幾步:

①. 判斷鍵值對數組table[i]是否為空或為null,否則執行resize()進行擴容,初始容量是16;

②. 根據鍵值key計算hash值得到插入的數組索引i,如果table[i]==null,直接新建節點添加,轉向⑥,如果table[i]不為空,轉向③;

③. 判斷table[i]的首個元素是否和key一樣,如果相同直接覆蓋value,否則轉向④,這裏的相同指的是hashCode以及equals;

④. 判斷table[i] 是否為TreeNode,即table[i] 是否是紅黑樹,如果是紅黑樹,遍歷發現該key不存在  則直接在樹中插入鍵值對;遍歷發現key已經存在直接覆蓋value即可;

⑤. 如果table[i] 不是TreeNode則是鏈表節點,遍歷發現該key不存在,則先添加在鏈表結尾, 判斷鏈表長度是否大於8,大於8的話把鏈錶轉換為紅黑樹;遍歷發現key已經存在直接覆蓋value即可;

⑥. 插入成功后,判斷實際存在的鍵值對數量size是否超多了最大容量threshold,如果超過,進行擴容。

10.resize方法

何時進行擴容?

HashMap使用的是懶加載,構造完HashMap對象后,只要不進行put 方法插入元素之前,HashMap並不會去初始化或者擴容table。

當首次調用put方法時,HashMap會發現table為空然後調用resize方法進行初始化
,當添加完元素后,如果HashMap發現size(元素總數)大於threshold(閾值),則會調用resize方法進行擴容

    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; //old的長度
        int oldCap = (oldTab == null) ? 0 : oldTab.length; //old的臨界值
        int oldThr = threshold; //初始化new的長度和臨界值
        int newCap, newThr = 0; //oldCap > 0也就是說不是首次初始化,因為hashMap用的是懶加載
        if (oldCap > 0) { //大於最大值
            if (oldCap >= MAXIMUM_CAPACITY) { //臨界值為整數的最大值
                threshold = Integer.MAX_VALUE; return oldTab; } //標記##,其它情況,擴容兩倍,並且擴容后的長度要小於最大值,old長度也要大於16
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //臨界值也擴容為old的臨界值2倍
                newThr = oldThr << 1; } /**如果oldCap<0,但是已經初始化了,像把元素刪除完之後的情況,那麼它的臨界值肯定還存在, 如果是首次初始化,它的臨界值則為0 **/
        else if (oldThr > 0) newCap = oldThr; //首次初始化,給與默認的值
        else { newCap = DEFAULT_INITIAL_CAPACITY; //臨界值等於容量*加載因子
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } //此處的if為上面標記##的補充,也就是初始化時容量小於默認值16的,此時newThr沒有賦值
        if (newThr == 0) { //new的臨界值
            float ft = (float)newCap * loadFactor; //判斷是否new容量是否大於最大值,臨界值是否大於最大值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //把上面各種情況分析出的臨界值,在此處真正進行改變,也就是容量和臨界值都改變了。
        threshold = newThr; //表示忽略該警告
        @SuppressWarnings({"rawtypes","unchecked"}) //初始化
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //賦予當前的table
        table = newTab; //此處自然是把old中的元素,遍歷到new中
        if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { //臨時變量
                Node<K,V> e; //當前哈希桶的位置值不為null,也就是數組下標處有值,因為有值表示可能會發生衝突
                if ((e = oldTab[j]) != null) { //把已經賦值之後的變量置位null,當然是為了好回收,釋放內存
                    oldTab[j] = null; //如果下標處的節點沒有下一個元素
                    if (e.next == null) //把該變量的值存入newCap中,e.hash & (newCap - 1)並不等於j
                        newTab[e.hash & (newCap - 1)] = e; //該節點為紅黑樹結構,也就是存在哈希衝突,該哈希桶中有多個元素
                    else if (e instanceof TreeNode) //把此樹進行轉移到newCap中
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { /**此處表示為鏈表結構,同樣把鏈錶轉移到newCap中,就是把鏈表遍歷后,把值轉過去,在置位null**/ Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } //返回擴容后的hashMap
        return newTab; }

其實主要就是兩步:1.創建新的數組 2.複製元素

但是在新的下標位置計算上1.8做了很大的優化,後面會說到。

11.get方法

    public V get(Object key) { Node<K,V> e; 9 //調用getNode方法來完成的
        return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { //first 頭結點,e 臨時變量,n 長度,k key
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //頭結點也就是數組下標的節點
        if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //如果是頭結點,則直接返回頭結點
            if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; //不是頭結點
            if ((e = first.next) != null) { //判斷是否是紅黑樹結構
                if (first instanceof TreeNode) //去紅黑樹中找,然後返回
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { //鏈表節點,一樣遍歷鏈表,找到該節點並返回
                    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //找不到,表示不存在該節點
        return null; }

主要就是利用equals和hashcode方法找到並返回

12.HashMap在JDK1.7和1.8除了數據結構的區別

(1)插入數據方式不同:

JDK1.7用的是頭插法,而JDK1.8及之後使用的都是尾插法,那麼他們為什麼要這樣做呢?因為JDK1.7認為最新插入的應該會先被用到,所以用了頭插法,但當採用頭插法時會容易出現逆序且環形鏈表死循環問題。但是在JDK1.8之後是因為加入了紅黑樹使用尾插法,能夠避免出現逆序且鏈表死循環的問題。

  說一下為什麼會產生死循環問題:

  問題出現在了這個移動元素的transfer方法里

  

 主要問題就出在了這行代碼上

Entry<K,V> next = e.next

如果兩個線程A,B都要對這個map進行擴容

A和B都已經創建了新的數組,假設線程A在執行到Entry < K,V > next = e.next之後,cpu時間片用完了,這時變量e指向節點a,變量next指向節點b。

此時A的狀態:e=a ,next=b

線程B繼續執行,很不巧,a、b、c節點rehash之後又是在同一個位置,開始移動節點, 因為頭插法,複製后順序是反的,結束后B的狀態:

 

 

 此時A開始執行,此時變量e指向節點a,變量next指向節點b,開始執行循環體的剩餘邏輯

if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next;

執行到

newTable[i] = e;

此時A的狀態

 

執行到

e = next;

 

此時e=b

再執行一波循環,Entry<K,V> next = e.next 但是此時b的next是a,就出現了死循環問題

 

 

(2)擴容后數據存儲位置的計算方式也不一樣:

在JDK1.7的時候是重新計算數組下標

而在JDK1.8的時候直接用了JDK1.7的時候計算的規律,也就是擴容前的原始位置+擴容的大小值=JDK1.8的計算方式,而不再是JDK1.7的那種異或的方法。但是這種方式就相當於只需要判斷Hash值的新增參与運算的位是0還是1就直接迅速計算出了擴容后的儲存方式。

就比如說:數組大小是4,hash算法是對長度取模

 

 擴容后是這樣的

我們可以把這三個數的二進制和擴容后的length-1進行按位與,可以看到只有数字5新增位為1

 

 

 

 因此,我們在擴充HashMap的時候,不需要像JDK1.7的實現那樣重新計算hash,只需要看看原來的hash值新增的那個bit是1還是0就好了,是0的話索引沒變,是1的話索引變成“原索引+oldCap”

(3)擴容的條件不同,1.7需要容量超過閾值且發生hash衝突,1.8超過閾值即會擴容

(4)JDK1.7的時候是先進行擴容後進行插入,而在JDK1.8的時候則是先插入後進行擴容

(5)1.8中沒有區分鍵為null的情況,而1.7版本中對於鍵為null的情況調用putForNullKey()方法。但是兩個版本中如果鍵為null,那麼調用hash()方法得到的都將是0,所以鍵為null的元素都始終位於哈希表table【0】中。

(6)jdk1.7中當哈希表為空時,會先調用inflateTable()初始化一個數組;而1.8則是直接調用resize()擴容

(7)jdk1.7中的hash函數對哈希值的計算直接使用key的hashCode值,而1.8中則是採用key的hashCode異或上key的hashCode進行無符號右移16位的結果,避免了只靠低位數據來計算哈希時導致的衝突,計算結果由高低位結合決定,使元素分佈更均勻

13、HashMap是線程安全的么?如果想線程安全怎麼辦?

不是線程安全的,多線程下會出現死循環和put操作時可能導致元素丟失

死循環原因:上邊已經分析過了

丟失原因:當多個線程同時執行addEntry(hash,key ,value,i)時,如果產生哈希碰撞,導致兩個線程得到同樣的bucketIndex去存儲,就可能會發生元素覆蓋丟失的情況

 

想實現線程安全的解決方法:

1.使用Hashtable 類,Hashtable 是線程安全的(不建議用,就是利用了synchronized進行加鎖);

2.使用併發包下的java.util.concurrent.ConcurrentHashMap,ConcurrentHashMap實現了更高級的線程安全;

3.或者使用synchronizedMap() 同步方法包裝 HashMap object,得到線程安全的Map,並在此Map上進行操作。

 

參考:

https://blog.csdn.net/m0_37914588/article/details/82287191

https://www.jianshu.com/p/7cf2d6f1096b

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

※教你寫出一流的銷售文案?

※廣告預算用在刀口上,台北網頁設計公司幫您達到更多曝光效益

※回頭車貨運收費標準

※別再煩惱如何寫文案,掌握八大原則!

※超省錢租車方案

※產品缺大量曝光嗎?你需要的是一流包裝設計!

※推薦台中搬家公司優質服務,可到府估價

程序員需要了解的硬核知識之二進制

我們都知道,計算機的底層都是使用二進制數據進行數據流傳輸的,那麼為什麼會使用二進製表示計算機呢?或者說,什麼是二進制數呢?在拓展一步,如何使用二進制進行加減乘除?二進制數如何表示負數呢?本文將一一為你揭曉。

為什麼用二進製表示

我們大家知道,計算機內部是由IC电子元件組成的,其中 CPU內存 也是 IC 电子元件的一種,CPU和內存圖如下

CPU 和 內存使用IC电子元件作為基本單元,IC电子元件有不同種形狀,但是其內部的組成單元稱為一個個的引腳。有人說CPU 和 內存內部都是超大規模集成電路,其實IC 就是集成電路(Integrated Circuit)。

IC元件兩側排列的四方形塊就是引腳,IC的所有引腳,只有兩種電壓: 0V5V,IC的這種特性,也就決定了計算機的信息處理只能用 0 和 1 表示,也就是二進制來處理。一個引腳可以表示一個 0 或 1 ,所以二進制的表示方式就變成 0、1、10、11、100、101等,雖然二進制數並不是專門為 引腳 來設計的,但是和 IC引腳的特性非常吻合。

計算機的最小集成單位為 ,也就是 比特(bit),二進制數的位數一般為 8位、16位、32位、64位,也就是 8 的倍數,為什麼要跟 8 扯上關係呢? 因為在計算機中,把 8 位二進制數稱為 一個字節, 一個字節有 8 位,也就是由 8個bit構成。

為什麼1個字節等於8位呢?因為 8 位能夠涵蓋所有的字符編碼,這個記住就可以了。

字節是最基本的計量單位,位是最小單位。

用字節處理數據時,如果数字小於存儲數據的字節數 ( = 二進制的位數),那麼高位就用 0 填補,高位和數學的數字錶示是一樣的,左側表示高位,右側表示低位。比如 這個六位數用二進制數來表示就是 100111,只有6位,高位需要用 0 填充,填充完后是 00100111,佔一個字節,如果用 16 位表示 就是 0000 0000 0010 0111佔用兩個字節。

我們一般口述的 32 位和 64位的計算機一般就指的是處理位數,32 位一次可以表示 4個字節,64位一次可以表示8個字節的二進制數。

我們一般在軟件開發中用十進制數表示的邏輯運算等,也會被計算機轉換為二進制數處理。對於二進制數,計算機不會區分他是 圖片、音頻文件還是数字,這些都是一些數據的結合體。

什麼是二進制數

那麼什麼是二進制數呢?為了說明這個問題,我們先把 00100111 這個數轉換為十進制數看一下,二進制數轉換為十進制數,直接將各位置上的值 * 位權即可,那麼我們將上面的數值進行轉換

也就是說,二進制數代表的 00100111 轉換成十進制就是 39,這個 39 並不是 3 和 9 兩個数字連着寫,而是 3 * 10 + 9 * 1,這裏面的 10 , 1 就是位權,以此類推,上述例子中的位權從高位到低位依次就是 7 6 5 4 3 2 1 0 。這個位權也叫做次冪,那麼最高位就是2的7次冪,2的6次冪 等等。二進制數的運算每次都會以2為底,這個2 指得就是基數,那麼十進制數的基數也就是 10 。在任何情況下位權的值都是 數的位數 – 1,那麼第一位的位權就是 1 – 1 = 0, 第二位的位權就睡 2 – 1 = 1,以此類推。

那麼我們所說的二進制數其實就是 用0和1兩個数字來表示的數,它的基數為2,它的數值就是每個數的位數 * 位權再求和得到的結果,我們一般來說數值指的就是十進制數,那麼它的數值就是 3 * 10 + 9 * 1 = 39。

移位運算和乘除的關係

在了解過二進制之後,下面我們來看一下二進制的運算,和十進制數一樣,加減乘除也適用於二進制數,只要注意逢 2 進位即可。二進制數的運算,也是計算機程序所特有的運算,因此了解二進制的運算是必須要掌握的。

首先我們來介紹移位 運算,移位運算是指將二進制的數值的各個位置上的元素坐左移和右移操作,見下圖

上述例子中還是以 39 為例,我們先把十進制的39 轉換為二進制的 0010 0111,然後向左移位 << 一個字節,也就變成了 0100 1110,那麼再把此二進制數轉換為十進制數就是上面的78, 十進制的78 竟然是 十進制39 的2倍關係。我們在讓 0010 0111 左移兩位,也就是 1001 1100,得出來的值是 156,相當於擴大了四倍!

因此你可以得出來此結論,左移相當於是數值擴大的操作,那麼右移 >> 呢?按理說右移應該是縮小 1/2,1/4 倍,但是39 縮小二倍和四倍不就變成小數了嗎?這個怎麼表示呢?請看下一節

便於計算機處理的補數

剛才我們沒有介紹右移的情況,是因為右移之後空出來的高位數值,有 0 和 1 兩種形式。要想區分什麼時候補0什麼時候補1,首先就需要掌握二進制數表示負數的方法。

二進制數中表示負數值時,一般會把最高位作為符號來使用,因此我們把這個最高位當作符號位。 符號位是 0 時表示正數,是 1 時表示 負數。那麼 -1 用二進制數該如何表示呢?可能很多人會這麼認為: 因為 1 的二進制數是 0000 0001,最高位是符號位,所以正確的表示 -1 應該是 1000 0001,但是這個答案真的對嗎?

計算機世界中是沒有減法的,計算機在做減法的時候其實就是在做加法,也就是用加法來實現的減法運算。比如 100 – 50 ,其實計算機來看的時候應該是 100 + (-50),為此,在表示負數的時候就要用到二進制補數,補數就是用正數來表示的負數。

為了獲得補數,我們需要將二進制的各數位的數值全部取反,然後再將結果 + 1 即可,先記住這個結論,下面我們來演示一下。

具體來說,就是需要先獲取某個數值的二進制數,然後對二進制數的每一位做取反操作(0 —> 1 , 1 —> 0),最後再對取反后的數 +1 ,這樣就完成了補數的獲取。

補數的獲取,雖然直觀上不易理解,但是邏輯上卻非常嚴謹,比如我們來看一下 1 – 1 的這個過程,我們先用上面的這個 1000 0001(它是1的補數,不知道的請看上文,正確性先不管,只是用來做一下計算)來表示一下

奇怪,1 – 1 會變成 130 ,而不是0,所以可以得出結論 1000 0001 表示 -1 是完全錯誤的。

那麼正確的該如何表示呢?其實我們上面已經給出結果了,那就是 1111 1111,來論證一下它的正確性

我們可以看到 1 – 1 其實實際上就是 1 + (-1),對 -1 進行上面的取反 + 1 后變為 1111 1111, 然後與 1 進行加法運算,得到的結果是九位的 1 0000 0000,結果發生了溢出,計算機會直接忽略掉溢出位,也就是直接拋掉 最高位 1 ,變為 0000 0000。也就是 0,結果正確,所以 1111 1111 表示的就是 -1 。

所以負數的二進製表示就是先求其補數,補數的求解過程就是對原始數值的二進制數各位取反,然後將結果 + 1

當然,結果不為 0 的運算同樣也可以通過補數求得正確的結果。不過,有一點需要注意,當運算結果為負的時候,計算結果的值也是以補數的形式出現的,比如 3 – 5 這個運算,來看一下解析過程

3 – 5 的運算,我們按着上面的思路來過一遍,計算出來的結果是 1111 1110,我們知道,這個數值肯定表示負數,但是負數無法直接用十進製表示,需要對其取反+ 1,算出來的結果是 2,因為 1111 1110的高位是 1,所以最終的結果是 -2。

編程語言的數據類型中,有的可以處理負數,有的不可以。比如 C語言中不能處理負數的 unsigned short類型,也有能處理負數的short類型 ,都是兩個字節的變量,它們都有 2 的十六次冪種值,但是取值範圍不一樣,short 類型的取值範圍是 -32768 – 32767 , unsigned short 的取值範圍是 0 – 65536。

仔細思考一下補數的機制,就能明白 -32768 比 32767 多一個數的原因了,最高位是 0 的正數有 0 ~ 32767 共 32768 個,其中包括0。最高位是 1 的負數,有 -1 ~ -32768 共 32768 個,其中不包含0。0 雖然既不是正數也不是負數,但是考慮到其符號位,就將其歸為了正數。

算數右移和邏輯右移的區別

在了解完補數后,我們重新考慮一下右移這個議題,右移在移位后空出來的最高位有兩種情況 0 和 1。當二進制數的值表示圖形模式而非數值時,移位后需要在最高位補0,類似於霓虹燈向右平移的效果,這就被稱為邏輯右移

將二進制數作為帶符號的數值進行右移運算時,移位后需要在最高位填充移位前符號位的值( 0 或 1)。這就被稱為算數右移。如果數值使用補數表示的負數值,那麼右移后在空出來的最高位補 1,就可以正確的表示 1/2,1/4,1/8等的數值運算。如果是正數,那麼直接在空出來的位置補 0 即可。

下面來看一個右移的例子。將 -4 右移兩位,來各自看一下移位示意圖

如上圖所示,在邏輯右移的情況下, -4 右移兩位會變成 63, 顯然不是它的 1/4,所以不能使用邏輯右移,那麼算數右移的情況下,右移兩位會變為 -1,顯然是它的 1/4,故而採用算數右移。

那麼我們可以得出來一個結論:左移時,無論是圖形還是數值,移位后,只需要將低位補 0 即可;右移時,需要根據情況判斷是邏輯右移還是算數右移。

下面介紹一下符號擴展:將數據進行符號擴展是為了產生一個位數加倍、但數值大小不變的結果,以滿足有些指令對操作數位數的要求,例如倍長於除數的被除數,再如將數據位數加長以減少計算過程中的誤差。

以8位二進製為例,符號擴展就是指在保持值不變的前提下將其轉換成為16位和32位的二進制數。將0111 1111這個正的 8位二進制數轉換成為 16位二進制數時,很容易就能夠得出0000 0000 0111 1111這個正確的結果,但是像 1111 1111這樣的補數來表示的數值,該如何處理?直接將其表示成為1111 1111 1111 1111就可以了。也就是說,不管正數還是補數表示的負數,只需要將 0 和 1 填充高位即可。

邏輯運算的竅門

掌握邏輯和運算的區別是:將二進制數表示的信息作為四則運算的數值來處理就是算數,像圖形那樣,將數值處理為單純的 01 的羅列就是邏輯

計算機能夠處理的運算,大體可分為邏輯運算和算數運算,算數運算指的是加減乘除四則運算;邏輯運算指的是對二進制各個數位的 0 和 1分別進行處理的運算,包括邏輯非(NOT運算)、邏輯與(AND運算)、邏輯或(OR運算)和邏輯異或(XOR運算)四種。

  • 邏輯非 指的是將 0 變成 1,1 變成 0 的取反操作
  • 邏輯與 指的是”兩個都是 1 時,運算結果才是 1,其他情況下是 0″
  • 邏輯或 指的是”至少有一方是 1 時,運算結果為 1,其他情況下運算結果都是 0″
  • 邏輯異或 指的是 “其中一方是 1,另一方是 0時運算結果才是 1,其他情況下是 0”

掌握邏輯運算的竅門,就是要摒棄二進制數表示數值這一個想法。大家不要把二進制數表示的值當作數值,應該把它看成是 開關上的 ON/OFF

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計最專業,超強功能平台可客製化

※自行創業缺乏曝光? 網頁設計幫您第一時間規劃公司的形象門面

※回頭車貨運收費標準

※推薦評價好的iphone維修中心

※教你寫出一流的銷售文案?

台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

台中搬家公司費用怎麼算?