HashMap

# HashMap扩容为什么是2的n次幂？

在计算数组下标时，先把Hash表中数组长度-1，然后与key的hash值进行按位与(&)操作；

i = (n-1)&hash

# HashMap扩容

HashMap在无参构造时，默认初始容量是16；

当链表长度>8，数组长度<64，优先对数组进行扩容；否则链表树化；

数组自己扩容时其扩容因子为0.75；

# 哈希碰撞

HashMap通过key的hashcode经过扰动函数处理后得到hash值，然后通过(n-1)&hash判断当前数组索引位置是否存在元素，存在的话就要判断该元素(Node节点)与要存入的元素的hash值与value是否相同，相同的话，直接覆盖；不同的话通过拉链法解决哈希冲突；
static class Node<K,V> implements Map.Entry<K,V> {
       final int hash;// 哈希值，存放元素到hashmap中时用来与其他元素hash值比较
       final K key;//键
       V value;//值
       // 指向下一个节点
       Node<K,V> next;
	   ...
}
1
2
3
4
5
6
7
8
“拉链法” 就是：将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。

# 线程不安全问题

jdk1.7：拉链法是头插法，出现并发死链问题；

jdk1.8：尾插法，但是put操作出现数据覆盖的风险（1.7也会）；

# modCount字段作用

modCount：遍历的时候记录数量，如果迭代器遍历时候数量发生变化，说明有多个线程操作HashMap，主动抛出异常；

在集合遍历的过程中，其它线程或当前线程都不能对集合结构进行修改，如果修改，报并发修改异常；

三种集合删除元素方式：
//1.索引判断
for(int i=0;i<n;i++){
    if(list.get(i).equals(val)){
        list.remove(i);
    }
}

//2.迭代器
Iterator<String> it = list.iterator();
while(it.hasNext()){
    String l = iterator.next();
    if(l.equals(val)){
        list.remove(l);
    }
}

//3.增强for
for(String l:list){
    if(l.equals(val)){
        list.remove(l);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1报错索引越界异常，23报错并发修改异常；

更改：

选择index从大到小遍历；

使用Iterator中的remove()方法；

使用集合中的removeIf()方法;

modCount++执行的位置：

增删元素；

集合排序；

集合扩容；

更新某位置元素并没有执行；

# map中存自定义对象需要注意什么？

当map/set的key为自定义对象时，必须重写hashCode 和 equals；

当使用map/set时，hashCode()方法会得到调用，判断已经存储在集合中的对象hashcode值是否与新增的相同，如果不一致直接加进去；如果一致，再进行equals判断；

← ArrayList ConcurrentHashMap→