java HashMap

HashMap是最常用的Map实现,它按照键的HashCode 值存储数据,按照键可以直接获取它的值，具有很快的拜候速度。HashMap最多只许可一笔记录的键为Null(多条会笼盖，也就是key不克不及反复);许可多笔记录的值为 Null。非同步的也就是说线程不平安。

东西/原料

电脑
intellij IDEA

第一步：HashMap实现道理。

1
什么是HashMap？
1、基于哈希表的一个Map接话柄现，存储的对象是一个键值对对象(Entry<K,V>)；
2、基于数组和链表实现，内部维护着一个数组table，该数组保留着每个链表的表头结点；查找时，先经由过程hash函数计较key的hash值，再按照key的hash值计较数组索引（取余法），然后按照索引找到链表表头结点，然后遍历查找该链表；
2
HashMap数据布局
1、画了个示意图，如下，左边的数组索引是按照key的hash值计较获得，分歧hash值有可能发生一样的索引，即哈希冲突，此时采用链地址法处置哈希冲突，即将所有索引一致的节点组成一个单链表；
3
HashMap担当的类与实现的接口
1、HashMap接口示意图：如下所示
2、Map接口，方式的寄义很简单，根基上看个方式名就知道了，后面会在HashMap源码阐发里具体申明
3、AbstractMap抽象类中界说的方式

第二步：关头源码讲解

1
HashMap 是若何存储的？
a.底层是一个数组 tab
b. hash=hash(key) ，然后按照数组长度n和hash值，决议当前需要put的元素对应的数组下标，
hash算法见红框。
2
数组长度是固心猿意马的，HashMap 可以无限put(k,v) ,为什么？
HashMap 的元素个数大于threshold的时辰，会进行resize() 扩容
3
若何实现扩容的？
扩容就是经由过程 resize() , 从头建立一个新数组，对所有元素rehash,放到新数组响应位置。
扩容价格是很大的，所以良多公司编码规范都有一条，合理设置hashMap的InitialCapicity,
禁止直接用HashMap()
4
Hash 冲突是什么？怎么解决这个问题？
1、Hash 冲突：假如一个黉舍有366个同窗，一年365天，那么至少有两个同窗是统一生成日，这就是hash冲突。用代码来说，分歧的key 颠末计较p = tab[i = (n - 1) & hash] 对应统一个p
2、若何解决:
p在有的翻译文档中叫桶，一个桶可以装多个，怎么装? 链表或者红黑树。
3、下图代码中 else if 部门是红黑树
else 部门是链表，链表中若是冲突元素个>=TREEIFY_THRESHOLD-1,会将链表转换当作红黑树。
因为元素个数良多时，红黑树比链表机能更好。
5
HashMap 是不是线程平安的，若何解决线程平安问题？
1、HashMap 是线程不平安的
2、对整个map加锁。
3、如图（3）对f加锁了，就是对桶加锁，就是传说中的分段锁机制。
在包管平安的前提下，加锁的规模越小，则程序机能越高，本身写代码时切记胡乱在方式上加synchronized
6
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 会有两个元素，而我们期望的只保留一个。
7
验证ConcurrentHashMap 线程平安。

第三步：HashMap利用实例

1
常用根基操作
package com.pichen.collection;

import java.util.HashMap;
import java.util.Map;

public class Main {

public static void main(String[] args) {
Map<String, Integer> map = new HashMap<String, Integer>();

//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<String, Integer> entry:map.entrySet()){
System.out.print(entry.getKey() + ": " + entry.getValue() + ", ");
}

}
}