简介

点击查看【bilibili】
感谢！！！视频2piece共2个多小时。

快速入门

什么是hashmap

HashMap是hash表对map接口的实现，是数组和链表的结合，HashMap同时兼备快速插入和读取的特性。
hashmap提供所有可选的映射操作， 并允许使用Null值和null键。
hashmap并非线程安全，当多个线程写入hashmap时，可能会导致数据不一致。

源码重要全局变量

loadFactor 表示负载因子，默认0.75,当负载因子高于0.75会扩容。
threshold表示所能容纳的键值对的临界值，计算公式为：数组长度*负载因子
modCount字段用来记录hashmap内部结构发生变化的次数。
常量INITIAL_CAPACITY 初始容量为16
常量TREEIFY_THRESHOLD = 8 树化临界值 大于8转红黑树
常量UNTREEIFY_THRESHOLD =6 仅在resize时使用，桶内元素<=6个，存链表。
常量MIN_TREEIFY_THRESHOLD = 64 最小树化容量

结构

hashmap使用数组+链表的数据结构
image.png
hashmap数组部分称为 hash桶 。当链表长度大于等于8时，链表数据将以红黑树存储，当长度降到6时会转到单向链表
链表遍历的时间复杂度为O(n)
红黑树的时间复杂度为O(log n)

如何设计hashmap?

二进制运算复习

image.png

hash

hash值：通过一定的散列算法，把一个固定的输入，转成一个固定的输出，在hashmap中，hash就一个Int值

hashcode计算：

取string的char字符的ascii码，然后再做一定的运算？

hash函数：把hash值打散到 数组的桶 索引位
hash碰撞：不同hash值，通过hash函数 被分配到相同的hash桶。

有哪些hash冲突的解决办法？

1. 再hash

对发生hash碰撞的一组数据再hash

2. 开放寻址

发生碰撞后往数组位的 上或下 去寻找空闲位

3. 开辟公共溢出区

开辟额外空间 放置存在hash冲突的数据

4. 链地址法(hashmap)

-

如何让设计的hashmap存取效率更高？

已经说了是hashmap，就不要再讲数组+链表，继承数组的快速读和链表的快速插

  1. 尽可能少的产生hash冲突
  2. 确实发生hash冲突，使用最佳的数据结构来保证hash桶内的数据最优存取

Hash函数

hash值 -> 数组索引值

  1. // 伪代码: 拿hash值，计算数组索引值
  2. static int indexForHash(int hash, int lenght){
  3.     return hash & (lenght - 1);
  4. }

为什么hashmap的lenght一定要是2的幂次方？ 为什么扩容要以2的倍数？

  1. 位运算比取模运算快27倍。用lenght-1 和 hash值的二进制 与运算 得到的值总是 [0,lenght-1]，有取模相同的效果但性能更优. (只有和2的n次方的&运算能够有取模相同的效果，不要再问了)

因此，这个的hash函数的离散率依赖hashCode值。hashcode值越分散，hash冲突越少。

  1. 1.8以后 resize后不需要rehash 老数据桶下标=旧下标 或者(旧下标+扩容长度）

resize 扩容

什么时候扩容？

JDK 1.7

扩容后再加元素
add时，负载因子高于0.75 且 当前桶下标产生hash碰撞

JDK 1.8

先加元素再扩容
负载因子高于0.75 直接扩容

怎么扩容？

JDK1.7

常规操作： 扩容 , rehash然后数据迁移
存在问题：头插法造成单线程迁移产生死环
image.png

JDK1.8

尾插法 add
桶内为单链表，对单链表迁移
桶内为红黑树(同时也是双向链表)，将双向链表进行数据迁移。

为什么桶内元素个数>=8时转红黑树？

根据泊松分布，桶内元素=8个的概率=亿分之6，小于亿分之十，树化的概率很低，但树化后对get的效率提升很高。

扩容后有什么问题（多线程环境）？

jdk1.7

多线程下 数据迁移 会形成环状链表

jdk1.8

多线程下 会有数据丢失的问题

什么样的hash函数是最好的？

负载因子低，使数据离散地分布在每个hash桶里面。或者说hash碰撞最少。

源码级解读

put原理

JDK 1.7

image.png

  1. public V put(K k, V v){
  2.     if(k==null)  return putForNullKey(v); 
  3.     // 内部通过一个扰乱算法 得到一个hash值 用于计算数组索引
  4.     int hash = hash(key);
  5.     // 计算数组桶下标
  6.     int i = indexFor(hash,table.length);
  7.     // 判断是否已存在 重复键
  8.     for( e at 桶内元素集 ){
  9.         if （e.hash==hash && (e.key == k || key.equals(k))){
  10.             // 更新k对应的value值
  11.             V old = e.value;
  12.             e.value = value;
  13.             e.recordAccess(this);
  14.             return old;
  15.         }
  16.     }
  17.     modCount++;
  18.     // key不存在 添加新元素
  19.     addEntry(hash,key,value,i);
  20.     return null;   
  21. }
  22. void addEntry(int hahs,K k, V v, int bucketIndex){
  23.     if(size>= threshold && null!=table[bucketIndex]){
  24.         // 负载高于0.75 且 当前桶位非空 
  25.         // 扩容为两倍
  26.         resize(2*table.length);
  27.         // rehash
  28.         hash= null==key?0:hash(key);
  29.         buckeyIndex = indexFor(hash,table.length);
  30.     }
  31.     // 添加kv到bucketIndex 
  32.     createEntry(hash,k,v,bucketIndex);  
  33. }

