前言
本周是學(xué)習(xí)java的第五周守屉，粗略的學(xué)習(xí)了一下hashmap的底層實現(xiàn)原理惑艇。
參考教程：
本周學(xué)習(xí)要點：
1.ArrayList在查詢較多時使用到，一般較多使用到它拇泛。
2.LinkList在增刪較多時使用到滨巴。
3.Vector線程安全，但相對的效率低俺叭，而且并不是安全就是好的恭取。
4.HashMap是鍵值對，是map接口的實現(xiàn)類熄守。put方法中蜈垮，鍵不能重復(fù)，否則會覆蓋掉舊的裕照。
5.HashMap底層是結(jié)合數(shù)組和鏈表實現(xiàn)的攒发，具有數(shù)組的查詢快的優(yōu)點和鏈表的增加和刪除快的優(yōu)點
6.在jdk1.8版本后，java對HashMap做了改進(jìn)晋南，在鏈表長度大于8的時候惠猿，將后面的數(shù)據(jù)存在紅黑樹中，以加快檢索速度
7.<< >>相當(dāng)于對該數(shù)作乘或除2的操作负间，比使用符號運算速度快紊扬。
哈希表
也叫散列表，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)唉擂。也就是說餐屎，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度玩祟。這個映射函數(shù)叫做散列函數(shù)腹缩，存放記錄的數(shù)組叫做散列表。
給定表M空扎，存在函數(shù)f(key)藏鹊，對任意給定的關(guān)鍵字值key，代入函數(shù)后若能得到包含該關(guān)鍵字的記錄在表中的地址转锈，則稱表M為哈希(Hash）表盘寡，函數(shù)f(key)為哈希(Hash) 函數(shù)。
若關(guān)鍵字為k撮慨，則其值存放在f(k)的存儲位置上竿痰。由此脆粥，不需比較便可直接取得所查記錄。稱這個對應(yīng)關(guān)系f為散列函數(shù)影涉，按這個思想建立的表為散列表变隔。
對不同的關(guān)鍵字可能得到同一散列地址，即k1≠k2蟹倾，而f(k1)=f(k2)匣缘，這種現(xiàn)象稱為沖突（英語：Collision）。具有相同函數(shù)值的關(guān)鍵字對該散列函數(shù)來說稱做同義詞鲜棠。綜上所述肌厨，根據(jù)散列函數(shù)f(k)和處理沖突的方法將一組關(guān)鍵字映射到一個有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為記錄在表中的存儲位置豁陆，這種表便稱為散列表夏哭，這一映射過程稱為散列造表或散列，所得的存儲位置稱散列地址献联。
若對于關(guān)鍵字集合中的任一個關(guān)鍵字，經(jīng)散列函數(shù)映象到地址集合中任何一個地址的概率是相等的何址，則稱此類散列函數(shù)為均勻散列函數(shù)（Uniform Hash function）里逆，這就是使關(guān)鍵字經(jīng)過散列函數(shù)得到一個“隨機的地址”，從而減少沖突用爪≡海——百度百科
從圖片中很輕易看出來就是數(shù)組和鏈表的結(jié)合。
java中的hashmap會先定義一個node:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
它是Map.Entry接口的一個實現(xiàn)類偎血，其內(nèi)還有一些set诸衔，get方法和toString方法等等。然后就是數(shù)組颇玷，數(shù)組默認(rèn)是一個長度為16的數(shù)組笨农，當(dāng)其內(nèi)元素被占用超過0.75也就是12時，會擴容帖渠。對于鏈表谒亦，在鏈表長度大于8的時候，將后面的數(shù)據(jù)存在紅黑樹中空郊，紅黑樹的平均查找長度是log(n)份招，如果長度為8，平均查找長度為log(8)=3狞甚，鏈表的平均查找長度為n/2锁摔，當(dāng)長度為8時，平均查找長度為8/2=4哼审，這才有轉(zhuǎn)換成樹的必要谐腰；鏈表長度如果是小于等于6孕豹，6/2=3，而log(6)=2.6怔蚌，雖然速度也很快的巩步，但是轉(zhuǎn)化為樹結(jié)構(gòu)和生成樹的時間并不會太短。
哈希函數(shù)
在我目前理解中桦踊，java的hashmap中椅野，是將key的hashcode傳入后經(jīng)過哈希函數(shù)運算出一個數(shù)字作為該鍵值對在數(shù)組中的地址，當(dāng)數(shù)據(jù)量大時會產(chǎn)生沖突籍胯，一個均勻的哈希函數(shù)可以減少沖突但不能避免沖突竟闪，所以需要解決沖突的方法。
紅黑樹
紅黑樹就是一種平衡的二叉查找樹杖狼，說他平衡的意思是他不會變成“瘸子”炼蛤，左腿特別長或者右腿特別長。除了符合二叉查找樹的特性之外蝶涩，還具體下列的特性：
- 節(jié)點是紅色或者黑色
- 根節(jié)點是黑色
- 每個葉子的節(jié)點都是黑色的空節(jié)點（NULL）
- 每個紅色節(jié)點的兩個子節(jié)點都是黑色的理朋。
- 從任意節(jié)點到其每個葉子的所有路徑都包含相同的黑色節(jié)點。
其在c語言中的簡單定義如下:
#define RED 0 // 紅色節(jié)點
#define BLACK 1 // 黑色節(jié)點
typedef int Type;
// 紅黑樹的節(jié)點
typedef struct RBTreeNode{
unsigned char color; // 顏色(RED 或 BLACK)
Type key; // 關(guān)鍵字(鍵值)
struct RBTreeNode *left; // 左孩子
struct RBTreeNode *right; // 右孩子
struct RBTreeNode *parent; // 父結(jié)點
}Node, *RBTree;
// 紅黑樹的根
typedef struct rb_root{
Node *node;
}RBRoot;
