hashmap問題解決方法_HashMap為什麼不安全

A. HashMap面試問題整理

拉鏈法
創建一個鏈表數組，數組中每一格就是一個鏈表。若遇到哈希沖突，則將沖突的值加到鏈表中即可。

鏈表長度大於閾值（默認為8）時，將鏈表轉化為紅黑樹，以減少搜索時間。

頭插

尾插

在 transfer() 方法中，因為新的 Table 順序和舊的不同，所以在多線程同時擴容情況下，會導致第二個擴容的線程next混亂，本來是 A -> B ，但t1線程已經 B -> A 了，所以就成環了。

1.8扔掉了 transfer() 方法，用 resize() 擴容：

使用 do while 循環一次將一個鏈表上的所有元素加到鏈表上，然後再放到新的 Table 上對應的索引位置。

JDK1.7的時候使用的是數組+ 單鏈表的數據結構。但是在JDK1.8及之後時，使用的是數組+鏈表+紅黑樹的數據結構（當鏈表的深度達到8的時候，也就是默認閾值，就會自動擴容把鏈表轉成紅黑樹的數據結構來把時間復雜度從O（n）變成O（logN）提高了效率）

1.8的索引只用了一次移位，一次位運算就確定了索引，計算過程優化。

二者的 hash 擾動函數也不同，1.7有4次移位和5次位運算，1.8隻有一次移位和一次位運算

初始容量和載入因子會影響 HashMap 的性能：

常說的capacity指的是 DEFAULT_INITIAL_CAPACITY （初始容量），值是 1<<4 ，即16；

capacity() 是個方法，返回數組的長度。

在hashMap構造函數中，賦值為 DEFAULT_LOAD_FACTOR（0.75f）

載入因子可設為>1，即永不會擴容，(犧牲性能節省內存)

Map中現在有的鍵值對數量，每 put 一個entry， ++size

數組擴容閾值。

即：HashMap數組總容量 * 載入因子（16 * 0.75 = 12）。當前 size 大於或等於該值時會執行擴容 resize() 。擴容的容量為當前 HashMap 總容量的兩倍。比如，當前 HashMap 的總容量為 16 ，那麼擴容之後為 32

獲取哈希碼， object 的 hashCode() 方法是個本地方法，是由C實現的。

理論上hashCode是一個int值，這個int值范圍在-2147483648和2147483648之間，如果直接拿這個hashCode作為HashMap中數組的下標來訪問的話，正常情況下是不會出現hash碰撞的。
但是這樣的話會導致這個HashMap的數組長度比較長，長度大概為40億，內存肯定是放不下的，所以這個時候需要把這個hashCode對數組長度取余，用得到的余數來訪問數組下標。

高低位異或，避免高位不同，低位相同的兩個 hashCode 值產生碰撞。

為什麼 重寫 equals 時必須重寫 hashCode 方法？

equals()既然已能對比的功能了，為什麼還要hashCode()呢？ 因為重寫的equals()里一般比較的比較全面比較復雜，這樣效率就比較低，而利用hashCode()進行對比，則只要生成一個hash值進行比較就可以了，效率很高。

hashCode()既然效率這么高為什麼還要equals()呢？ 因為hashCode()並不是完全可靠，有時候不同的對象他們生成的hashcode也會一樣（生成hash值得公式可能存在的問題），所以hashCode()只能說是大部分時候可靠，並不是絕對可靠，

A：兩個時候

Node[] table，即哈希桶數組，哈希桶數組table的長度length大小必須為2的n次方

0.75 * 2^n 得到的都是整數。

把bucket擴充為2倍，之後重新計算index，把節點再放到新的bucket中

hashCode是很長的一串數字，(換成二進制，此元素的位置就是後四位組成的 ( 數組的長度為16，即4位 ))

eg.

1111 1111 1111 1111 0000 1111 0001 1111 (原索引是後面四個，索引是15)

擴容後：
1111 1111 1111 1111 0000 1111 000 1 1111 (新的索引多了一位)（多出來這個，或1或0 隨機，完全看hash）

因此，我們在擴充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成「原索引+oldCap」。

這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由於 新增的1bit是0還是1可以認為是隨機的 （hashCode里被作為索引的數往前走了一個，走的這個可能是0，也可能是1），因此resize的過程，均勻的把之前的沖突的節點分散到新的bucket了。

用Iterator有兩種方式，分別把迭代器放到entry和keyset上，第一種更推薦，因為不需要再 get(key)

