認(rèn)識hash
hash
就是把任意長度的輸入（又叫做預(yù)映射诱篷， pre-image），通過散列算法雳灵，變 換成固定長度的輸出棕所，該輸出就是散列值。這種轉(zhuǎn)換是一種壓縮映射悯辙，也就是琳省， 散列值的空間通常遠(yuǎn)小于輸入的空間躲撰，不同的輸入可能會散列成相同的輸出岛啸，所 以不可能從散列值來確定唯一的輸入值。簡單的說就是一種將任意長度的消息壓 縮到某一固定長度的消息摘要的函數(shù)茴肥。常用 HASH 函數(shù)：直接取余法、乘法取整 法荡灾、平方取中法瓤狐。
處理沖突方法:
1．開放尋址法；
2． 再散列法：
3． 鏈地址法(拉鏈法) 常用 hash 算法的介紹：（1)MD4（2)MD5 它對輸入仍以 512 位分組批幌，其輸 出是 4 個 32 位字的級聯(lián)（3)SHA-1 及其他犁罩。
位運算
二 進(jìn) 制
從小學(xué)一年級開始锥惋，我們就開始學(xué)加減乘除，特別是學(xué)加法的時候，剛開始算超過十的時候再芋，如果不熟練，我們會掰著手指頭數(shù)巨税，有時候恨不得把腳趾頭也加上达吞。正是因為我們一般人有十個手指頭，所以绸罗，從我們老老意推。。珊蟀。祖先開始就 用十進(jìn)制菊值。那計算機(jī)怎么辦？計算機(jī)又沒十個手指頭。自然界要找出有十種狀態(tài) 的東西很難腻窒，但是只有兩種狀態(tài)的東西或者現(xiàn)象還是很容易的昵宇，所以計算機(jī)中要用二進(jìn)制。?
逢十進(jìn)一儿子，意味著至少兩點瓦哎，1，每個位上的數(shù)字不能超過 10典徊，最大只能到 9杭煎，第二，如果某個位上的數(shù)字因為運算超過了 10卒落，怎么辦羡铲？往高位進(jìn)位。那么 二進(jìn)制也是一樣的儡毕，不能說你二進(jìn)制比較二也切，規(guī)則就不一樣了，基本法還是要遵 守的腰湾。所以二進(jìn)制里同樣要遵循：1雷恃，每個位上的數(shù)字不能超過 2，最大只能到 1费坊， 第二倒槐，如果某個位上的數(shù)字因為運算超過了 2，怎么辦附井？往高位進(jìn)位讨越。
?
?常用位運算?
位與 &(1&1=10&0=01&0=0)
位或 | (1|1=10|0=01|0=1)
位非 ~(~1=0 ~0=1)
位異或 ^(1^1=01^0=1 0^0=0)
有符號右移>>(若正數(shù),高位補(bǔ) 0,負(fù)數(shù),高位補(bǔ) 1)
有符號左移<<
無符號右移>>>(不論正負(fù),高位均補(bǔ) 0)
有趣的取模性質(zhì)：取模 a%(2^n) 等價于 a&(2^n-1)，所以在 map 里的數(shù) 組個數(shù)一定是 2 的乘方數(shù)永毅，計算 key 值在哪個元素中的時候把跨，就用位運算來快速定位。??
/*
* 位運算* */
public class IntToBinary {
public static void main(String[] args)throws UnsupportedEncodingException {
System.out.println("the 4 is : " + Integer.toBinaryString(4));
System.out.println("the 6 is : " + Integer.toBinaryString(6));
//位與&(真真為真 真假為假 假假為假)
? ? ? ? System.out.println("the 4&6 is : " + Integer.toBinaryString(6&4));
//位或|(真真為真 真假為真 假假為假)
? ? ? ? System.out.println("the 4|6 is : " + Integer.toBinaryString(6|4));
//位非~
? ? ? ? System.out.println("the ~4 is : " + Integer.toBinaryString(~4));
//位異或^(真真為假 真假為真 假假為假)
? ? ? ? System.out.println("the 4^6 is : " + Integer.toBinaryString(6^4));
//有符號右移>>(若正數(shù),高位補(bǔ)0,負(fù)數(shù),高位補(bǔ)1)
? ? ? ? System.out.println("the 4>>1 is : " + Integer.toBinaryString(4>>1));
//有符號左移<<(若正數(shù),高位補(bǔ)0,負(fù)數(shù),高位補(bǔ)1)
? ? ? ? System.out.println("the 4<<1 is : " + Integer.toBinaryString(4<<1));
//無符號右移>>>(不論正負(fù),高位均補(bǔ)0)
? ? ? ? System.out.println("the 234567 is : " + Integer.toBinaryString(234567));
System.out.println("the 234567>>>4 is : " + Integer.toBinaryString(234567>>>4));
//無符號右移>>>(不論正負(fù),高位均補(bǔ)0)
? ? ? ? System.out.println("the -4 is : " + Integer.toBinaryString(-4));
System.out.println("the -4>>>4 is : " + Integer.toBinaryString(-4>>>4));
System.out.println(Integer.parseInt(Integer.toBinaryString(-4>>>4),2));
//取模a % (2^n) 等價于a & (2^n - 1)
? ? ? ? System.out.println("the 345 % 16 is : " + (345%16)+" or "+(345&(16-1)));
System.out.println("Mark hashCode is : "+"Mark".hashCode()+"="
? ? ? ? ? ? ? +Integer.toBinaryString("Mark".hashCode()));
System.out.println("Bill hashCode is : "+"Bill".hashCode()+"="
? ? ? ? ? ? ? +Integer.toBinaryString("Bill".hashCode()));
}
}
位運算運用場景?
Java 中的類修飾符沼死、成員變量修飾符着逐、方法修飾符，比如 Class 類中
Java 容器中的 HashMap 和 ConcurrentHashMap 的實現(xiàn)
權(quán)限控制或者商品屬性 簡單可逆加密意蛀，比如異或運算(1^1=0 ;0^1=1)
實戰(zhàn)：將位運算用在權(quán)限控制耸别、商品屬性上
/**
* 位運算的運用-權(quán)限控制,add,query,modify,del
*/
public class Permission {
private static final int ALLOW_SELECT =1<<0;
private static final int ALLOW_INSERT =1<<1;
private static final int ALLOW_UPDATE =1<<2;
private static final int ALLOW_DELETE =1<<3;
//當(dāng)前的權(quán)限狀態(tài)
? ? private int flag;
public void setPermission(int permission){
flag = permission;
}
/*增加權(quán)限,可以一項或者多項*/
? ? public void addPermission(int permission){
flag =flag|permission;
}
/*刪除權(quán)限,可以一項或者多項*/
? ? public void disablePermission(int permission){
flag =flag&~permission;
}
/*是否擁有某些權(quán)限*/
? ? public boolean isAllow(int permission){
return (flag&permission)==permission;
}
/*是否不擁有某些權(quán)限*/
? ? public boolean isNotAllow(int permission){
return (flag&permission)==0;
}
public static void main(String[] args) {
int flag =15;
Permission permission =new Permission();
permission.setPermission(flag);
permission.disablePermission(ALLOW_DELETE|ALLOW_INSERT);
System.out.println("ALLOW_SELECT="+permission.isAllow(ALLOW_SELECT));
System.out.println("ALLOW_INSERT="+permission.isAllow(ALLOW_INSERT));
System.out.println("ALLOW_UPDATE="+permission.isAllow(ALLOW_UPDATE));
System.out.println("ALLOW_DELETE="+permission.isAllow(ALLOW_DELETE));
}
}
使用位運算的優(yōu)劣勢：
節(jié)省很多代碼量、效率高县钥、屬性變動影響小太雨、不直觀?
為什么要使用ConcurrentHashMap
JDK1.7中HashMap死循環(huán)分析
在多線程環(huán)境下，使用 HashMap 進(jìn)行 put 操作會引起死循環(huán)囊扳，導(dǎo)致 CPU 利 用率接近 100%，HashMap 在并發(fā)執(zhí)行 put 操作時會引起死循環(huán)狭瞎，是因為多線程 會導(dǎo)致 HashMap 的 Entry 鏈表?形成環(huán)形數(shù)據(jù)結(jié)構(gòu)，一旦形成環(huán)形數(shù)據(jù)結(jié)構(gòu)搏予， Entry 的 next 節(jié)點永遠(yuǎn)不為空熊锭， 就會產(chǎn)生死循環(huán)獲取 Entry。
那么這個死循環(huán)是如何生成的呢雪侥？我們來仔細(xì)分析下碗殷。
HashMap擴(kuò)容流程
原理
引發(fā)死循環(huán)，是在 HashMap 的擴(kuò)容操作中速缨。
正常的擴(kuò)容操作是這個流程锌妻。HashMap 的擴(kuò)容在 put 操作中會觸發(fā)擴(kuò)容旬牲，主要是三個方法：
?
?
?
綜合來說原茅，HashMap 一次擴(kuò)容的過程：
1、取當(dāng)前 table 的 2 倍作為新 table 的大小
2擂橘、根據(jù)算出的新 table 的大小 new 出一個新的 Entry 數(shù)組來晌区，名為 newTable
3、輪詢原 table 的每一個位置通贞，將每個位置上連接的 Entry朗若，算出在新 table 上的位置，并以鏈表形式連接
4、原 table 上的所有 Entry 全部輪詢完畢之后，意味著原 table 上面的所有 Entry 已經(jīng)移到了新的 table 上夯辖，HashMap 中的 table 指向 newTable
實例
現(xiàn)在 hashmap 中有三個元素，Hash 表的 size=2, 所以 key=3,7,5，在 mod2 以后都沖突在 table[1]這里了近速。
?
按照方法中的代碼
?
對 table[1]中的鏈表來說，進(jìn)入 while 循環(huán)，此時 e=key(3)蛮瞄，那么 next=key(7)谆扎， 經(jīng)過計算重新定位 e=key(3)在新表中的位置挂捅，并把 e=key(3)掛在 newTable[3]的位 置
?
?
這樣循環(huán)下去，將 table[1]中的鏈表循環(huán)完成后堂湖，于是 HashMap 就完成了擴(kuò)容
?
并發(fā)下的擴(kuò)容
上面都是單線程下的擴(kuò)容闲先，當(dāng)多線程進(jìn)行擴(kuò)容時，會是什么樣子呢无蜂？ 初始的 HashM 還是：
?
我們現(xiàn)在假設(shè)有兩個線程并發(fā)操作伺糠，都進(jìn)入了擴(kuò)容操作，
?我們以顏色進(jìn)行區(qū)分兩個線程斥季。
我們假設(shè)训桶，線程 1 執(zhí)行到 Entrynext=e.next;時 被操作系統(tǒng)調(diào)度掛起了，而線程 2 執(zhí)行完成了擴(kuò)容操作
?
于是酣倾，在線程 1,2 看來舵揭，就應(yīng)該是這個樣子
?
接下來，線程 1 被調(diào)度回來執(zhí)行：
1）
?
2）
?
3）
?
4）
?
?5）
?
6）
?
7）
?
循環(huán)列表產(chǎn)生后躁锡，一旦線程 1 調(diào)用 get（11,15 之類的元素）時午绳，就會進(jìn)入一 個死循環(huán)的情況，將 CPU 的消耗到 100%映之。
總結(jié)?
HashMap 之所以在并發(fā)下的擴(kuò)容造成死循環(huán)拦焚，是因為蜡坊，多個線程并發(fā)進(jìn)行 時，因為一個線程先期完成了擴(kuò)容耕漱，將原 Map 的鏈表重新散列到自己的表中算色， 并且鏈表變成了倒序，后一個線程再擴(kuò)容時螟够，又進(jìn)行自己的散列灾梦，再次將倒序鏈 表變?yōu)檎蜴湵怼Ｓ谑切纬闪艘粋€環(huán)形鏈表妓笙，當(dāng) get 表中不存在的元素時若河，造成 死循環(huán)。
