2020-12-07

2020-12-07 本文已影响0人范er_er

数组长度是有限的，我们通过key.hashcode()得到的值有可能是相同的，则会形成链表

JDK1.7 数组+链表

public void node(){
    final K key;
    V value;
    final int hash;
     Entry<K,V> entry;
}

JDK1.8 数组+链表+红黑树

class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        }

JDK1.7 entry链表插入方式每次扩容的时候会将所有的entry值重新rehash 会出现环形链表，出现死循环

java8之前是头插法，就是说新来的值会取代原有的值，原有的值就顺推到链表中去，就像上面的例子一样，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。

JDK1.8 Node尾部插入了在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

初始化大小16
1<<4就是16
在使用2的冥的时候，length-1的值所有的二进制的值都为1，index的结果与hashcode的后几位相同，实现了均匀分布
- index = hashcode(key) & (length -1)

数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize。
- resize有两个因素：
  - Capacity：HashMap当前长度。
  - loadFactor: 负载因子，默认值0.75
```
就比如当前的容量大小为100，当你存进第76个的时候，判断发现需要进行resize了，那就进行扩容，但是HashMap的扩容也不是简单的扩大点容量这么简单的。
```
扩容方式
- 1.创建一个新的 Entry空数组，长度是原数组的2倍
- 2.Rehash：遍历原Entry 数组，把所有的Entry重新Hash到数组
为啥是loadFactor是0.75
- 空间换时间 - 如果大于0.75 数组被填满的元素就多，冲突的几率大，链表存的元素就越多，查询不方便
- 时间换空间-小于0.75，数组被填满的元素少，冲突的几率少，链表存的元素少，查询快

转为红黑树有两个条件

根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表。

1.效率低的原因
- 对数据操作都会上锁
2.与hashmap不同点
- 1.hashtable不允许key与value为空值，hashMap是允许的
  - Hashtable在我们put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理。
  - Hashtable使用的是安全失败机制（fail-safe）
- 2.实现方式不同，hashTable继承Dictionary； hashMap继承AbstractMap
- 3.初始化容量不同，hashTable 是 11 ，hashMap为16
- 4.扩容机制不同 hashMap是翻倍 hashtable是翻倍+1
- 5.迭代器不同 hashMap的迭代器iterator 是fail-safe
fail-safe
- 原理
  - 迭代器遍历访问内容，会存在modCount 变量，如果遍历发生内容的改变，则会改变modCount的值，当下次hashNext()/next()遍历下一个节点，会检测 expectedmodCount值，是的话返回遍历，否则抛出异常
- 场景
  - 并发修改