可減少哈希碰撞

可以，null的索引被設置為0，也就是Table[0]位置
在JDK7中，調用了 putForNullKey() 方法，處理空值

JDK8中，則修改了hash函數，在hash函數中直接把 key==null 的元素hash值設為0，

再通過計算索引的步驟

得到索引為0；

對key的hashCode()做hash運算，計算index; 如果在bucket里的第一個節點里直接命中，則直接返回；如果有沖突，則通過key.equals(k)去查找對應的Entry;

調用 putValue :

是以31為權，每一位為字元的ASCII值進行運算，用int的自然溢出來等效取模。

假設String是ABC，

可以使用ConcurrentHashmap，Hashtable等線程安全等集合類。

Divenier總結：

要看作為key的元素的類如何實現的，如果修改的部分導致其 hashcode 變化，則修改後不能 get() 到；

如修改部分對 hashcode 無影響，則可以修改。

開放定址法、鏈地址法(拉鏈法)、再Hash法

部分參考資料：

https://tech.meituan.com/2016/06/24/java-hashmap.html

https://zhuanlan.hu.com/p/76735726

https://zhuanlan.hu.com/p/111501405

B. java 中遍歷 hashmap的問題

可以使用LinkedHashMap來解決迭代順序與插入順序一致的問題。
在你的代碼中，用LinkedHashMap替換HashMap即可。

參看:

LinkedHashMap和HashMap的比較使用

http://www.cnblogs.com/hubingxu/archive/2012/02/21/2361281.html.

C. 如何遍歷HashMap逆序在java問題，怎麼解決

案例

//遍歷HashMap逆序
public static void main(String[] args) {
LinkedHashMap <String,String > linkedhashmap = new LinkedHashMap<String,String>();
linkedhashmap.put("1","a");
linkedhashmap.put("2","b");
linkedhashmap.put("3","c");
linkedhashmap.put("4","d");
ListIterator<Map.Entry<String,String>> i=new ArrayList<Map.Entry<String,String>>(linkedhashmap.entrySet()).listIterator(linkedhashmap.size());
while(i.hasPrevious()) {
Map.Entry<String, String> entry=i.previous();
System.out.println(entry.getKey()+":"+entry.getValue());
}
}

結果：

D. 如何解決hashmap因為多線程未同步時導致put進的元素get出來為null的分析

