java HashMap

java HashMap

HashMap是最常用的Map实现,它根据键的HashCode 值存储数据,根据键可以直接获取它的值，具有很快的访问速度。HashMap最多只允许一条记录的键为Null(多条会覆盖，也就是key不能重复);允许多条记录的值为 Null。非同步的也就是说线程不安全。

什么是HashMap？

1、基于哈希表的一个Map接口实现，存储的对象是一个键值对对象(Entry)；

2、基于数组和链表实现，内部维护着一个数组table，该数组保存着每个链表的表头结点；查找时，先通过hash函数计算key的hash值，再根据key的hash值计算数组索引（取余法），然后根据索引找到链表表头结点，然后遍历查找该链表；

HashMap数据结构

1、画了个示意图，如下，左边的数组索引是根据key的hash值计算得到，不同hash值有可能产生一样的索引，即哈希冲突，此时采用链地址法处理哈希冲突，即将所有索引一致的节点构成一个单链表；

HashMap继承的类与实现的接口

1、HashMap接口示意图：如下所示

2、Map接口，方法的含义很简单，基本上看个方法名就知道了，后面会在HashMap源码分析里详细说明

3、AbstractMap抽象类中定义的方法

HashMap 是如何存储的？

a.底层是一个数组 tab

b. hash=hash(key) ，然后根据数组长度n和hash值，决定当前需要put的元素对应的数组下标，

hash算法见红框。

数组长度是固定的，HashMap 可以无限put(k,v) ,为什么？

HashMap 的元素个数大于threshold的时候，会进行resize() 扩容

如何实现扩容的？

扩容就是通过 resize() , 重新创建一个新数组，对所有元素rehash,放到新数组相应位置。

扩容代价是很大的，所以很多公司编码规范都有一条，合理设置hashMap的InitialCapicity,

禁止直接用HashMap()

Hash 冲突是什么？怎么解决这个问题？

1、Hash 冲突： 假如一个学校有366个同学，一年365天，那么至少有两个同学是同一天生日，这就是hash冲突。用代码来说，不同的key 经过计算p = tab[i = (n - 1) & hash] 对应同一个p

2、如何解决:

p在有的翻译文档中叫桶，一个桶可以装多个，怎么装? 链表或者红黑树。

3、下图代码中 else if 部分是红黑树

else 部分是链表 ，链表中如果冲突元素个>=TREEIFY_THRESHOLD-1,会将链表转换成红黑树。

因为元素个数很多时，红黑树比链表性能更好。

HashMap 是不是线程安全的，如何解决线程安全问题？

1、HashMap 是线程不安全的

2、对整个map加锁。

3、如图（3）对f加锁了，就是对桶加锁，就是传说中的分段锁机制。

在保证安全的前提下，加锁的范围越小，则程序性能越高，自己写代码时切记胡乱在方法上加synchronized

HashMap 和 hash() equals() 方法的关系

1、面试中面试官会问重写equals()方法要注意是什么，答案是hash()也要重写。

不重写会引起HashMap 等集合类使用的混乱。

2、如下图：比如类Person(id,name)，重写了 equals(Object obj){... reutrn this.id==obj.id}，没有重写hash(), 那么从类定义上来说，只要id相等就是同一个人，当我们Person作为key，放入两个Person对象(id相等)到HashMap的时候，那么就翻车了，HashMap 会有两个元素，而我们期望的只保留一个。

验证ConcurrentHashMap 线程安全。

常用基本操作

package com.pichen.collection;

import java.util.HashMap;

import java.util.Map;

public class Main {

public static void main(String[] args) {

Map map = new HashMap();

//put方法

map.put("A", 5);

map.put("B", 6);

map.put("C", 7);

map.put("D", 8);

//重写了toString方法

System.out.println(map);

//size方法

System.out.println(map.size());

System.out.println(map.containsKey("A"));

System.out.println(map.containsValue(6));

System.out.println(map.get("B"));

//remove

map.remove("C");

System.out.println(map);

//key集合

for(String str:map.keySet()){

System.out.print(str + " ");

}

System.out.println();

//value集合

for(Integer obj:map.values()){

System.out.print(obj + " ");

}

System.out.println();

//key-value集合

for(Map.Entry entry:map.entrySet()){

System.out.print(entry.getKey() + ": " + entry.getValue() + ", ");

}

}

}