jdk1.8
  1. public V put(int hash, K k, V v, boolean evict){
  2.     int i = (table.length-1)&hash
  3.        // table初始化
  4.     if (table==null  || table.length==0){
  5.         n = (table = resize()).length;
  6.     }
  7.     // 当前桶位 无元素 直接放入
  8.     if(table[i]==null) {
  9.         table[i]=newNode(hash,k,v,null);
  10.     }else{
  11.         // 存在hash碰撞
  12.         Node record = table[i];
  13.         if(record.key==k){
  14.             根节点的Key刚好=k, 更新v
  15.         }else if(当前桶内集合为红黑树){
  16.            record = putTreeVal(..);
  17.         }else{
  18.             桶内集合为单链表
  19.             for(ele at 链表all){
  20.                 record = ele;
  21.                 if(record.next==null){
  22.                     插入链表尾部
  23.                     if (链表size>8) treeify(...); 添加到树(); 
  24.                     break;
  25.                 }
  26.                 if(record.key=k) break; // key重复 
  27.             }
  28.         }
  29.         if(record!=null){
  30.             // 如果插入已存在的key
  31.             更新record值
  32.             return record;
  33.         }
  34.     }
  36.     // key不存在于新增 且 新增后 超出临界值 直接扩容
  37.     if(++size>threshold)
  38.         resize(...)
  39.     afterNodeInsertion(evict)
  40.     return null
  41. }

扩容

jdk1.7
  1. void resize(int newCapacity){
  2.     扩容;
  3.     newTable = new Entry[newCapacity];
  4.     transfer(newTable,rehash);    
  5.     threshold = 0.75*newCapacity;
  6.     table = newTable;
  7. }
  8. void transfer(newtab,rehash){
  9.     int newcapacity = newtab.length;
  10.     for (e at table){
  11.         while(null != e){
  12.             // 重新计算hash值，数据从老表迁移到新表
  13.             next = e.next;
  14.             if(rehash){
  15.                 e.hash==null?0:hash(e.key);
  16.             }
  17.             int i = indexFor(e.hash,newCapacity);
  18.             newTable[i] = e;
  19.             e=next;
  20.         }
  21.     }
  22. }

jdk1.8
  1. void resize(){
  2.     计算new阈值,newCapacity, 初始化table;
  3.     table = newTable
  4.     // 执行迁移
  5.     for (e at oldTable){
  6.         if(e.next==null) {
  7.             直接put到newTable;
  8.         }else if (e instance of TreeNode){
  9.             // spilt树到新表
  10.             ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
  11.         }else{
  12.             // 单链表迁移
  13.             while(e.next !=null){
  14.                 // hashmap的老数据 迁移后 桶下标 = 旧下标或者 (旧下标+扩容长度)
  15.                 if(e.hash & oldCap == 0){
  16.                     table[i] = oldTable[i]; //此时全局变量table已指向新表
  17.                 }else{
  18.                     table[i] = oldTable[i+newCap/2]
  19.                 }
  20.             }            
  21.         }
  22.     }  
  23. }

// todo putTreeVal 和 tree.splite 两个源码？