Hash算法,哈希算法是什么?hash算法详解

TheDisguiser 2020-08-25 14:40:18 java常见问答 7463

算法是一门语言进阶的基石,hash算法可谓是最经典的算法之一了,小伙伴们知道它吗?今天,小编就带大家了解一下它。

哈希(Hash)我们一般也叫它散列,具体就是指把任意长度的输入,通过散列算法,变换成一个固定长度的输出,这个输出的值就是散列值。

哈希表

哈希表(Hash table,也叫散列表),指根据键值对(Key value)而直接进行访问的数据结构。具体就是,它通过把关键码值映射到表中一个位置从而来访问记录,加快查询速度。这个映射函数就叫做散列函数,而存放记录的数组叫做散列表。

Hash函数

一个合格的Hash函数应满足下列要求:

a、一致性 —— 等价(equal)的key必然产生相等的hash code

b、高效性 —— 高效的计算

c、均匀性 —— 均匀地散列所有的key

Hash查询算法有两步:

1、把Hash函数将要被查找的键转化为数组中一个索引。一般情况下,不同的键都能转化为不同的索引值。只是一般情况下,因此我们需要面对两个或多个键都会散列到相同的索引值的情况。

2、处理碰撞冲突的过程

实例:

Pojo类

package my.hash;
/**
 * Person类
 * 重写hashCode方法和equals方法
 * hashCode方法计算该对象的散列码
 * Java中每个对象都有一个散列码
 * @author ASUS
 *
 */
public class Person
{
    private String name;
    private int age;
    //set和get方法
    public String getName()
    {
        return name;
    }
    public void setName(String name)
    {
        this.name = name;
    }
    public int getAge()
    {
        return age;
    }
    public void setAge(int age)
    {
        this.age = age;
    }
    //构造器
    public Person(String name, int age)
    {
        super();
        this.age = age;
        this.name = name;
    }
    //输出方法
    public String toString()
    {
        return "Person [name=" + name + ",age=" + age + "]";
    }
    //重写hashcode方法
    public int hashCode()
    {
        final int prime = 31;
        int result = 1;
        result = prime * result + age;
        result = prime * result + ((name == null) ? 0 : name.hashCode());
        return result;
    }
    /*重写equals方法
     * 重写该方法时必须重写hashCode方法,因为要确保一个对象映射到同一个存储地址
     */
    public boolean equals(Object object)
    {
        if (this == object)
        {
            return true;
        }
        if (object == null)
        {
            return false;
        }
        if (getClass() != object.getClass())
        {
            return false;
        }
        Person other = (Person) object;
        if (age != other.age)
        {
            if (other.name != null)
            {
                return false;
            }
        }
        else if (!name.equals(other.name))
        {
            return false;
        }
        return true;
    }
}

测试类

package my.hash;
import java.util.HashSet;
public class Test
{
    public static void main(String[] args)
    {
        //构造6个person对象
        Person p1 = new Person("sam", 10);
        Person p2 = new Person("amy", 13);
        Person p3 = new Person("lili", 22);
        Person p4 = new Person("daming", 34);
        Person p5 = new Person("a", 2);
        Person p6 = new Person("b", 2);
        //输出a和b的hashcode值
        System.out.println("a的hashcode值:" + p5.hashCode() + "  b的hashcode值:" + p6.hashCode());
        //定义一个HashSet,将Person对象存储在该集合中
        HashSet < Person > set = new HashSet < Person > ();
        //将Person对象添加进HashSet集合中
        set.add(p6);
        set.add(p5);
        set.add(p4);
        set.add(p3);
        set.add(p2);
        set.add(p1);
        //遍历HashSet,若p5和p6的hashCode一致,但是却添加进了集合set,说明hashset底层解决了hash冲突的问题。
        for (Person person: set)
        {
            System.out.println(person);
        }
    }
}

以上就是本篇文章的所有内容,更多java架构师详情快关注奇Q工具网了解。

推荐阅读:

hash算法原理和用途有哪些?

hash算法有哪几种?几种经典的hash算法

hashmap面试题汇总