文档章节

Hash和HashCode深入理解

潇湘剑雨
 潇湘剑雨
发布于 09/21 14:18
字数 3714
阅读 18
收藏 10

目录介绍

  • 1.Hash的作用介绍
    • 1.1 Hash的定义
    • 1.2 Hash函数特性
    • 1.3 Hash的使用场景
  • 2.如何判断两个对象相等
    • 2.1 判断两个字符串
    • 2.2 判断两个int数值
    • 2.3 其他基本类型
  • 3.HashCode深入分析
    • 3.0 HashCode是什么
    • 3.1 为什么要重写HashCode
    • 3.2 HashCode源代码分析
    • 3.3 HashCode带来的疑问
    • 3.4 HashCode的作用
    • 3.5 HashMap中的HashCode
    • 3.6 可直接用hashcode判断两个对象是否相等
  • 4.Hash表是什么
    • 4.1 Hash表定义
    • 4.2 Hash表简单介绍
  • 5.Hash中的算法应用
    • 5.1 基础算法
    • 5.2 经典算法[摘自网络]
    • 5.3 Hash碰撞[摘自网络]
  • 6.Hash在Java中的应用场景
    • 6.1 equals与hashCode有两个注意点
    • 6.2 以HashSet为例说明hashCode()的作用
    • 6.3 以HashMap为例说明Hash的作用
    • 6.4
  • 7.版本更新情况
  • 8.其他介绍

1.Hash的作用介绍

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算法(也叫散列算法)。
  • 散列算法就是一种以较短的信息来保证文件唯一性的标志,这种标志与文件的每一个字节都相关,而且难以找到逆向规律。因此,当原有文件发生改变时,其标志值也会发生改变,从而告诉文件使用者当前的文件已经不是你所需求的文件。
  • 这种标志有何意义呢?之前文件下载过程就是一个很好的例子,事实上,现在大部分的网络部署和版本控制工具都在使用散列算法来保证文件可靠性。

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

2.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;
}

2.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;
}

2.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的索引。这两个质数足够大,用来作为索引时,出现碰撞的可能性低。


3.HashCode深入分析

3.0 HashCode是什么

  • HashCode是Object的一个方法,hashCode方法返回一个hash code值,且这个方法是为了更好的支持hash表,比如String,Set,HashTable、HashMap等;

3.1 为什么要重写HashCode

  • 如果用 equal 去比较的话,如果存在1000个元素,你 new 一个新的元素出来,需要去调用1000次equal去逐个和他们比较是否是同一个对象,这样会大大降低效率。hashcode实际上是返回对象的存储地址,如果这个位置上没有元素,就把元素直接存储在上面,如果这个位置上已经存在元素,这个时候才去调用equal方法与新元素进行比较,相同的话就不存了,散列到其他地址上

3.2 HashCode源代码分析

  • 在Object中的HashCode源代码
public int hashCode() {
    int lockWord = shadow$_monitor_;
    final int lockWordStateMask = 0xC0000000; // Top 2 bits.
    final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
    final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
    if ((lockWord & lockWordStateMask) == lockWordStateHash) {
        return lockWord & lockWordHashMask;
    }
    //返回的是对象引用地址
    return System.identityHashCode(this);
}
  • 在String中的HashCode源代码
public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        for (int i = 0; i < count; i++) {
            h = 31 * h + charAt(i);
        }
        hash = h;
    }
    return h;
}
  • 在Integer中的HashCode源代码
public int hashCode() {
    //int值
    return value;
}

3.3 HashCode带来的疑问

  • 为何重写equals建议同时重写hashCode?
  • hashCode是什么?
  • hashCode作用?
  • hash code(hash值)是什么?
  • hash table(hash表)是什么?
  • hashCode方法对hash表有益处?
  • hashCode方法对不是hash有益处吗?

3.4 HashCode的作用

  • 减少查找次数,提高程序效率
    • 例如查找是否存在重复值
      • h(k1)≠h(k2)则k1≠k2
      • 首先查看h(k2)输出值(内存地址),查看该内存地址是否存在值;
      • 如果无,则表示该值不存在重复值;
      • 如果有,则进行值比较,相同则表示该值已经存在散列列表中,如果不相同则再进行一个一个值比较;而无需一开始就一个一个值的比较,减少了查找次数

3.5 HashMap中的HashCode

  • 在Java中也一样,hashCode方法的主要作用是为了配合基于散列的集合一起正常运行,这样的散列集合包括HashSet、HashMap以及HashTable。
  • 为什么这么说呢?考虑一种情况,当向集合中插入对象时,如何判别在集合中是否已经存在该对象了?(注意:集合中不允许重复的元素存在)
    • 也许大多数人都会想到调用equals方法来逐个进行比较,这个方法确实可行。但是如果集合中已经存在一万条数据或者更多的数据,如果采用equals方法去逐一比较,效率必然是一个问题。
    • 此时hashCode方法的作用就体现出来了,当集合要添加新的对象时,先调用这个对象的hashCode方法,得到对应的hashcode值,实际上在HashMap的具体实现中会用一个table保存已经存进去的对象的hashcode值,如果table中没有该hashcode值,它就可以直接存进去,不用再进行任何比较了;如果存在该hashcode值, 就调用它的equals方法与新元素进行比较,相同的话就不存了,不相同就散列其它的地址,所以这里存在一个冲突解决的问题,这样一来实际调用equals方法的次数就大大降低了,说通俗一点:Java中的hashCode方法就是根据一定的规则将与对象相关的信息(比如对象的存储地址,对象的字段等)映射成一个数值,这个数值称作为散列值。下面这段代码是java.util.HashMap的中put方法的具体实现:
  • put方法是用来向HashMap中添加新的元素,从put方法的具体实现可知,会先调用hashCode方法得到该元素的hashCode值,然后查看table中是否存在该hashCode值,如果存在则调用equals方法重新确定是否存在该元素,如果存在,则更新value值,否则将新的元素添加到HashMap中。从这里可以看出,hashCode方法的存在是为了减少equals方法的调用次数,从而提高程序效率。
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

