哈希表
目的
提供一個(gè)存儲(chǔ)結(jié)構(gòu), 其中存儲(chǔ)的是Key-Value對(duì), Key和Value可以是任意的類型
類似于數(shù)組: 可以使用數(shù)組的下標(biāo)索引(數(shù)字!!!!)去訪問(wèn)存儲(chǔ)的數(shù)據(jù)!
Key可以是任何類型的! arr[名字] = 人的身份對(duì)象
; test = abc["fff"] xxxx
類似于f(x) = y這樣的函數(shù), 我們可以設(shè)置任意的f(x1) = y1, 或者f(x2) = y2.
或者訪問(wèn): a = f(x1)
也就是支持四種操作: 增刪改查!
增加, 查詢,修改和刪除操作的時(shí)間復(fù)雜度都近似于 O(1) , 也不依賴于插入的順序. 也就是隨機(jī)訪問(wèn)(想訪問(wèn)哪個(gè)數(shù)據(jù)就馬上訪問(wèn)哪個(gè)數(shù)據(jù)!)
存儲(chǔ)在哈希表里的數(shù)據(jù)沒(méi)有順序!!! 不可以對(duì)哈希表進(jìn)行排序
有什么樣的屬性!
支持什么樣的操作!
HashMap<String, String> genderMap = new HashMap<String, String>();
// 增
genderMap.put("alex", "male");
genderMap.put("CC", "female");
// 查
if (genderMap.containsKey("alex")) {
System.out.println(genderMap.get("alex"));
}
// 改
genderMap.put("CC", "male"); // 覆蓋掉
// 刪
genderMap.remove("CC");
數(shù)組和哈希表不一樣的點(diǎn)
數(shù)組的key只支持?jǐn)?shù)字的, 但是哈希表支持更多的數(shù)據(jù)類型
數(shù)組在中間插入數(shù)據(jù)操作, 時(shí)間復(fù)雜度一般不是O(1)
基本實(shí)現(xiàn)原理
把任意的Key值轉(zhuǎn)換成數(shù)字, 然后作為數(shù)組的下標(biāo), 然后把Value存儲(chǔ)在數(shù)組下標(biāo)對(duì)應(yīng)位置上
ValueClass[] array = new ValueClass[size
比如:
修改操作
String key = someString();
int index = hash(key);
array[index] = value;
訪問(wèn)操作
int index = hash(key);
ValueClass value = array[index];
棧
一個(gè)數(shù)據(jù)結(jié)構(gòu), 用于存儲(chǔ)數(shù)據(jù). 支持兩種操作:
- 插入數(shù)據(jù) (push);
- 取出數(shù)據(jù) (pop); 獲得數(shù)據(jù), 同時(shí)把數(shù)據(jù)從棧中刪除
所有操作的時(shí)間復(fù)雜度度為O(1)
最重要的是, 哈希表可以隨機(jī)訪問(wèn). 但是棧對(duì)數(shù)據(jù)的訪問(wèn)順序有規(guī)定. 遵循一個(gè)規(guī)則: 先進(jìn)后出, 后進(jìn)先出. 也就是只能訪問(wèn)當(dāng)最近放進(jìn)到棧里面的那個(gè)數(shù)據(jù)!
Stack<Number> stack = new Stack<Number>();
stack.push(3);
stack.push(5);
stack.push(7);
System.out.println(stack.pop()); // 5
System.out.println(stack.pop()); // 3
// 只看頂部數(shù)據(jù)，但是不刪除
stack.peek();
// 檢查是否為空
stack.empty();
實(shí)例
- 函數(shù)調(diào)用棧
function f1() {
f2()
code...
}
function f2() {
f3()
code....
}
f1(); -> f2(); -> f3
// 調(diào)用f1中, 會(huì)把f1的狀態(tài),裝入棧中, 調(diào)用f2
- 深度優(yōu)先搜索, 漢諾塔, 括號(hào)平衡檢查, 表達(dá)式求值...
隊(duì)列
一個(gè)類似于棧的數(shù)據(jù)結(jié)構(gòu), 用于存儲(chǔ)數(shù)據(jù), 同樣支持兩種操作:
- 插入數(shù)據(jù) (push);
- 取出數(shù)據(jù) (pop); 獲得數(shù)據(jù), 同時(shí)從隊(duì)列中刪除
所有操作的時(shí)間復(fù)雜度為O(1)
隊(duì)列遵循一個(gè)規(guī)則: 先進(jìn)先出, 后進(jìn)后出. 也就是從隊(duì)列中取出數(shù)據(jù)的順序和放進(jìn)去的順序是一樣的!
實(shí)例
- 消息隊(duì)列
- 廣度優(yōu)先搜索
// 隊(duì)列
Queue<Integer> queue = new LinkedList<>();
queue.add(3);
queue.add(5);
System.out.println("queue, " + queue.poll()); // 3
System.out.println("queue, " + queue.poll()); // 5
Integer first_of_queue = queue.peek();
queue.isEmpty();
