哈希表表（Hashtable，散列表），是根据关键码值(Keyvalue)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash)函数。
举个例子：统计s="fsgererhgerh"中字符出现次数（其中s只包含小写字母）
我们通常会使用这样的数组：int[]freq=newint[26];
这个freq就是一个哈希表
其中每一个字符都和一个索引对应：
哈希表设计思想：
哈希表充分体现了算法设计领域的经典思想：空间换时间。
哈希表是空间和时间之间的平衡
哈希函数的设计十分重要
“键”通过哈希函数得到的“索引”分布越均匀越好
哈希函数的设计哈希函数设计原则：
1.一致性：如果a==b,则hash(a)==hash(b)，反之，则不成立
2.高效性：计算高效简便
3.均匀性：哈希值均匀分布
整数小范围正整数：
直接使用
小范围负整数：
进行偏移，比如[-,]，左右区间都+，进行偏移，得到[0,]
大整数：比如身份证号
通常做法：取模
1.取后4位，相当于mod00--获得
2.取后6位，相当于mod0000--获得，但是获取的数据不可能超过32万，因为在身份证中19为表示的是一个月的某一天，最大值是31，即所谓分布不均匀问题;只取后6位，就没有利用所有信息。
3.解决2中的两个问题的简单解决办法：模一个素数
浮点型浮点型在计算机中也是32位或者64位的二进制表示的，只不过是计算机解析成浮点数的，因此，可以根据浮点数的二进制表示，转化为整数。
字符串转换成整型处理
""--1*10^2+6*10^1+3*10^0
"code"--c*26^3+o*26^2+d*26^1+e*26^0
"code"也可以这样转换：
"code"--c*B^3+o*B^2+d*B^1+e*B^0
(26和B都是进制，合理选择进制即可)
因此有如下哈希函数：
hash("code")=(c*B^3+o*B^2+d*B^1+e*B^0)%M
进一步转化：
hash("code")=(((c*B+o)*B+d)*B+e)%M
(((c*B+o)*B+d)*B+e)数据有可能过大，再进一步进行转化：
hash("code")=((((c%M)*B+o)%M*B+d)%M*B+e)%M
对应代码如下：
inthash=0;for(inti=0;is.length();i++){hash=(hash*B+s.charAt(i))%M;}复合类型
转化成整型处理
比如：对于自定义的Date
classDate{intyear;intmonth;intday;}
hash(date)=(((date.year%M)*B+date.month)%M*B+date.day)%M
注意：以上都是都是转化为整型处理，但这并不是唯一的方法。
Java中hashCode方法Java中hashCode函数的使用
publicclassMain{publicstaticvoidmain(String[]args){Integera=newInteger(3);System.out.println(a.hashCode());//3Integerb=newInteger(-3);System.out.println(b.hashCode());//-3Doublec=newDouble(.4);System.out.println(c.hashCode());//--Strings="abcd";System.out.println(s.hashCode());//}}
在自定义对象中重写hashCode函数
publicclassStudent{privateintid;privatedoublescore;privateStringname;publicStudent(intid,doublescore,Stringname){this.id=id;this.score=score;this.name=name;}
OverridepublicinthashCode(){intB=26;inthash=0;hash=hash*B+id;hash=hash*B+((Double)score).hashCode();//忽略name的大小写问题hash=hash*B+name.toLowerCase().hashCode();returnhash;}}publicclassMain2{publicstaticvoidmain(String[]args){Students=newStudent(1,90.0,"aaa");System.out.println(s.hashCode());//-Students2=newStudent(1,90.0,"aaa");System.out.println(s2.hashCode());//-}}
重写equals()方法
检查是否为同一个对象的引用，如果是直接返回true；
检查是否是同一个类型(判断Class对象是否相同)，如果不是，直接返回false；
将Object对象进行转型
判断每个关键域是否相等
Overridepublicbooleanequals(Objectobj){if(this==obj){returntrue;}if(obj==nullthis.getClass()!=obj.getClass()){returnfalse;}Studentanother=(Student)obj;returnthis.id==another.idthis.score==another.scorethis.name.toLowerCase().equals(another.name.toLowerCase());}
publicclassMain2{publicstaticvoidmain(String[]args){Students=newStudent(1,90.0,"aaa");System.out.println(s.hashCode());//-Students2=newStudent(1,90.0,"aaa");System.out.println(s2.hashCode());//-//s和s2的地址是不同的，但是内容是相同的System.out.println(s==s2);//falseSystem.out.println(s.equals(s2));//true}}
注意：Java中每个对象默认有默认的hashCode实现。hashCode就是该对象的地址。
重写hashCode的情况：
Students=newStudent(1,90.0,"aaa");System.out.println(s.hashCode());//-Students2=newStudent(1,90.0,"aaa");System.out.println(s2.hashCode());//-
未重写hashCode的情况:
Students=newStudent(1,90.0,"aaa");System.out.println(s.hashCode());//Students2=newStudent(1,90.0,"aaa");System.out.println(s2.hashCode());//
s和s2的hashCode不同，因为s和s2的地址不同。
哈希冲突的处理SeperateChaining计算哈希值(hashCode(k1)0x7fffffff)%M
采用查找表解决哈希冲突，查找表也可以使用平衡树结构
使用HashMap作为查找表
注意：
1.Java8之前，每个位置对应一个链表
2.Java8之后，当哈希冲突达到一定程度，每个位置从链表转成红黑树
哈希表编程publicclassHashTableK,V{privateTreeMapK,V[]hashtable;privateintM;privateintsize;publicHashTable(intM){this.M=M;this.size=0;this.hashtable=newTreeMap[M];for(inti=0;iM;i++){hashtable=newTreeMap();}}publicHashTable(){this(97);}privateinthash(Kkey){return(key.hashCode()0x7fffffff)%M;}publicintgetSize(){returnsize;}}
哈希表具体功能实现
publicvoidadd(Kkey,Vvalue){TreeMapK,Vmap=hashtable[hash(key)];if(map.containsKey(key)){map.put(key,value);}else{map.put(key,value);size++;}}publicVremove(Kkey){TreeMapK,Vmap=hashtable[hash(key)];Vret=null;if(map.containsKey(key)){ret=map.remove(key);size--;}returnret;}publicvoidset(Kkey,Vvalue){TreeMapK,Vmap=hashtable[hash(key)];if(!map.containsKey(key)){thrownewIllegalArgumentException(key+"doesnotexist!");}map.put(key,value);}publicbooleancontains(Kkey){returnhashtable[hash(key)].containsKey(key);}publicVget(Kkey){returnhashtable[hash(key)].get(key);}
哈希表链表法时间复杂度分析
哈希表的动态空间处理publicclassHashTable2K,V{privatestaticfinalintupperTol=10;privatestaticfinalintlowerTol=2;privatestaticfinalintinitCapacity=7;privateTreeMapK,V[]hashtable;privateintM;privateintsize;publicHashTable2(intM){this.M=M;this.size=0;this.hashtable=newTreeMap[M];for(inti=0;iM;i++){hashtable=newTreeMap();}}publicHashTable2(){this(initCapacity);}privateinthash(Kkey){return(key.hashCode()0x7fffffff)%M;}privatevoidresize(intnewM){TreeMapK,V[]newHashtable=newTreeMap[newM];for(inti=0;inewM;i++){newHashtable=newTreeMap();}intoldM=M;this.M=newM;for(inti=0;ioldM;i++){TreeMapK,Vmap=hashtable;for(Kkey:map.keySet()){newHashtable[hash(key)].put(key,map.get(key));}}hashtable=newHashtable;}publicintgetSize(){returnsize;}publicvoidadd(Kkey,Vvalue){TreeMapK,Vmap=hashtable[hash(key)];if(map.containsKey(key)){map.put(key,value);}else{map.put(key,value);size++;if(size=upperTol*M){resize(2*M);}}}publicVremove(Kkey){TreeMapK,Vmap=hashtable[hash(key)];Vret=null;if(map.containsKey(key)){ret=map.remove(key);size--;if(sizelowerTol*MM/2=initCapacity){resize(M/2);}}returnret;}publicvoidset(Kkey,Vvalue){TreeMapK,Vmap=hashtable[hash(key)];if(!map.containsKey(key)){thrownewIllegalArgumentException(key+"doesnotexist!");}map.put(key,value);}publicbooleancontains(Kkey){returnhashtable[hash(key)].containsKey(key);}publicVget(Kkey){returnhashtable[hash(key)].get(key);}}
时间复杂度分析：
平均时间复杂度：O(1)
实际上每个操作的时间复杂度是：O(log(lowerTol))~O(log(upperTol)),而lowerTol和upperTol都是常数。
优化哈希表publicclassHashTable3K,V{//哈希表容量的常量表privatefinalint[]capacity={53,97,,,,,,,,,,,,,,,,,,,,663319,,,,};//int类型的最大素数就是privatestaticfinalintupperTol=10;privatestaticfinalintlowerTol=2;privateintcapacityIndex=0;privateTreeMapK,V[]hashtable;privateintM;privateintsize;publicHashTable3(){this.M=capacity[capacityIndex];this.size=0;this.hashtable=newTreeMap[M];for(inti=0;iM;i++){hashtable=newTreeMap();}}privateinthash(Kkey){return(key.hashCode()0x7fffffff)%M;}privatevoidresize(intnewM){TreeMapK,V[]newHashtable=newTreeMap[newM];for(inti=0;inewM;i++){newHashtable=newTreeMap();}intoldM=M;this.M=newM;for(inti=0;ioldM;i++){TreeMapK,Vmap=hashtable;for(Kkey:map.keySet()){newHashtable[hash(key)].put(key,map.get(key));}}hashtable=newHashtable;}publicintgetSize(){returnsize;}publicvoidadd(Kkey,Vvalue){TreeMapK,Vmap=hashtable[hash(key)];if(map.containsKey(key)){map.put(key,value);}else{map.put(key,value);size++;if(size=upperTol*McapacityIndex+1capacity.length){capacityIndex++;resize(capacity[capacityIndex]);}}}publicVremove(Kkey){TreeMapK,Vmap=hashtable[hash(key)];Vret=null;if(map.containsKey(key)){ret=map.remove(key);size--;if(sizelowerTol*McapacityIndex-1=0){capacityIndex--;resize(capacity[capacityIndex]);}}returnret;}publicvoidset(Kkey,Vvalue){TreeMapK,Vmap=hashtable[hash(key)];if(!map.containsKey(key)){thrownewIllegalArgumentException(key+"doesnotexist!");}map.put(key,value);}publicbooleancontains(Kkey){returnhashtable[hash(key)].containsKey(key);}publicVget(Kkey){returnhashtable[hash(key)].get(key);}}设计的哈希表中的不足
Java8之前，每一个位置对应一个链表，K不要求具有可比性,所以是无序的。
Java8之后，当哈希冲突得到一定程度时，每一个位置从链表转化成红黑树，这时就要求K具有可比性。
开放地址法解决哈希冲突1.线性探测法每次遇到哈希冲突，就+1
2.平方探测法遇到哈希冲突,就+1
再次遇到哈希冲突，就+4
再次遇到哈希冲突，就+9
...
3.二次哈希每次遇到哈希冲突，就+hash2(key)
其他解决哈希冲突的方法：
再哈希法Rehashing
CoalescedHashing(综合了开放地址法和链地址法)
预览时标签不可点收录于话题#个上一篇下一篇