HashMap接口总结和常见面试问题
HashMap集合
一、 初识hashmap
之前学过ArrayList，LinkedList。
（1）ArrayList底层是以数组实现的，插入删除慢，查询快。
（2）LinkedList底层是以链表实现的，插入删除快，查询慢。
hashmap结合了以上二者的有点，hashmap底层是数组加单链表的形式，以（key—value）键值对结构存储数据。
二、HashMap源码分析
一）集合特点
public class HashMap<K,V>
extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable
static class Entry<K,V> implements Map.Entry<K,V>
private abstract class HashIterator<E> implements Iterator<E>
从继承的接口来看，有如下特点：
1、Map：是存放一对值的最大接口！即接口中的每个元素都是一对， 以key --> value的形式保存，并且Key是不重复的，元素的存储位置由key决定。也就是可以通过key去寻找key-value的位置，从而得到value的值。适合做查找工作。
/2、Cloneable*：Cloneable是标记型的接口，它们内部都没有方法和属性，实现 Cloneable来表示该对象能被克隆，能使用Object.clone()方法。如果没有实现 Cloneable的类对象调用clone()就会抛出CloneNotSupportedException。
3、Serializable：public interface Serializable类通过实现 java.io.Serializable 接口以启用其序列化功能。
4、 Iterator：可以使用迭代器遍历
二）构造函数 默认值
这里列举几个常见的初始值
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16：默认初始化的容器大小16；
static final int MAXIMUM_CAPACITY = 1 << 30; //最大的数据容量2的30次方。也就是说最多存放2的30次方个数据；
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认的加载因子 0.75f（ 散列表的加载因子=填入表中的元素个数/散列表的长度，加载因子越大，说明空闲位置越小，冲突越多，散列表的性能会下降。）
hashmap提供了三个构造函数
1、 public HashMap(int initialCapacity, float loadFactor)
生成空的HashMap，传入容量和负载因子。容量和负载因子都是自定义的不能小于0的值，根据具体实际情况而定。
2、 public HashMap(int initialCapacity)
生成空的HashMap，传入初始容量，负载因子使用默认值（0.75）。
3、 public HashMap()
生成空的HashMap，初始容量和负载因子全为默认值。
三）增
和其他集合一样，增删改查同样是重点。
增的时候同样考虑1、什么时候开始初始化。2、是否需要扩容。3、计算增加到那个数组下标下，然后在此下标下使用链表的头插法插入链表中。
A：如果是第一次增加，调用构造函数进行初始化。
B：通过key计算index，在index链表下添加。{
a、key重复时新值替换旧值
b、key不重复时使用头插法插入
c、key为null时，添加在0号下标中，为防止空指针异常，需特殊处理
}
C：是否需要扩容，加载因子判断，为减少哈希冲突。扩容涉及到重新哈希，所以加载因子要设置合适
源码大家都有，附上自己的实现的源码：
public int hash(K key) { // 计算扰动处理后的hashcode
if (key == null) {
return 0; //对null特殊处理
}
int h = key.hashCode(); //是一个负数
h ^= (h >>> 20) ^ (h >>> 12);
h = h ^ (h >>> 7) ^ (h >>> 4); //（1）扰动处理 ： 降低hashcode的 重复率，降低index的重复率
return h;//table.length 永远是2的幂
//h & (table.length - 1) == h % table.length （2） 位运算符的计算效率高于算数运算符
//（3）并且能够解决index为负数的问题
//前提条件是 table.length 是2的幂
}
public int indexOf(int h) { //计算index
return h & (table.length - 1);
}
public void put(K key, V value) {
if (table == Empty_Table) { // 是否时第一次添加元素
table = new Entry[DEFAULT_CAPCITY];
}
int h = hash(key);
int index = indexOf(h);//计算key值对应的下标
//e.key.equals(key) 比较速率较慢
for (Entry<K, V> e = table[index]; e != null; e = e.next) {//遍历下标下的链表
if (e.hash == h && (e.key == key || (key != null && key.equals(e.key)))) {//如果key值相同，则值替换
e.value = value;
return; //如果key有重复 值替换掉之后方法就退出
}
}
//代码走到着说明key 没有重复 头插法
if (size >= table.length * threshold) {
resize(); //如何扩容：2倍扩容 始终能够保证table.length是2的幂
index = indexOf(hash(key));
}
//添加数据
table[index] = new Entry<>(key, value, table[index], h);//不相同则头插
size++;
}
public void resize() {
int old_length = table.length;
int new_length = 2 * old_length;
Entry[] new_table = new Entry[new_length];
//老数组中的元素放入到新数组中 由于数组长度变了，所以要重新计算每一个元素的下标
for (Entry<K, V> e : table) {
while (e != null) {
Entry<K, V> next = e.next;
int index = indexOf(hash(e.key));
e.next = new_table[index];
new_table[index] = e;
e = next;
}
}
table = new_table;
}
四）删
删除时要考虑的是删除的是链表上的节点，所以也就变成了单链表节点的删除。回顾之前写的单链表删除操作，
需要找到待删节点的前驱节点，将前驱节点的next指向待删节点的后继，再把value，key域置为空。这样就需要考虑一个特殊情况，如果待删节点是头结点，没有前驱节点，所以需要单独处理，记得更新头结点。
同样附上自己实现的源码（这里用了两个指针）：
public Boolean remove(K key) {
if (size <= 0) {
return false;
}
int h = hash(key);
int index = indexOf(h);
Entry<K, V> pre = table[index];
Entry<K, V> e = table[index];
while (e != null) {
Entry<K, V> next = e.next;
//第一个循环进来如果判断相等就成立 删除的的就是头节点 pre == e
if (e.hash == h && (e.key == key || (key != null && key.equals(e.key)))) {
size--;
//如果删除的节点是头节点
if (pre == e) { //判断删除的节点就是头节点
table[index] = next;
} else {
pre.next = next;
}
e.next = null;
e.key = null;
e.value = null; //只有指向空之后才能进行垃圾回收
return true;
}
pre = e;
e = next; //pre 变成了e的前驱
}
return false;
}
五）改
找到key键，新value替换旧value
public void replace(K key, V new_value) {//通过key 找到对应的节点 然后将value替换成新的value
if (size <= 0) {
return;
}
int h = hash(key);
int index = indexOf(h);
for (Entry<K, V> e = table[index]; e != null; e = e.next) {//遍历下标下的链表
if (e.hash == h && (e.key == key || (key != null && key.equals(e.key)))) {
e.value = new_value;
}
}
}
六）查
根据key查找value
时间复杂度O（1）
public V get(K key) { //通过key 找到对应的节点 然后将value返回
if (size <= 0) {
return null;
}
int h = hash(key);
int index = indexOf(h);
for (Entry<K, V> e = table[index]; e != null; e = e.next) {//遍历下标下的链表
if (e.hash == h && (e.key == key || (key != null && key.equals(e.key)))) {
return e.value;
}
}
return null;
}
七）迭代器实现
``
public Iterator<Entry<K, V>> iterator() {
return new HashIterator();
}
class HashIterator implements Iterator<Entry<K, V>> {
Entry <K,V> next; // 下一个要被遍历的节点
Entry <K,V> current; // 当前正在被遍历的节点
int index; //当前所在的数组的下标
HashIterator (){
if(size >0){
Entry []t=table ;
while (index <t.length &&(next =t[index ++])==null ){
;//找到第一个节点
}
}
}
@Override
public boolean hasNext() { // 判断是否有下一个元素
return next !=null ;//index和size之间的关系
}
final Entry<K, V> nextEntry() { // 取出元素并且移动到下一个元素的位置
Entry<K,V> e = next;
if (e == null)
throw new NoSuchElementException();
if ((next = e.next) == null) { //如果下一个元素为空
Entry[] t = table;
while (index < t.length && (next = t[index++]) == null)//找到下一个不为空的节点
;
}
current = e;//更新当前节点的位置
return e;
}
@Override
public Entry<K, V> next() {
return nextEntry() ;
}
@Override
public void remove() {
if (current == null) {//如果当前节点为空
throw new IllegalStateException();
}
K k = current.key;//保存k值
current = null;//更新current
MyHashMap .this.remove( k);//调用删除方法
}
}
遍历方式
//1、迭代器遍历
Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<String, Integer> next = iterator.next();
System.out.println("key:" + next.getKey() + " value:" + next.getValue());
//System.out.println(iterator .next() .getKey() + iterator .next() .getValue() );
}
System.out.println("==================");
//2、遍历key值，位置由key值决定
Iterator<String> iterator1 = map.keySet().iterator();
while (iterator1.hasNext()) {
String key = iterator1.next();
System.out.println("key:" + key);
}
System.out.println("===================");
//3、遍历value
Iterator<Integer> iterator2 = map.values().iterator();
while (iterator2.hasNext()) {
Integer value = iterator2.next();
System.out.println("value" + value);
}
System.out.println("=================");
//foreach遍历key ，value
for (Map.Entry<String, Integer> entry : map.entrySet()) {
System.out.println("key: " + entry.getKey() + " value: " + entry.getValue());
}
}
八、哈希冲突
当同一个index对应多个key，这就叫哈希冲突
比如15%8=7
23%8=7
31%8=7
jdk1.7版本中，hashmap中解决此方法用的是链地址法
链地址法的不足：
① 链地址法存在的不足在于，当产生哈希冲突的节点越多，那么数组索引下标查找就会变成链表的遍历操作。数组的优势在于随机取值，时间复杂度达到O(1)，而链表的查找时间效率达到O(n)。
② 当产生数组扩容时，所有的元素节点都必须进行重新哈希。
我还了解到线性探测法来解决哈希冲突
线性探测法：主要根据index = val.hashcode()%element.length来解决哈希冲突问题。从数组当前位置（hashcode()）开始，找到下一个空位置，进行存放。当数组填充满之后，进行数组的扩容操作，继续存放值。存储的键值对中键相等进行值的覆盖操作。进行扩容后的操作，还得进行元素的重新哈希操作。
线性探测法的不足：线性探测法当产生哈希冲突的键值对越多，遍历数组的次数就会越多。
九、常见关于hashmap面试题的整理
1.HashMap的特点
存储双值 key value
Map<K,V>
以key --> value的形式存储数据
并且Key是不重复的，key可以为null，元素的存储位置由key决定。
也就是可以通过key去寻找key-value的位置。
从而得到value的值。
适合做查找工作。
Cloneable 可以使用clone
Serializable 可以被序列化
Map.Entry 可以存储key-value具体数值。
Iterator 迭代器 只能从前往后进行遍历
2.HashMap如何计算key-value结构的存储位置
先取出key的hashCode，然后对HashCode进行扰动处理，然后将扰动处理后的HashCode和tablelength -1 进行
按位与 —》 index 这个index就是key-Value结构存储的下标。
3.哈希冲突
当多个key对应同一个数组下标。
h & (length-1) length 是 2的幂
h % length --》 index
15 % 8 = 7
23 % 8 = 7
31 % 8 = 7 哈希冲突
4.解决哈希冲突的方法，HashMap使用哪种方法
1.7 数组+链表的结构 – 链地址法
1.8 数组+链表的结构 当一个链表上节点大于8个时 改用数组+红黑树 – 链地址法
遍历链表的时间复杂度O（n）
红黑树 查找的时间复杂度（log2N）
除了链地址法外，你还了解哪些解决哈希冲突的方法（线性探测法）
5.HashMap get方法的时间复杂度
通过key计算除index 遍历链表
O（1）
答：时间复杂度近似于O（1），由于哈希冲突存在所以不一定能够达到O(1).
6.为什么hashcode要进行扰动处理
（1）扰动处理 ： 降低hashcode的 重复率，降低index的重复率
h1 & (length-1) = 8
h2 & (length-1) = 8
h1’ & (length-1) =
h2’ & (length-1) =
7.为什么不直接采用经过hashCode（）处理的哈希码 作为 存储数组table的下标位置？
保证index一定时小于数组长度。防止数组下标访问越界。
8.为什么hashmap的容量要保持2的幂
为了用 & (length-1) 代替 % length 。
9.为什么用按位与代替取余
因为位运算的计算效率高于 算数运算。
10. HashMap中如果添加重复key会怎样
新添加进来的key对应的newvalue代替之前老的value。
11.如何判断添加了重复的key
（1）先判断添加的key是否为空，如果为null在零号下标对应的节点处寻找key为null的节点。
（2）先判断hashcode 在判断 引用地址是否相同 最后判断equals
先比较hashcode 如果hashcode 不同，那么一定key不相同。如果hashcode 相同这两个key有可能是相同的key
然偶我们再去比较引用地址和equals
12.如果自己指定HashMap的初始容量和加载因子，那么容量的大小，和加载因子的大小对HashMap有什么影响
初始容量：如果我们指定不是2的幂，源码中有函数能够保证将最终数组容量改变到2的幂。向上取整找最近的2的幂。
初始容量越小，越容易发生哈希冲突。
加载因子 :越大 。对扩容时机有影响。
加载因子越大扩容的时机越晚，哈希冲突的几率越大，空间利用率越大。
加载因子越小，越大扩容的时机越早，哈希冲突的几率越小，空间利用率越小。
13.为什么HashMap需要扩容
不是因为没有足够存储空间。
扩容之后要重新计算每一个节点对应的index，哈希冲突概率降低。
14.HashMap的使用场景
使用场景 hashMap查询效率比较高，并且可以通过key去查询对应value
10学生
List.add(90) 100 70
10 用户信息 user(密码，sex,age,…);
list.add(user1)list.add(user2) …
HashMap<String,User>
map.put(“zhanshan”,user1);
map.get(“zhanshan”)
存储数据，可以快速根据key获取value
计数 ：随机输入任意个任意字符 统计每个字符的数量。
我输入a 返回a出现的次数
public static void cal(String str, Map<Character ,Integer > map) {
System.out.println("输入要查询的字母");
Scanner scanner =new Scanner(System .in ) ;
Character c=scanner.next() .charAt(0) ;
for (int i = 0; i < str.length(); i++) { //遍历字符串中的字母 cha
Character cha = str.charAt(i);
if (cha >= 'a' && cha <= 'z' || cha <= 'Z' && cha >= 'A') {
if (map.containsKey(cha)) {
int count=map .get(cha );
map.put(cha, count+1) ;//如果map中已经有key，则使count值加一，用put方法计入value中
} else {
map.put(cha, 1);//如果key是第一次出现，则把value值设为1
}
}
}
System.out.println("该字母的个数为: "+map .get(c) );
}
public static void main(String[] args) {
//字母 字母的个数
HashMap <Character,Integer> map =new HashMap<>() ;
String str = "dfhjgsajdkgasdgsadrewruhu";
cal(str,map);
}
十、hashmap的使用场景
由于hashmap可以根据key快速查找到value，所以多用于查询。
10学生
List.add(90) 100 70
10 用户信息 user(密码，sex,age,…);
list.add(user1)list.add(user2) …
HashMap<String,User>
map.put(“zhanshan”,user1);
map.get(“zhanshan”)
存储数据，可以快速根据key获取value
这里要考虑如果key值可以重复，需要将key对应的信息设置为一个类，添加时为new class（）这样就不会出现新值替换旧值的情况了。
十一、hashmap和hashtable的区别
Hashtable 和HashMap底层实现和方法使用基本类似，以下是二者的区别
1、继承的父类和接口：
Hashtable ：extends Dictionary<K,V>
HashMap：extends AbstractMap<K,V>
2、默认容量
Hashtable ：11
HashMap：16
3、Table的初始化时机
T: 构造函数中初始化，new对象时。
M: 当第一次put元素。
4、并发操作，集合是否是线程安全的
T:由于加了synchronized关键字，所以是线程安全。但是并不是绝对的线程安全。
由于Hashtable效率低已经倍淘汰，所有多线程环境我们尽量选择
ConcurrentHashMap。
M: 线程不安全的。
5、数据遍历的方式
T: hashTable 可以使用Enumeration进行遍历
也可以使用Iterator进行遍历。
M: 只可以使用Iterator进行遍历。
6/是否支持fast-fail（快速失败机制）
T: 使用Iterator进行遍历时支持使用Enumeration进行遍历时不支持。
M: 使用Iterator进行遍历时支持。
6、是否可以添加重复的key
T,M: 不能，会用新值替代老值
7、是否接受值为null的Key 或Value？
T: Key和value都 不可以为空，否则会报出空指针异常。
M:Key和value可以为空。
根据hash值计算数组下标的算法 Hash值的计算：hashSeed ^ k.hashCode() 没有扰动处理
Index 重复率会高
8、计算index:
T: hash & 0x7FFFFFFF) 保证hash的值不为负数
(hash & 0x7FFFFFFF) % tab.length;
保证index不会大于tab.length; h ^= k.hashCode();
M: h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4); 有扰动处理 减低哈希冲突
9、计算index:
T: h & (length-1);
M: 保证index不会大于tab.length;
9、Entry数组的长度
T: 11
M: 16 始终保持他是2的幂
10、LoadFactor负荷因子
T,M: 0.75 作用也是相同 。size 》= 数组的长度 * 负荷因子 进行扩容
11、负荷超过（loadFactor * 数组长度）时
T: 内部数据的调整方式 *2 + 1 奇数 取余之后的结果相比于偶数更分散。
M: 2倍的扩容
T,M:两者都会根据key重新计算所有元素的存储位置，算法相似，时间空效率相同。