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是很长的一串数字，<font color = orange>(换成二进制，此元素的位置就是后四位组成的 ( 数组的长度为16，即4位 ))</font>

eg.

<font color = gray>1111 1111 1111 1111 0000 1111 0001</font> 1111 (原索引是后面四个，索引是15)

扩容后：
<font color = gray>1111 1111 1111 1111 0000 1111 000</font> 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中，在多线程环境下，会发生数据覆盖的情况。