3.6 可直接用hashcode判断两个对象是否相等

  • 肯定是不可以的,因为不同的对象可能会生成相同的hashcode值。虽然不能根据hashcode值判断两个对象是否相等,但是可以直接根据hashcode值判断两个对象不等,如果两个对象的hashcode值不等,则必定是两个不同的对象。如果要判断两个对象是否真正相等,必须通过equals方法。
  • 也就是说对于两个对象,如果调用equals方法得到的结果为true,则两个对象的hashcode值必定相等;
    • 如果equals方法得到的结果为false,则两个对象的hashcode值不一定不同;
    • 如果两个对象的hashcode值不等,则equals方法得到的结果必定为false;
    • 如果两个对象的hashcode值相等,则equals方法得到的结果未知。

4.Hash表是什么

4.1 Hash表定义

  • 根据关键码值(KEY-VALUE)而直接进行访问的数据结构;它通过把关键码值(KEY-VALUE)映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

4.2 Hash表简单介绍

  • 将k作为输入值,h(k)输出值作为内存地址,该内存地址用来存放value,然后可以通过k获取到value存放的地址,从而获取value信息。

5.Hash中的算法应用

5.1 基础算法

  • 比如,Java中的String.hashCode使用乘法和加法
public int hashCode() {
    int h = hash;
    if (h == 0 && count > 0) {
        for (int i = 0; i < count; i++) {
            //乘法与加法
            h = 31 * h + charAt(i);
        }
        hash = h;
    }
    return h;
}

5.2 经典算法[摘自网络]

  • MD4,MD5,SHA-1或SHA-2等其他

5.3 Hash碰撞[摘自网络]

  • hash是存在碰撞的,如果k1≠k2,h(k1)=h(k2) 则发生碰撞;

6.Hash在Java中的应用场景

6.1 equals与hashCode有两个注意点

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

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

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

6.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.关于我的博客

© 著作权归作者所有

共有 人打赏支持
潇湘剑雨
粉丝 7
博文 92
码字总数 300424
作品 0
朝阳
私信 提问
Java hashCode() 方法深入理解

Java.lang.Object 有一个hashCode()和一个equals()方法,这两个方法在软件设计中扮演着举足轻重的角色。在一些类中覆写这两个方法以完成某些重要功能。本文描述了为什么要用hashCode(), 如何...

ForingY
2016/06/12
37
1
深入理解HashMap(及hash函数的真正巧妙之处)

原文地址:http://www.iteye.com/topic/539465 Hashmap是一种非常常用的、应用广泛的数据类型,最近研究到相关的内容,就正好复习一下。网上关于hashmap的文章很多,但到底是自己学习的总结,...

令仔很忙
2016/07/18
0
0
HashMap HashTable 深入理解

在java编程语言中,最基本的结构就是两种,一个是数组,另外一个是模拟指针(引用),所有的数据结构都可以用这两个基本结构来构造的,hashmap也不例外。Hashmap实际上是一个数组和链表的结合...

jeff_han
2015/11/18
0
0
Java中Object类的equals()和hashCode()方法深入解析

1.equals() 在初学Java的时候,很多人会说在比较对象的时候,==是比较地址,equals()是比较对象的内容,谁说的? 看看equals()方法在Object类中的定义: public boolean equals(Object obj){ ...

梁金晶
2017/11/01
0
0
JAVA基础-自问自答学hashCode和equals

前言 和常常在面试中会被问到,在工作中我们也有可能遇到要重写对象方法的情况,而且方法的设计思想值得我们学习,所以我们有必要去深入学习一下这两个方法。 下面我就以面试问答的形式学习我...

liangzzz
2017/09/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

js垃圾回收机制和引起内存泄漏的操作

JS的垃圾回收机制了解吗? Js具有自动垃圾回收机制。垃圾收集器会按照固定的时间间隔周期性的执行。 JS中最常见的垃圾回收方式是标记清除。 工作原理:是当变量进入环境时,将这个变量标记为“...

Jack088
昨天
2
0
大数据教程(10.1)倒排索引建立

前面博主介绍了sql中join功能的大数据实现,本节将继续为小伙伴们分享倒排索引的建立。 一、需求 在很多项目中,我们需要对我们的文档建立索引(如:论坛帖子);我们需要记录某个词在各个文...

em_aaron
昨天
3
0
"errcode": 41001, "errmsg": "access_token missing hint: [w.ILza05728877!]"

Postman获取微信小程序码的时候报错, errcode: 41001, errmsg: access_token missing hint 查看小程序开发api指南,原来access_token是直接当作parameter的(写在url之后),scene参数一定要...

两广总督bogang
昨天
7
0
MYSQL索引

索引的作用 索引类似书籍目录,查找数据,先查找目录,定位页码 性能影响 索引能大大减少查询数据时需要扫描的数据量,提高查询速度, 避免排序和使用临时表 将随机I/O变顺序I/O 降低写速度,占用磁...

关元
昨天
7
0
撬动世界的支点——《引爆点》读书笔记2900字优秀范文

撬动世界的支点——《引爆点》读书笔记2900字优秀范文: 作者:挽弓如月。因为加入火种协会的读书活动,最近我连续阅读了两本论述流行的大作,格拉德威尔的《引爆点》和乔纳伯杰的《疯传》。...

原创小博客
昨天
21
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部