似乎是最适用的hashtable知识总结

哈希表:将工具转换为索引,然后存储在数组中。

界说注重点:

  • 工具:就是面向工具中的工具,可以为任何东西。整数、浮点数、日期、字符串、类。
  • 转换:通过hash函数来完成,hash函数是hash表的焦点与难点。对于整数,可以将取模运算作为hash函数
  • 数组:hash表本质是就是一个数组(静态、动态),这也是名称中”表”的寄义。

体现的盘算机头脑: 空间换时间

思索角度,当空间无限时,可以使用O(1)完成各项操作,当空间只要1个时,就退化为线性表O(n)。

哈希表关注的焦点问题

  • 哈希函数若何设计
  • 若何解决hash冲突

对于差别的关键字得到了统一个hash地址,这种征象称为hash冲突(collision),形式化为:key1≠key2,f(key1)==f(key2),其中f为hash函数。

hash函数的设计原则

  • 一致性:若是a==b,则hash(a)==hash(b),这是java自界说类时必须需重写的hashcode方式缘故原由。

  • 高效性:盘算高效便捷,O(1),这也是使用动态数组,在适当的情况下resize的缘故原由。

  • 平均性哈希值的漫衍越平均越好这就是取模法中模为质数的缘故原由

整数转换为索引的方式:取模法

hashcode=val%M,其中M为一个质数,M的参考取值请点击这儿。注重,公式总val为正整数,若是类型为int,可以先举行去除符号操作:val=val&ox7fffffff。由于从二进制的角度看ox7fffffff就是0和31个1,正好把符号位过滤掉。

任何工具都可以示意为整数。

  • 浮点数:在盘算机内部都是用32位或者64位二进制示意,从整数的角度去剖析这些位,就找到了浮点数对应的整数。
  • 字符串:字符串本质上可以理解为B(base)进制数,其中B可以是差别字符串的个数。例如26。也可以是随便设定的一个质数。
    • 例如:code=c*26^3+o*26^2+d*26^1+e*26^0
    • 例如:abcd=a*B^3+b*B^2+c*B^1+d*B^0

进制示意的形式简化以及编程实现:

hash(code)=(c*B^3+o*B^2+d*B^1+e*B^0)%M,可以示意为每一位乘以base,在加下一位

=((((c*B+o)*B+d)*B+e)%M,很主要,在java字符串的hashcode方式中B=31

=((((c%M)*B+o)%M*B+d)%M*B+e)%M,取余操作可以拿到括号内里去。(此性子快速幂算法中很常用)

C++中const的特性

int hash=0;
for(int i=0;i<s.length;i++){
    hash=(hash*B+s.charAt(i))%M;
}
//java中B的是31,不在乎是否溢出,只要返回的是一个整数就OK,不知道M是什么,以是就没有泛起M。
  • 日期类型思量每个部门,每部门示意差别的权重(进制头脑)。

    • Date: year,month,day,则hash(date)=(((date.year%M)*B+date.month%M)*B+date.day)%M
  • 分别将类的每一个字段当做B进制中的某一位。依据B进制数举行转换。

当将自界说的类作为hashmap和hashSet的Key时,必须重写hashcode方式和equal方式。

1.由于默认的hashcode()方式取工具的地址为基础获得的,而new()统一类的差别实例工具地址差别,使得hashcode的效果也差别,这就不满足一致性,例如,new Person(“小明”)两次,它们的hashcode差别,但这显然就不合理。

2.重写hashcode()只是为了获得准确的hash值,但当冲突了,还需要逐个字段举行对照才气确定是否相等,这就要求重写equal来完成,由于默认的equal就即是==,寄义为对照工具地址。

自界说hashcode和equals的实例

基本思路行使已有基本类型的包装类和String类的hashcode()方式来天生我们的hashcode()

public class Student {
    Integer grade;
    Integer cls;
    String name;
//省去无关代码
    @Override
    public int hashCode() {//套路:模拟String,Base取31
        int B=31;
        int hash=0;
        hash=hash*B+grade.hashCode();
        hash=hash*B+cls.hashCode();
        hash=hash*B+name.hashCode();
        return hash;
    }

    @Override
    public boolean equals(Object obj) {//有套路,逐个字段对照
        if(this==obj) return true;
        if(obj==null)return false;
        if(this.getClass()!=obj.getClass()) return  false;
        Student another=(Student) obj;
        return this.grade.equals(another.grade) &&
                this.cls.equals(another.cls) &&
                this.name.equals(another.name);//字符串对照相等,equals
    }
}

完整代码以及测试用例,请点击这儿

hash冲突的解决方式:链地址法

数组中每个元素保留的是地址。数组中每个元素的位置是N%M

去掉符号位:hashcode(k1)&0X7FFFFFFF

动态空间(扩容和缩容)处置N/M>=upperTolN/M<lowerTol

实现自己的hashtable,接纳TreeMap作为链接冲突元素的容器

都是先获得key索引,然后再获某个元素。TreeMap<K,V> map=hashtable[hash(key)]

完整源码及测试代码请点击这儿

更多关于hash冲突的设施

  1. 开放地址法。
  2. 再哈希法:rehashing.

原创文章,作者:admin,如若转载,请注明出处:https://www.2lxm.com/archives/7928.html