的实现。在前面的文章中，我们学习了Map基于数组、链表、二叉树、红黑树的操作。在本文中，我们将学习如何基于哈希表实现Map来实现Map，该方法对应java中的HashMap，也是使用最广泛的方法。Map的哈希表实现主要分为两步：根据哈希函数将搜索到的key转化为数组下标，并对哈希值进行处理遇到冲突时，处理冲突的方式有两种：zipper和线性检测hash功能。实现哈希表的第一步是考虑如何将键转换为数组下标。这时候就需要用到哈希函数，先将键值转化为整数，然后用求余法计算数组的下标。我们需要为每种类型的密钥使用不同的哈希函数。java中常用的数据类型已经实现了HashCode。我们只需要根据hashCode的值使用除法取余的方法，将其转化为数组下标即可。java中的约定：如果两个对象的equals相等，则hashCode必须相同；如果hashCode相同，则equals不一定相同。对于自定义类型的key，我们通常需要自定义hashCode和equals；默认的hashCode返回对象的内存地址，这种hash值不是很好。下面我来看一下Java中常用的hashCode计算方法。Integer由于hashCode需要返回的值是一个int值，所以Integer的hashCode的实现很简单，直接返回当前值}LongJava中Long类型的hashCode计算是先将无符号的值右移32位，然后与值异或，保证每一位都用到，最后转成int值@OverridepublicinthashCode(){returnLong.hashCode(value);}publicstaticinthashCode(longvalue){return(int)(value^(value>>>32));}Double,Float浮点型keyjava的hashCode实现是将keys表示为binarypublicstaticinthashCode(floatvalue){returnfloatToIntBits(value);}publicstaticintfloatToIntBits(floatvalue){intresult=floatToRawIntBits(value);//检查NaNbasedonvaluesofbitfields,maximum//exponentandnonzerosignificant.)&&(result&FloatConsts.SIGNIF_BIT_MASK)!=0)result=0x7fc00000;returnresult;}Stringjava每个char都可以表示为int值，所以字符串转为int值publicinthashCode(){inth=hash;if(h==0&&value.length>0){charval[]=value;for(inti=0;iimplementsMap{privateintsize;privateLinkedMap[]table;publicSeparateChainingHashMap(intcapacity){this.table=(LinkedMap[])newLinkedMap[容量];对于(inti=0;i();}}@Overridepublicvoidput(Kkey,Vvalue){this.table[hash(key)].put(key,价值);大小++;}privateinthash(Kkey){return(key.hashCode()&0x7fffffff)%table.length;}@OverridepublicVget(Kkey){returnthis.table[hash(key)].get(key);}@Overridepublicvoiddelete(kkey){this.table[hash(key)].delete(key);size--;}@Overridepublicintsize(){returnsize;}}这个hash函数使用key的hashCode和上0x7fffffff得到一个非-负整数，然后用求余法计算数组的下标。其中0x7FFFFFFF的二进制表示除了第一位为0，其余均为1，也就是说这是最大的整数int（因为第一位是符号位，0表示是正数number)，可以用Integer.MAX_VALUE代替哈希表的主要目的是将键值均匀分布到数组中，所以哈希表是无序的。如果你需要的Map需要支持提取最大值和最小值，那么哈希表就不适合了。我们这里实现的压缩哈希表的数组大小是固定的，但通常随着数据量的增加，较短的数组发生碰撞的概率会增加，所以数组需要支持动态扩展。展开后，需要将原来的值重新插入到展开后的数组中。数组的扩展可以参考之前的文章《老哥是时候来复习下数据结构与算法了》线性检测哈希表哈希表的另一种实现方式是使用大小M来存储N个键值，其中M>N；解决碰撞冲突，需要利用空位；这种方法最简单的实现是线性探测。线性检测的主要思想：插入key时，发生碰撞后，直接在index中加1，检查下一个位置。这时候会出现三种情况：下一个位置等于要插入的key，然后修改value。如果一个位置不等于要插入的key，则在索引中加一，继续查找。如果下一个位置还是一片空白，那么直接把要插入的对象放到这个空白处。初始化线性检测哈希表，使用两个数组存储key和value，capacity表示初始化数组的大小.keys=(K[])newObject[capacity];this.values=(V[])newObject[capacity];}Insert当插入key的位置超过数组大小时，需要回数组的开头并继续搜索，直到找到一个为空的位置；index=(index+1)%capacity当数组的存储容量超过数组总容量的一半时，需要扩容到原来的两倍@Overridepublicvoidput(Kkey,Vvalue){if(Objects.isNull(键)){thrownewIllegalArgumentException("Keycannotnull");}if(this.size>this.capacity/2){resize(2*this.capacity);}intindex;for(index=hash(key);this.keys[index]!=null;index=(index+1)%capacity){if(this.keys[index].equals(key)){this.values[index]=value;return;}}this.keys[index]=key;this.values[index]=value;size++;}动态调整数组大小我们可以参考上篇文章实现的动态调整数据大小《老哥是时候来复习下数据结构与算法了》；在线性检测中，需要将原始数据重新插入到扩展数据中，因为数组的大小发生变化，需要重新计算索引。privatevoidresize(intcap){LinearProbingHashMaplinearProbingHashMap=newLinearProbingHashMap<>(cap);for(inti=0;i7->9，删除7后，如果不重新插入7的位置，则get方法将无法查询到元素9；每次删除后，需要检测数组中实际元素的个数。收缩操作；@Overridepublicvoiddelete(Kkey){if(Objects.isNull(key)){抛出newIllegalArgumentException("Keycannotnull");}intindex;for(index=hash(key);this.keys[index]!=null;index=(index+1)%capacity){if(this.keys[index].equals(key)){this.keys[index]=null;this.values[index]=null;break;}}for(index=(index+1)%capacity;this.keys[index]!=null;index=(index+1)%capacity){this.size--;this.put(this.keys[index],this.values[index]);this.keys[index]=null;this.values[index]=null;}this.size--;if(size>0&&size
