HashMap ：基于哈希表的Map接口实现。底层基于数组，链表，1.8引入红黑树。
主要属性
final float loadFactor ;负载因子
用来表示数组的占满程度，负载因子过小，数组占满程度小造成空间的浪费
负载因子过大，数组的占满程度大，空间利用率高，但hash冲突的机会变大查询效率变低。
经典的时空折中问题
hash冲突：不同的key值经hash函数计算后可能具有相同的结果。也就是说存储在数组中的同一个位置这就是hash冲突。
解决hash冲突的四种方法：
开放定址法：一旦发生hash冲突，就去寻找下一个空的散列地址。
再hash法：在维护一个hash表来存储冲突的元素。
链表法：用链表存储hash冲突的元素。
公共溢出区：建立一个公共储存空间储存hash冲突的元素。
int threshold; 临界值等于负载因子乘数组大小 ，超过临界值就要进行扩容操作resize;
int modCount ; 修改次数
int size;数组中元素的个数
内部 Node类
final int hash; 用于定位数组索引
final K key;
V value;
Node next;
优点：可以实现O(1)时间复杂度的查询。
缺点：hash冲突，线程不安全resize 造成死锁问题。
HashMap put方法的实现思路
1计算key的hashcode在做hash 计算在数组（buckets）的位置index
2如果该位置无元素直接存放，若已有元素以链表的形式存放在buckets后面，若链表长度大于8就把链表转换为红黑树。
3如果该节点（key值）已存在 ，就替换value值
4如果size超过了临界值threshold 就要进行resize;
HashMap get方法的实现思路
计算key的hashcode在做hash 计算在数组（buckets）的位置index
通过key.equals(k)在链表o(n)或红黑树o(logn)查找
扩容机制resize
当HashMap中元素大于临界值threshold就需要进行扩容
创建一个新数组容量为原数组2倍，遍历Node数组获取每个元素进行rehash计算在新数组中的位置并存入。
在存入新数组中链表使用了头插入方法 优点是无需遍历链表 缺点在多线程并发进行是可能造成死锁
死锁的形成原因：
线程1进行transfer 记录链表的顺序为A->B，此时线程切换
线程2对HashMap进行resize 结果为B->A.
线程1继续进行transfer 形成A.next=B,B.next=A 形成环形链表 ，存取进入环形链就会形成死锁。
解决方案使用ConcurrntHashMap代替。
网友评论