當你明明put進了一對非null key-value進了HashMap，某個時候你再用這個key去取的時候卻發現value為null，再次取的時候卻又沒問題，都知道是HashMap的非線程安全特性引起的，分析具體原因如下：
Java代碼
public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
// indexFor方法取得key在table數組中的索引，table數組中的元素是一個鏈表結構，遍歷鏈表，取得對應key的value
for (Entry 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;
再看看put方法：
Java代碼
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 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++;
// 若之前沒有put進該key，則調用該方法
addEntry(hash, key, value, i);
return null;

E. java hashmap 問題求解

package com.day14.mine;

import java.io.UnsupportedEncodingException;
import java.util.Collection;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

/**
* 〈一句話功能簡述〉
* 〈功能詳細描述〉
* @author
* @version
* @since
*/
public class GradeTest
{

/**
* 〈一句話功能簡述〉
* 〈功能詳細描述〉
* @param args void
* @throws Exception
*/
public static void main(String[] args) throws Exception
{
LinkedList<HashMap<String, Integer>> gradeList = getGradeList();
int time = 0;
String name = null;

System.out.println("---（1）查詢某次考試總成績（具體考試次數由台用戶輸入Scanner決定）---");
time = Integer.valueOf(getConsoleInput());

System.out.println(getTotalResults(gradeList, time));

System.out.println("-----（2）查詢某學生總成績（具體學生由台用戶輸入Scanner決定）-----");
name = getConsoleInput();
System.out.println(name + " : " + getStudentTotalResults(gradeList, name.trim()));

System.out.println("----（3）查詢某學生平均成績（具體學生由台用戶輸入Scanner決定）----");
name = getConsoleInput();
System.out.println(name + " : " + getStudentAVGResults(gradeList, name.trim()));

System.out.println("----（4）查詢全班平均分高次考試成績哪次並輸出平均成績具體值-------");
System.out.println(getHighGradeTime(gradeList));

System.out.println("-----（5）查詢某學生某次考試成績（學生姓名和考試次數均由台用戶輸入）------");
System.out.println("姓名：");
name = getConsoleInput();
System.out.println("次數：");
time = Integer.valueOf(getConsoleInput());
System.out.println(getStudentOneTimeResult(gradeList, time, name.trim()));
}

public static LinkedList<HashMap<String, Integer>> getGradeList()
{
LinkedList<HashMap<String, Integer>> gradeList = new LinkedList<HashMap<String, Integer>>();
HashMap<String, Integer> m = new HashMap<String, Integer>();
m.put("zhangsan", 80);
m.put("lisi", 65);
m.put("wangwu", 35);
m.put("xueliu", 90);
m.put("zhaoqi", 70);
gradeList.add(m);

m = new HashMap<String, Integer>();
m.put("zhangsan", 88);
m.put("lisi", 75);
m.put("wangwu", 45);
m.put("xueliu", 92);
m.put("zhaoqi", 75);
gradeList.add(m);

m = new HashMap<String, Integer>();
m.put("zhangsan", 86);
m.put("lisi", 67);
m.put("wangwu", 55);
m.put("xueliu", 98);
m.put("zhaoqi", 65);
gradeList.add(m);

m = new HashMap<String, Integer>();
m.put("zhangsan", 88);
m.put("lisi", 80);
m.put("wangwu", 59);
m.put("xueliu", 88);
m.put("zhaoqi", 68);
gradeList.add(m);
return gradeList;
}

private static String getConsoleInput()
{
Scanner scanner = new Scanner(System.in);

String input = "";

while(scanner.hasNext())
{
input = scanner.nextLine();
break;
}

return input;
}

/**
*
* 某次總成績
* 〈功能詳細描述〉
* @param gradeList
* @param once
* @return int
*/
public static int getTotalResults( LinkedList<HashMap<String, Integer>> gradeList,int time)
{
if(time > gradeList.size())
{
return -1;
}

int outTotalResults = 0;

HashMap<String, Integer> map = gradeList.get(time - 1);
Collection<Integer> values = map.values();
for (Integer i : values)
{
outTotalResults += i;
}

return outTotalResults;
}

/**
*
* 某生總成績
* @param gradeList
* @param once
* @return int
* @throws UnsupportedEncodingException
*/
public static int getStudentTotalResults( LinkedList<HashMap<String, Integer>> gradeList,String name) throws UnsupportedEncodingException
{
int outTotalResults = 0;
for (HashMap<String, Integer> map : gradeList)
{
if(null != map.get(name))
{
outTotalResults += map.get(name);
}
}

return outTotalResults;
}

/**
*
* 學生平均成績
* @param gradeList
* @param once
* @return int
*/
public static int getStudentAVGResults( LinkedList<HashMap<String, Integer>> gradeList,String name)
{
int totalResults = 0;

for (HashMap<String, Integer> map : gradeList)
{
if(null != map.get(name))
{
totalResults += map.get(name);
}
}

return totalResults / gradeList.size();
}

/**
*
* 平均成績最高一次
* @param gradeList
* @return int
*/
public static int getHighGradeTime( LinkedList<HashMap<String, Integer>> gradeList)
{
double highAVGResults = 0;
double tempTotalResults = 0;
int highAVGIndex = 0;

for (int i = 0; i < gradeList.size(); i++)
{
Collection<Integer> values = gradeList.get(i).values();
for (Integer value : values)
{
tempTotalResults += value;
}

if (highAVGResults < tempTotalResults / values.size())
{
highAVGResults = tempTotalResults / values.size();
highAVGIndex = i;
tempTotalResults = 0;
}
}

return highAVGIndex;
}

/**
*
* 某生某次成績
* @param gradeList
* @param time
* @param name
* @return int
*/
public static int getStudentOneTimeResult( LinkedList<HashMap<String, Integer>> gradeList, int time,String name)
{
if(time > gradeList.size())
{
return -1;
}

HashMap<String, Integer> map = gradeList.get(time - 1);

return map.get(name);
}
}

F. JAVA hashmap的問題

HashMap散列圖、Hashtable散列表是按「有利於隨機查找的散列(hash)的順序」。並非按輸入順序。遍歷時只能全部輸出，而沒有順序。甚至可以rehash()重新散列，來獲得更利於隨機存取的內部順序。
總之，遍歷HashMap或Hashtable時不要求順序輸出，即與順序無關。

可以使用迭代的方式，輸出HashMap。

Iteratori=hasmap.entrySet().iterator();
while(i.hasNext()){
Entryentry=(Entry)it.next();
Objectkey=entry.getKey();
Objectvalue=entry.getValue();
}

G. hashmap會問到數組索引，hash碰撞怎麼解決

Java中HashMap是利用「拉鏈法」處理HashCode的碰撞問題。在調用HashMap的put方法或get方法時，都會首先調用hashcode方法，去查找相關的key，當有沖突時，再調用equals方法。hashMap基於hasing原理，我們通過put和get方法存取對象。當我們將鍵值對傳遞給put方法時，他調用鍵對象的hashCode()方法來計算hashCode，然後找到bucket（哈希桶）位置來存儲對象。當獲取對象時，通過鍵對象的equals()方法找到正確的鍵值對，然後返回值對象。HashMap使用鏈表來解決碰撞問題，當碰撞發生了，對象將會存儲在鏈表的下一個節點中。hashMap在每個鏈表節點存儲鍵值對對象。當兩個不同的鍵卻有相同的hashCode時，他們會存儲在同一個bucket位置的鏈表中。鍵對象的equals()來找到鍵值對。

H. HashMap為什麼不安全

我們都知道HashMap是線程不安全的，在多線程環境中不建議使用，但是其線程不安全主要體現在什麼地方呢，本文將對該問題進行解密。

1.jdk1.7中的HashMap

在jdk1.8中對HashMap做了很多優化，這里先分析在jdk1.7中的問題，相信大家都知道在jdk1.7多線程環境下HashMap容易出現死循環，這里我們先用代碼來模擬出現死循環的情況：

publicclassHashMapTest{publicstaticvoidmain(String[]args){HashMapThreadthread0=newHashMapThread();HashMapThreadthread1=newHashMapThread();HashMapThreadthread2=newHashMapThread();HashMapThreadthread3=newHashMapThread();HashMapThreadthread4=newHashMapThread();thread0.start();thread1.start();thread2.start();thread3.start();thread4.start();}}{privatestaticAtomicIntegerai=newAtomicInteger();privatestaticMapmap=newHashMap<>();@Overridepublicvoidrun(){while(ai.get()<1000000){map.put(ai.get(),ai.get());ai.incrementAndGet();}}}

上述代碼比較簡單，就是開多個線程不斷進行put操作，並且HashMap與AtomicInteger都是全局共享的。

在多運行幾次該代碼後，出現如下死循環情形：

2.jdk1.8中HashMap

在jdk1.8中對HashMap進行了優化，在發生hash碰撞，不再採用頭插法方式，而是直接插入鏈表尾部，因此不會出現環形鏈表的情況，但是在多線程的情況下仍然不安全，這里我們看jdk1.8中HashMap的put操作源碼：

finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;Nodep;intn,i;if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;if((p=tab[i=(n-1)&hash])==null)//如果沒有hash碰撞則直接插入元素tab[i]=newNode(hash,key,value,null);else{Nodee;Kk;if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))e=p;elseif(pinstanceofTreeNode)e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);else{for(intbinCount=0;;++binCount){if((e=p.next)==null){p.next=newNode(hash,key,value,null);if(binCount>=TREEIFY_THRESHOLD-1)//-1for1sttreeifyBin(tab,hash);break;}if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))break;p=e;}}if(e!=null){//=e.value;if(!onlyIfAbsent||oldValue==null)e.value=value;afterNodeAccess(e);returnoldValue;}}++modCount;if(++size>threshold)resize();afterNodeInsertion(evict);returnnull;}

這是jdk1.8中HashMap中put操作的主函數，注意第6行代碼，如果沒有hash碰撞則會直接插入元素。

如果線程A和線程B同時進行put操作，剛好這兩條不同的數據hash值一樣，並且該位置數據為null，所以這線程A、B都會進入第6行代碼中。

假設一種情況，線程A進入後還未進行數據插入時掛起，而線程B正常執行，從而正常插入數據，然後線程A獲取CPU時間片，此時線程A不用再進行hash判斷了，問題出現：線程A會把線程B插入的數據給覆蓋，發生線程不安全。

總結

首先HashMap是線程不安全的，其主要體現：

在jdk1.7中，在多線程環境下，擴容時會造成環形鏈或數據丟失。

在jdk1.8中，在多線程環境下，會發生數據覆蓋的情況。

導航:首頁 > 解決方法 > hashmap問題解決方法

hashmap問題解決方法

案例

與hashmap問題解決方法相關的資料