1。什么是哈希表？哈希表是由哈希算法和其他数据结构组成的数据结构。为什么会有这样的数据结构呢？主要原因是在理想情况下，取出和放入元素所消耗的时间复杂度为\(O(1)\)例如我们看一个常见的实现方式，哈希算法+数组+组成的哈希表链表：假设数组索引从1开始，那么根据哈希算法，元素1放在数组下标为1的地方，元素3放在数组??下标为3的地方，元素5放在数组下标为1的地方，但是因为元素1已经在数组中了，针对这种情况，我们的解决方案之一是通过链表把元素1和元素5连接起来，元素1还在数组，新加入的元素5放在元素1的后面，元素1的下一个节点指向元素5.2。java实现哈希表的用途非常广泛，比如java的HashMap和HashSet。对于哈希表，我们的操作主要是PUT和GET操作。让我们来看看如何实现一个简单版本的HashMap。importjava.util.Arrays;importjava.util.Objects;/***keyandvaluearenotpermittednull*@authorbennetty74*@since2021.10.24*/publicclassHashMapimplementsMap{//声明一个ENTRY数组用于存储释放元素privateEntry[]entries;privatefinaldoubleloadFactor=0.75d;私有int容量=8；私有整数大小=0；@SuppressWarnings("unchecked")publicHashMap(){entries=newEntry[this.capacity];}@SuppressWarnings("unchecked")publicHashMap(intcapacity){this.capacity=capacity;条目=新条目[容量]；}@Overridepublicbooleancontains(Kkey){intidx=getIndex(key);如果（条目[idx]==null）{返回假；}条目条目=条目[idx];while(entry!=null){if(entry.key.equals(key)){返回真；}条目=条目.下一个；}返回假；}//put操作，不允许key和value为nullpublicbooleanput(Kkey,Vvalue){if(Objects.isNull(key)||Objects.isNull(value)){thrownewIllegalArgumentException("Keyorvalue一片空白”）;}intidx=getIndex(键);//如果为null，则放入条目数组if(Objects.isNull(entries[idx])){entries[idx]=newEntry<>(key,value);}else{//else放在Entry列表的头部EntrynewEntry=newEntry<>(key,value);newEntry.next=条目[idx];条目[idx]=newEntry;}//如果负载因子大于0.75，则重新哈希if(size++/(double)capacity>0.75f){rehash();}返回真；}privatevoidrehash(){容量=2*容量；条目[]oldEntries=Arrays.copyOf(this.entries,capacity);条目=新条目[容量]；for(EntryoldEntry:oldEntries){if(oldEntry!=null){put(oldEntry.key,oldEntry.value);}}}publicVget(Kkey){if(Objects.isNull(key)){thrownewIllegalArgumentException("Keyisnull");}//通过key的hashCode获取idxintidx=getIndex(key);条目条目=条目[idx]；如果(!Objects.isNull(entry)){而(!Objects.isNull(entry)){如果(key.equals(entry.key)){返回entry.value;}条目=条目.下一个；}}//没有找到具体的key，返回nullreturnnull;}//这里的hash算法很简单，就是将key的hashCode除以入口数组容量的余数作为数组下标存放元素privateintgetIndex(Kkey){returnkey.hashCode()%容量；}@OverridepublicStringtoString(){StringBuildersb=newStringBuilder();sb.append("HashMap{");for(inti=0;i条目=条目[i];while(entry!=null){sb.append(entry.key).append("=").append(entry.value).append(",");条目=条目.下一个；}}}sb.replace(sb.length()-1,sb.length(),"").append("}");返回sb.toString();}//Entry类，包含HashMap的key和valueprivatestaticclassEntry{Kkey;V值；publicEntry(Kkey,Vvalue){this.key=key;this.value=值；}接下来是条目；}}
