编程进阶网

目录介绍

01.Hash是啥
02.Hash冲突
03.Hash案例
04.判断两个对象相等
05.Java中的应用场景

好消息

博客笔记大汇总【15年10月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！所有博客陆续更新到GitHub上！
链接地址：https://github.com/yangchong211/YCBlogs
如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.Hash是啥

1.0 Hash通俗解释

Hash，一般翻译做“散列”，也有直接音译为“哈希”的，就是把任意长度的输入，通过散列算法，变换成固定长度的输出，该输出就是散列值。根据散列值作为地址存放数据，这种转换是一种压缩映射，简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。查找关键字数据（如K）的时候，若结构中存在和关键字相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。我们称这个对应关系f为散列函数(Hash function)，按这个事件建立的表为散列表。
综上所述，根据散列函数f(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。

1.1 Hash的定义

散列（哈希）函数
- 把任意长度的输入（又叫做预映射pre-image）通过散列算法变换成固定长度的输出，该输出就是散列值，是一种压缩映射。
- 或者说一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。

1.2 Hash函数特性

h(k1)≠h(k2)则k1≠k2，即散列值不相同，则输入值即预映射不同
- 如果k1≠k2，h(k1)=h(k2) 则发生碰撞；
- 如果h(k1)=h(k2)，k1不一定等于k2；

1.3 Hash的使用场景

比如说我们下载一个文件，文件的下载过程中会经过很多网络服务器、路由器的中转，如何保证这个文件就是我们所需要的呢？我们不可能去一一检测这个文件的每个字节，也不能简单地利用文件名、文件大小这些极容易伪装的信息，这时候，就需要一种指纹一样的标志来检查文件的可靠性，这种指纹就是我们现在所用的Hash算法(也叫散列算法)。
散列算法就是一种以较短的信息来保证文件唯一性的标志，这种标志与文件的每一个字节都相关，而且难以找到逆向规律。因此，当原有文件发生改变时，其标志值也会发生改变，从而告诉文件使用者当前的文件已经不是你所需求的文件。
这种标志有何意义呢？之前文件下载过程就是一个很好的例子，事实上，现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。

02.Hash冲突

对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称hash冲突。即：key1通过f(key1)得到散列地址去存储key1，同理，key2发现自己对应的散列地址已经被key1占据了。解决办法（总共有四种）：
1.开放寻址法
- 所谓的开放定址法就是一旦发生了冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将记录存入。
- 开放寻址法：Hi=(H(key) + di) MOD m,i=1,2,…，k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：
  - 1)．di=1,2,3,…，m-1，称线性探测再散列；
  - 2)．di=1^2,(-1)^2,2^2,(-2)^2,(3)^2,…，±(k)^2,(k<=m/2)称二次探测再散列；
  - 3)．di=伪随机数序列，称伪随机探测再散列。
- 用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术（线性探测法、二次探测法（解决线性探测的堆积问题）、随机探测法（和二次探测原理一致，不一样的是：二次探测以定值跳跃，而随机探测的散列地址跳跃长度是不定值））在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止插入即可。
- 比如说，我们的关键字集合为{12,67,56,16,25,37,22,29,15,47,48,34},表长为12。我们用散列函数f(key) = key mod l2 　　当计算前S个数{12,67,56,16,25}时，都是没有冲突的散列地址，直接存入：　　计算key = 37时，发现f(37) = 1，此时就与25所在的位置冲突。　　于是我们应用上面的公式f(37) = (f(37)+1) mod 12 = 2。于是将37存入下标为2的位置：
2.再哈希
- 再哈希法又叫双哈希法，有多个不同的Hash函数，当发生冲突时，使用第二个，第三个，….，等哈希函数去计算地址，直到无冲突。虽然不易发生聚集，但是增加了计算时间。
3.链地址法(Java hashmap就是这么做的)
- 链地址法的基本思想是：每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，将所有关键字为同义词的结点链接在同一个单链表中，如：
- 设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：
4.建立一个公共溢出区
- 这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

03.Hash案例

代码如下所示

/**
 * Person类
 * 重写hashCode方法和equals方法
 * hashCode方法计算该对象的散列码
 * Java中每个对象都有一个散列码
 */
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;
    }
}

测试代码

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);
        }
    }
}

04.如何判断两个对象相等

4.1 判断两个字符串

使用equals方法判断两个字符串是否相等

String a = "yc1";
String b = "yc2";
boolean isEqual = a.equals(b);

当然Object的子类可以通过重写equals的方法，实现子类自身的对象是否相等的逻辑；String是Object的子类，查看下它的equals方法

//在Object类中
public boolean equals(Object obj) {
    //直接比较的是地址
    return (this == obj);
}

