一、Hash的理解核心优势查找时间复杂度是O1本质原因HashMap 底层基于「数组」实现数组支持随机访问通过哈希函数直接定位到数组下标就能快速找到数据。无哈希冲突时就是O1有冲突时链表/红黑树会退化为OnOlog n底层数据结构key 数据的标识与操作入口value 要存储的数据本体hash key的哈希值定位与冲突处理的工具是计算得到的不是用户直接传进来的链表节点包含next指针红黑树节点包含parentleftright指针流程传入keyHashMap计算出来它的Hash值hash数组长度减一找到数组下标定位到对应的桶遍历桶中的数据结构找到对应节点最后返回这个节点对应的value数组长度为什么必须是2的幂1.如果数组长度是2的幂n-1的二进制全是1等价于去hash的低几位结果分布均匀冲突概率低2.如果不是这样则就会有零出现比如1110那么末尾一定会是0。3.扩容时无需重新计算hash可直接判断节点是否需要移动到新的位置提升扩容效率。只需要遍历对应的桶不需要将所有的部分全部再计算hash值。链表与红黑树的转换规则在单个桶长度大于8时链表会转换为红黑树长度小于6时红黑树转换为链表不是同一个树的原因防止这两个数反复横跳每次转换存储结构都会消耗资源。得到哈希冲突的两种情况纯正的Hash冲突两个不同的keyhashCode的返回值完全相同例如不同字符串的hash值重复。下标冲突伪冲突两个不同的keyhashCode值不同但与数组最大下标n-1做与运算后的数组下标相同二、代码初始练习根据大致功能进行的后期会完善先用取模代替与运算packageHash;//import java.util.HashMap;//K,V代表泛型意思时这个节点可以村任何类型的键和值。classNodeK,V{Kk;Vv;// 声明一个指针 next用来指向下一个 Node。这是拉链法解决冲突的关键它让节点能连成一条链表NodeK,Vnext;inthash;publicNode(Kk,Vv){this.kk;this.vv;this.hash(knull?0:k.hashCode());}}//定义自己的Hash类同样使用泛型k,VpublicclassHashK,V{//声明一个数组table里面存放的元素类型时NodeK,V,这是哈希桶privateNodeK,V[]table;//声明一个静态常量表示数组的默认初始长度必须是2的幂privatestaticfinalintDEFAULT_INITIAL_CAPACITY16;//声明一个静态常量表示负载因子当占有0.75的格子时说明该扩容了privatestaticfinalfloatDEFAULT_LOAD_FACTOR0.75f;//声明一个变量用来记录这个Map里到底存了多少个真实的键值对privateintelementSize;//声明一个变量记录table数组里有多少个格子被占用privateintarrUsedSize;//声明一个变量length用来记录当前数组的总长度16/32/64privateintlength;// Hash 类的构造方法当你 new Hash() 时会执行的代码publicHash(){// 初始化时把当前数组的长度设置为默认的 16lengthDEFAULT_INITIAL_CAPACITY;// 真正向内存申请空间创建一个长度为 16 的 Node 数组赋值给 table。此时里面全都是 nulltablenewNode[length];}// 核心的存入数据方法publicvoidput(Kk,Vv){// 1. 拿到 key 的哈希值inthash(knull)?0:k.hashCode();// 2. 计算下标用哈希值的绝对值对数组长度取模求余数// Math.abs() 是为了防止 hashCode 是负数导致数组越界报错intindexMath.abs(hash)%length;//运用取模来得到在哪个桶里// 3. 去对应的格子里看看原来有没有东西赋给 first 变量NodeK,Vfirsttable[index];// 情况1该位置是空的直接占用新格子if(firstnull){table[index]newNode(k,v);// 创建新节点直接扔进空格子elementSize;// 元素总数 1arrUsedSize;// 占用的格子数 1}// 情况2该位置已经有节点了发生哈希冲突else{// 先看第一个节点的 key 是不是我们要找的比较哈希值和 equals 内容//从前到后判断速度以此降低//先判断哈希值在判断两个对象内存你地址是否完全一样最后判断对象内的内容是否一致if(first.hashhashfirst.kk||first.k.equals(k)){first.vv;// key 完全相同说明你是来“修改”数据的更新 value}// 第一个节点不是你要的说明顺着它后面可能是一条链表顺着链表往下找else{NodeK,Vtempfirst;// 派出一个探路指针 temp从头开始找NodeK,Vnodenull;// 这是一个“标记兵”记录中途有没有找到同样的 key// 只要当前节点的后面还有节点就一直循环往下走while(temp.next!null){temptemp.next;// 指针往后挪一步// 检查挪到的这个节点是不是我们要找的 keyif(temp.hashhashtemp.kk||temp.k.equals(k)){temp.vv;// 找到了同样的 key更新 valuenodetemp;// 把这个节点记给标记兵说明不是新来的break;// 既然找到了就赶紧退出循环不用往下找了}}// 如果整个循环都找完了标记兵 node 还是 null说明这是一张全新的面孔if(nodenull){// 尾插法此时 temp 刚好停在链表的最末尾直接把新节点挂在它的 next 上temp.nextnewNode(k,v);elementSize;// 元素总数 1注意这里不加 arrUsedSize因为没占新格子}}}}//打印出来publicvoidprintMap(){System.out.println(当前状态);System.out.println(元素总数: elementSize, 占用格子数: arrUsedSize);// 遍历这 16 个格子for(inti0;itable.length;i){// 只打印那些装了东西的格子if(table[i]!null){System.out.print(格子 [i] - );NodeK,Vtemptable[i];// 如果格子里有链表就顺着链表一直打印到底while(temp!null){System.out.print({temp.ktemp.v} - );temptemp.next;}System.out.println(null/n);// 链表结尾指向 null}}}// 程序的启动入口main 方法publicstaticvoidmain(String[]args){// 1. 创建你的 Hash 实例HashString,StringmapnewHashString,String();// 2. 正常放入几个不同的 keymap.put(Apple,苹果);map.put(Banana,香蕉);map.put(Applee,苹果e);map.put(Appleee,苹果ee);// 3. 测试覆盖旧的值再次 put Applemap.put(Apple,超级大苹果);// 4. 查看打印结果验证底层结构map.printMap();}}