//在String类中
public boolean equals(Object anObject) {
    //直接比较的是地址
    if (this == anObject) {
        return true;
    }
    //盘旋是否是字符串String类型
    if (anObject instanceof String) {
        String anotherString = (String) anObject;
        int n = count;
        if (n == anotherString.count) {
            int i = 0;
            //循环判断每个字符是否相等
            while (n-- != 0) {
                if (charAt(i) != anotherString.charAt(i))
                        return false;
                i++;
            }
            return true;
        }
    }
    return false;
}

4.2 判断两个int数值

Integer类的equals方法又是如何实现的呢？

Integer a = Integer.valueOf("1");
Integer b = Integer.valueOf("2");
boolean ab = a.equals(b);


public boolean equals(Object obj) {
    //先判断是否是Integer类型
    if (obj instanceof Integer) {
        //转为int值后进行比较
        return value == ((Integer)obj).intValue();
    }
    return false;
}

4.3 其他基本类型

如下所示

//short类型
@Override
public int hashCode() {
    return Short.hashCode(value);
}
public static int hashCode(short value) {
    return (int)value;
}


//Byte类型
@Override
public int hashCode() {
    return Byte.hashCode(value);
}
public static int hashCode(byte value) {
    return (int)value;
}

//Long类型
@Override
public int hashCode() {
    return Long.hashCode(value);
}
public static int hashCode(long value) {
    return (int)(value ^ (value >>> 32));
}
//long类型作为索引范围太大，需要转为int类型。这里简单的获取低32位容易导致散列不均，因为高位部分没有被利用。所以这里采用逻辑右移32位，让高32位和低32位进行XOR操作，导致高位低位都能被利用到

//Boolean类型
@Override
public int hashCode() {
    return Boolean.hashCode(value);
}
public static int hashCode(boolean value) {
    return value ? 1231 : 1237;
}
//采用两个质数作为true或false的索引。这两个质数足够大，用来作为索引时，出现碰撞的可能性低。

05.Java中的应用场景

5.1 equals与hashCode有两个注意点

equals相同，则hashCode相同；而hashCode相同，equals不一定相同
- 如果equals相同，hashCode不相同，有可能会造成上述重复值等情况，这种情况是不允许的；
- 而hasCode相同，但是equals不一定相同，有可能是因为发生了碰撞而碰撞是有可能性发生的

5.2 以HashSet为例说明hashCode()的作用

假设，HashSet中已经有1000个元素。当插入第1001个元素时，需要怎么处理？
- 因为HashSet是Set集合，它允许有重复元素。“将第1001个元素逐个的和前面1000个元素进行比较”？
- 显然，这个效率是相等低下的。散列表很好的解决了这个问题，它根据元素的散列码计算出元素在散列表中的位置，然后将元素插入该位置即可。对于相同的元素，自然是只保存了一个。
- 由此可知，若两个元素相等，它们的散列码一定相等；但反过来确不一定。在散列表中，
  - 1、如果两个对象相等，那么它们的hashCode()值一定要相同；
  - 2、如果两个对象hashCode()相等，它们并不一定相等。
  - 注意：这是在散列表中的情况。在非散列表中一定如此！

5.3 以HashMap为例说明Hash的作用

在HashMap中有许多地方用到了hash算法

//put方法
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

//remove方法
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

//get方法
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

//上面这几个方法都用到了这个方法
static final int hash(Object key) {
    int h;
    //计算hashCode，并无符号移动到低位
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

举个例子: h = 363771819^(363771819 >>> 16)
0001 0101 1010 1110 1011 0111 1010 1011(363771819)
0000 0000 0000 0000 0001 0101 1010 1110(5550) XOR
--------------------------------------- =
0001 0101 1010 1110 1010 0010 0000 0101(363766277)
这样做可以实现了高地位更加均匀地混到一起

01.关于博客汇总链接

02.关于我的博客

github：https://github.com/yangchong211
知乎：https://www.zhihu.com/people/yczbj/activities
简书：http://www.jianshu.com/u/b7b2c6ed9284
csdn：http://my.csdn.net/m0_37700275
喜马拉雅听书：http://www.ximalaya.com/zhubo/71989305/
开源中国：https://my.oschina.net/zbj1618/blog
泡在网上的日子：http://www.jcodecraeer.com/member/content_list.php?channelid=1
邮箱：yangchong211@163.com
阿里云博客：https://yq.aliyun.com/users/article?spm=5176.100- 239.headeruserinfo.3.dT4bcV
segmentfault头条：https://segmentfault.com/u/xiangjianyu/articles
掘金：https://juejin.im/user/5939433efe88c2006afa0c6e