精华内容
下载资源
问答
  • hashcode的作用
    2021-02-13 00:37:50

    根据API文档,java中的hashcode事实上是跟equals是有着密切联系的,hashcode是为了提高哈希表的性能

    下面的话来自JDK:

    hashCode

    public int hashCode()返回该对象的哈希码值。支持此方法是为了提高哈希表(例如 java.util.Hashtable 提供的哈希表)的性能。

    public native int hashCode();

    说明是一个本地方法,它的实现是根据本地机器相关的。当然我们可以在自己写的类中覆盖hashcode()方法,比如String、Integer、Double。。。。等等这些类都是覆盖了hashcode()方法的。例如在String类中定义的hashcode()方法如下:

    public int hashCode() {

    int h = hash;

    if (h == 0) {

    int off = offset;

    char val[] = value;

    int len = count;

    for (int i = 0; i < len; i++) {

    h = 31*h + val[off++];

    }

    hash = h;

    }

    return h;

    }

    解释一下这个程序(String的API中写到):

    s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

    使用 int 算法,这里 s[i] 是字符串的第 i 个字符,n 是字符串的长度,^ 表示求幂。(空字符串的哈希码为 0。)

    在集合中,比如HashSet中,要求放入的对象不能重复,那么首先会调用hashcode,如果hashcode相等,则继续调用equals,也相等,则认为重复。

    如果重写equals后,如果不重写hashcode,则hashcode就是继承自Object的,返回内存编码,这时候可能出现equals相等,而hashcode不等,你的对象使用集合时,就会等不到正确的结果

    更多相关内容
  • 主要介绍了Java 中HashCode作用以及hashcode对于一个对象的重要性,对java中hashcode的作用相关知识感兴趣的朋友一起学习吧
  • HashCode作用以及使用

    千次阅读 多人点赞 2019-05-07 11:49:40
    title: HashCode作用以及使用 date: 2019-02-20 03:33:00 tags: SpringBoot category: SpringBoot description: HashCode作用以及使用 前言 博主github 博主个人博客http://blog.healerjean.com 感谢大神 1、...

    前言

    博主github

    博主个人博客http://blog.healerjean.com

    感谢大神HashCode

    感谢大神HashMap

    1、一些常见的HashCode

    1.1、Integer

    
        @Test
        public void Integer_HashCode(){
    
            Integer one  = new Integer(20);
            System.out.println(one.hashCode()); //20
    
        }
    
        /**
         * Integer 的 hashCode 就是它的value
         *
         *     public int hashCode() {
         *         return Integer.hashCode(value);
         *     }
         */
    

    1.2、String

    
    @Test
    public void String_HashCode(){
        String str1  ="123";
        System.out.println(str1.hashCode()); // 48690
    
    }
    
    /**
     * ASCII http://tool.oschina.net/commons?type=4
    
    * String 类的散列值就是依次遍历其每个字符成员,
    * 递归的将当前得到的hashCode乘以31然后加上下一个字符成员的ASCII值 (h = 31 * h + val[i];)
    *
    *   h 初始为 0
    *  '1'  49   h = 31 * 0  + 49 = 49
    *  '2'  50   h = 31 * 49 + 50 = 1569
    *  '3'  51   h = 31 * 1569 + 51 = 48690   
    *
    *     public int hashCode() {
    *         int h = hash;
    *         if (h == 0 && value.length > 0) {
    *             char val[] = value;
    *
    *             for (int i = 0; i < value.length; i++) {
    *                 h = 31 * h + val[i];
    *             }
    *             hash = h;
    *         }
    *         return h;
    *     }
    */
    
    

    2、为什么HashCode 会使用31

    关于网上的一些解释

    Why does Java’s hashCode() in String use 31 as a multiplier?

    排名第一的答案

    The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i`. Modern VMs do this sort of optimization automatically.
    
    
    选择数字31是因为它是一个奇质数,,相对来说,如果选择一个偶数会在乘法运算中产生溢出,导致数值信息丢失,因为乘二相当于移位运算。
    
    选择质数的优势并不是特别的明显,但这是一个传统。同时,数字31有一个很好的特性,即乘法运算可以被移位和减法运算取代,来获取更好的性能:31 * i == (i << 5) - i,现代的 Java 虚拟机可以自动的完成这个优化。
    
    (h = 31 * h + val[i];)
    
    

    排名第二的答案 ,后面有可视化验证

    As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.
    
    正如 Goodrich 和 Tamassia 指出的那样,如果你对超过 50,000 个英文单词(由两个不同版本的 Unix 字典合并而成)进行 hash code 运算,并使用常数 31, 33, 37, 39 和 41 作为乘子,每个常数算出的哈希值冲突数都小于7个,所以在上面几个常数中,常数 31 被 Java 实现所选用也就不足为奇了。
    
    

    2.1、原因,后面可视化也有更详细的解释

    2.1、31是一个不大不小的质数(素数)
    2.2、31可以被 JVM 优化,31 * i = (i << 5) - i。现代的 Java 虚拟机可以自动的完成这个优化
    
    假设 n=3
    i=0 -> h = 31 * 0 + val[0]
    i=1 -> h = 31 * (31 * 0 + val[0]) + val[1]
    i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2]
           h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2]
           h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2]
    
    
    这里先分析质数2。-------仅计算公式中次数最高的那一项-----------
    首先,假设 n = 6,然后把质数2和 n 带入上面的计算公式。结果是2^5 = 32,是不是很小。所以这里可以断定,当字符串长度不是很长时,用质数2做为乘子算出的哈希值,数值不会很大。也就是说,哈希值会分布在一个较小的数值区间内,分布性不佳,最终可能会导致冲突率上升,质数2做为乘子会导致哈希值分布在一个较小区间内
    
    那么如果用一个较大的大质数101会产生什么样的结果呢?根据上面的分析,我想大家应该可以猜出结果了。就是不用再担心哈希值会分布在一个小的区间内了,因为101^5 = 10,510,100,501。但是要注意的是,这个计算结果太大了。如果用 int 类型表示哈希值,结果会溢出,最终导致数值信息丢失。如果不在意质数101容易导致数据信息丢失问题,或许其是一个更好的选择。
    
    尽管数值信息丢失并不一定会导致冲突率上升,但是我们暂且先认为质数101(或者更大的质数)也不是很好的选择。最后,我们再来看看质数31的计算结果: 31^5 = 28629151,结果值相对于32和10,510,100,501来说。是不是很nice,不大不小。
    
    
    

    2.2、可视化得出结论

    计算哈希算法冲突率并不难,比如可以一次性将所有单词的 hash code 算出,并放入 Set 中去除重复值。之后拿单词数减去 set.size() 即可得出冲突数,有了冲突数,冲突率就可以算出来了。当然,如果使用 JDK8 提供的流式计算 API,则可更方便算出,代码片段如下:

    public static Integer hashCode(String str, Integer multiplier) {
        int hash = 0;
        for (int i = 0; i < str.length(); i++) {
            hash = multiplier * hash + str.charAt(i);
        }
    
        return hash;
    }
        
    /**
     * 计算 hash code 冲突率,顺便分析一下 hash code 最大值和最小值,并输出
     * @param multiplier
     * @param hashs
     */
    public static void calculateConflictRate(Integer multiplier, List<Integer> hashs) {
        Comparator<Integer> cp = (x, y) -> x > y ? 1 : (x < y ? -1 : 0);
        int maxHash = hashs.stream().max(cp).get();
        int minHash = hashs.stream().min(cp).get();
    
        // 计算冲突数及冲突率
        int uniqueHashNum = (int) hashs.stream().distinct().count();
        int conflictNum = hashs.size() - uniqueHashNum;
        double conflictRate = (conflictNum * 1.0) / hashs.size();
    
        System.out.println(String.format("multiplier=%4d, minHash=%11d, maxHash=%10d, conflictNum=%6d, conflictRate=%.4f%%",
                    multiplier, minHash, maxHash, conflictNum, conflictRate * 100));
    }
    

    1557195124268

    从上图可以看出,

    简单总结

    1、 质数2、冲突率达到了 55%以上,而且hash值分布不是很广泛,,仅仅分布在了整个哈希空间的正半轴部分,即 0 ~ 2^31-1。而负半轴 -2^31 ~ -1,则无分布。这也证明了我们上面断言,即质数2作为乘子时,对于短字符串,生成的哈希值分布性不佳。

    2、奇质数,101、109 表现也不错,冲突率很低,说明了哈希值溢出不一定导致冲突率比较高,但是溢出的话,我们不认为是我们的优选乘子 ,如果不在意质数101容易导致数据信息丢失问题,或许其是一个更好的选择。

    3、偶数 32、36 这两个并不好,32的冲突率已经超过了50%,尽管36表现好一些,但是和31,37相比,冲突率还是比较高的,但是**偶数也不一定作为乘子冲突率就比较高 **

    4、奇质数 31、37 、41 表现都不出,冲突数都小于7个,使用较小的质数做为乘子时,冲突率会很高。 选择比较大的质数作为乘子时,冲突率会降低,但是可能会再次哈希值溢出

    2.3、哈希值分布可视化

    上面的2.2介绍了不同数字作为乘子的冲突率情况,下面分析一下不同数字作为乘子时,hash值得分布情况

    https://segmentfault.com/a/1190000010799123

    3、HashCode使用

    3.1、HashCode定义(确定位置,但不能确定地址)

    从Object角度看,JVM每new一个Object,它都会将这个Object丢到一个Hash表中去,这样的话,下次做Object的比较或者取这个对象的时候(读取过程),它会根据对象的HashCode再从Hash表中取这个对象。这样做的目的是提高取对象的效率。若HashCode相同再去调用equal。

    (1)HashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,HashCode是用来在散列存储结构中确定对象的存储地址的;

    (2)如果两个对象相同, equals方法一定返回true,并且这两个对象的HashCode一定相同;除非重写了方法

    (3)如果对象的equals方法被重写,那么对象的HashCode也尽量重写,并且产生HashCode使用的对象,一定要和equals方法中使用的一致,否则就会违反上面提到的第2点;

    (4)两个对象的HashCode相同,并不一定表示两个对象就相同,也就是equals方法不一定返回true,只能够说明这两个对象在散列存储结构中,如Hashtable,他们存放在同一个篮子里。

    3.2、HashCode作用

    Java中的集合(Collection)有两类,一类是List,再有一类是Set。前者集合内的元素是有序的,元素可以重复;后者元素无序,但元素不可重复。 equals方法可用于保证元素不重复,但是,如果每增加一个元素就检查一次,如果集合中现在已经有1000个元素,那么第1001个元素加入集合时,就要调用1000次equals方法。这显然会大大降低效率。

    于是,Java采用了哈希表的原理。

    哈希算法也称为散列算法,是将数据依特定算法直接指定到一个地址上。这样一来,当集合要添加新的元素时,先调用这个元素的HashCode方法,就一下子能定位到它应该放置的物理位置上。

    (1)如果这个位置上没有元素,它就可以直接存储在这个位置上,不用再进行任何比较了;

    (2)如果这个位置上已经有元素了,就调用它的equals方法与新元素进行比较,相同的话就不存了;

    (3)不相同的话,也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同HashCode的对象放到这个单链表上去,串在一起(很少出现)。这样一来实际调用equals方法的次数就大大降低了,几乎只需要一两次。 (下面1、的实例就为这里的测试实例)

    3.3、HashCode是用于查找使用的,而equals是用于比较两个对象的是否相等的。

    (1)例如内存中有这样的位置 :0 1 2 3 4 5 6 7

    而我有个类,这个类有个字段叫ID,我要把这个类存放在以上8个位置之一,如果不用HashCode而任意存放,那么当查找时就需要到这八个位置里挨个去找,或者用二分法一类的算法。

    但如果用HashCode那就会使效率提高很多。 定义我们的HashCode为ID%8,比如我们的ID为9,9除8的余数为1,那么我们就把该类存在1这个位置,如果ID是13,求得的余数是5,那么我们就把该类放在5这个位置。依此类推。

    (2)但是如果两个类有相同的HashCode,例如9除以8和17除以8的余数都是1,也就是说,我们先通过 HashCode来判断两个类是否存放某个桶里,但这个桶里可能有很多类,比如hashtable,那么我们就需要再通过 equals 在这个桶里找到我们要的类。

    3.4、Set测试

    3.4.1、实例重写HashCode方法
    
    public class HashTest {    
        private int i;    
        
        public int getI() {    
            return i;    
        }    
        
        public void setI(int i) {    
            this.i = i;    
    }   
     
        @Override
        public int hashCode() {    
            return i % 10;    
    }
        
    /**
    *  对象的内存地址与hashcode有关系,但并不是hashcode值相等,就是代表内存地址相同,这种想法是幼稚的
    *  比如hashtable中hashcode值相等,
    *  	但是存了很多的对象,这表明对象的== 肯定不相等,Ojbect逆向推理,equals不相等,==肯定不相等 
    *  
    */
    
        public final static void main(String[] args) {    
            HashTest a = new HashTest();    
            HashTest b = new HashTest();  
    
            System.out.println(a.hashCode() == b.hashCode());  //true 人为制造hashcode值相同  
            System.out.println(a==b);    //false //== 比较对象的相等比较对象引用地址是否相等。还要要比较对象内容是否相等
            System.out.println(a.equals(b));    //false 不同的对象 object中 == 和euqals是一样的
    
            a.setI(1);    
            b.setI(1);    
            Set<HashTest> set = new HashSet<HashTest>();    
            set.add(a);    
            set.add(b);    
            //没有 equels 重写的情况
            System.out.println(a.hashCode() == b.hashCode());  //true hashcode相同   
    
            System.out.println(a.equals(b));    //false 不同的对象 ,创建出来的是地址就不同了
    
            //2 这个时候会发想存入了两个值  set中存放是根据hashcode值存放,如果hashcode值相同,
            //再比较equals值,如果equals值也相同,则产生一个单链表放进去
            System.out.println(set.size());    
    
        }    
    
    

    1557200814335

    3.4.2、重写equels方法
    
    public class HashTest {    
        private int i;    
        
        public int getI() {    
            return i;    
        }    
        
        public void setI(int i) {    
            this.i = i;    
        }    
        
        @Override
        public boolean equals(Object object) {    
            if (object == null) {    
                return false;    
            }    
            if (object == this) {    
                return true;    
            }    
            if (!(object instanceof HashTest)) {    
                return false;    
            }    
            HashTest other = (HashTest) object;    
            if (other.getI() == this.getI()) {    
                return true;    
            }    
            return false;    
        }  
        
        @Override
        public int hashCode() {    
            return i % 10;    
        }    
         public final static void main(String[] args) {    
            HashTest a = new HashTest();    
            HashTest b = new HashTest();  
            
            System.out.println(a.hashCode() == b.hashCode());         
            System.out.println(a==b);           
            System.out.println(a.equals(b));   
    
            a.setI(1);    
            b.setI(1);    
            Set<HashTest> set = new HashSet<HashTest>();    
            set.add(a);    
            set.add(b);    
           
            System.out.println(a.hashCode() == b.hashCode());          
            System.out.println(a.equals(b));   
            
            System.out.println(set.size());    
            
        }    
    }    
    }
    
    

    1557200890482

    3.5、map测试
    package com.hlj.util.Z009HashCode;
    
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    /**
     * @Description
     * @Author HealerJean
     * @Date 2018/4/12
     */
    public class D02_Object {
    
        public static void main(String[] args) {
            Map <Object,Object> map = new HashMap<>();
    
            Object o = new Object();
            map.put(o,"Stromg");
    
    
            Object o2 = new Object();
            map.put(o2,3);
    
    
            System.out.println(map.get(o)); //Stromg
            System.out.println(map.get(o2)); //3
    
            o = 456;
            System.out.println(map.get(o)); //null  因为提供的key的hashcode的地址不是我们存储的地址,所以不能找到,但是之前存储的还在
    
    
            Person person = new Person();
            person.setAge(1);
            map.put(person,3);
            System.out.println(map.get(person)); //3
    
            person.setName("HealerJean");
            System.out.println(map.get(person)); //3
            System.out.println("map的大小"+map.size()); //map的大小3
    
            person = null ; // person设置为null, map中还是具有该person对象
            System.out.println(map.get(person));  //null
            System.out.println("map的大小"+map.size()); //map的大小3
    
            System.out.println("打印map的结果集");
            Object[] list = map.keySet().toArray();
            for (Object object :list){
                System.out.println("key="+object.toString()+"||||| value="+map.get(object).toString());
            }
    
    
        }
    
    
    }
    
    class Person {
        int age;
        String name;
    
        public int getAge() {
            return age;
        }
    
        public void setAge(int age) {
            this.age = age;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        @Override
        public String toString() {
            return "Person{" +
                    "age=" + age +
                    ", name='" + name + '\'' +
                    '}';
        }
    }
    
    
    打印结果
    
    /**
    * Stromg
    * 3
    * null
    * 3
    * 3
    * map的大小3
    * null
    * map的大小3
    * 打印map的结果集
    * key=java.lang.Object@9807454||||| value=3
    * key=Person{age=1, name='HealerJean'}||||| value=3
    * key=java.lang.Object@4fca772d||||| value=Stromg
    */
    
    
    

    4、HashMap

    上面明白了hashcode的生成原理了,现在我们来看看 hash算法

    4.1、 HashMap 的 hash 算法的实现原理(为什么右移 16 位,为什么要使用 ^ 位异或)

    hash值的作用,知道hash是为了获取数组下标的,很明显就知道该hash值是为了均匀散列表的下标,仔细看看,就知道下面使用了 hashcode 右移16位再和自己异或得到的hash值

    static final int hash(Object key) {
           int h;
           return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    

    观察下HashMap查找到数组的

    // 重点关注
    first = tab[(n - 1) & hash]) != null
               
    
    final Node<K,V> getNode(int hash, Object key) { // 该处的hash实际上是调用的上面的hash方法
           Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
           if ((tab = table) != null && (n = tab.length) > 0 &&
               // 我们需要关注下面这一行
               (first = tab[(n - 1) & hash]) != null) {
               if (first.hash == hash && // always check first node
                   ((k = first.key) == key || (key != null && key.equals(k))))
                   return first;
               if ((e = first.next) != null) {
                   if (first instanceof TreeNode)
                       return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                   do {
                       if (e.hash == hash &&
                           ((k = e.key) == key || (key != null && key.equals(k))))
                           return e;
                   } while ((e = e.next) != null);
               }
           }
           return null;
       }
    

    举例说明

    对象 A 的 hashCode 为 0100 0010 0011 1000 1000 0011 1100 0000

    对象 B 的 hashCode 为 0011 1011 1001 1100 0101 0000 1010 0000

    如果不经过hash运算,如果数组长度是16(默认就是16),也就是 15 与运算这两个数,

    15 的二进制数 0000 0000 0000 0000 0000 0000 0000 1111 ,发现结果都是0。这样的话数组小标就都是0了,这样的结果应该不是我们想看到的,因为这种情况其实出现的次数挺多的。

    解决

    如果我们将 hashCode 值右移 16 位,也就是取 int 类型的一半,刚好将该二进制数对半切开。并且使用位异或运算(如果两个数对应的位置相反,则结果为1,反之为0),这样的话,就能避免我们上面的情况的发生,即(h = key.hashCode()) ^ (h >>> 16)。 相当于让自己的前半段16位和后半段16位做一个异或的运算

    总的来说,使用位移 16 位和 异或 就是防止这种极端情况。但是,该方法在一些极端情况下还是有问题,比如:10000000000000000000000000 和 1000000000100000000000000 这两个数,如果数组长度是16,那么即使右移16位,在异或,hash 值还是会重复。但是为了性能,对这种极端情况,JDK 的作者选择了性能。毕竟这是少数情况,为了这种情况去增加 hash 时间,性价比不高。

    当数组吃长度n为 16 的时候数组下标: 1111 & 101010100101001001000(随便写的) 1000 = 8

    4.2、HashMap 为什么使用 & 与运算代替模运算

    其中 n 是数组的长度。其实该算法的结果和模运算的结果是相同的。但是,对于现代的处理器来说,**除法和求余数(模运算)**是最慢的动作,

    通过上面的4.1末尾,可以看到,可以看到,当 n 为 2 的幂次方的时候,减一之后就会得到 一堆1111…… 的数字,这个数字正好可以掩码 (都是一堆 1111……),并且得到的结果取决于 hash 值。因为 hash 位值是1,那么最终的结果也是1 ,hash位 值是0,最终的结果也是0。

    tab[   (n - 1) & hash   ];
    

    4.3、HashMap 的容量为什么建议是 2的幂次方?

    接4.2、hash 算法的目的是为了让hash值均匀的分布在桶中(数组),那么,如何做到呢?试想一下,如果不使用 2 的幂次方作为数组的长度会怎么样?

    假设我们的数组长度是10,还是上面的公式:

    1001 & 101010100101001001000 结果:1000 = 8

    1001 & 101000101101001001001 结果:1001 = 9

    1001 & 101010101101101001010 结果: 1000 = 8

    1001 & 101100100111001101100 结果: 1000 = 8

    结论

    所以说,我们一定要保证 & 中的二进制位全为 1,才能最大限度的利用 hash 值,并更好的散列,只有全是1 ,才能有更多的散列结果。如果是 1001,有的散列结果是永远都不会出现的,比如 1111,1010,1011,…,只要 & 之前的数有 0, 对应的 1 肯定就不会出现(因为只有都是1才会为1)。大大限制了散列的范围。

    4.4、我们自定义 HashMap 容量最好是多少

    那我们如何自定义呢?自从有了阿里的规约插件,每次楼主都要初始化容量,如果我们预计我们的散列表中有2个数据,那么我就初始化容量为2嘛

    绝对不行,如果大家看过源码就会发现,如果Map中已有数据的容量达到了初始容量的 75%,那么散列表就会扩容,而扩容将会重新将所有的数据重新散列,性能损失严重,所以,我们可以必须要大于我们预计数据量的 1.34 倍,如果是2个数据的话,就需要初始化 2.68 个容量。当然这是开玩笑的,2.68 不可以,3 可不可以呢?肯定也是不可以的,我前面说了,如果不是2的幂次方,散列结果将会大大下降。导致出现大量链表。那么我可以将初始化容量设置为4。 当然了,如果你预计大概会插入 12 条数据的话,那么初始容量为16简直是完美,一点不浪费,而且也不会扩容。

    项目经验总计:

    1、比如链表数很多,肯定是数组初始化长度不对,这样的话会造成拥挤

    2、如果某个map很大,注意,肯定是事先没有定义好初始化长度

    假设,某个Map存储了10000个数据,那么他会扩容到 20000,实际上,根本不用 20000,只需要 10000* 1.34= 13400 个,然后向上找到一个2 的幂次方,也就是 16384 初始容量足够。



    感兴趣的,欢迎添加博主微信

    哈,博主很乐意和各路好友交流,如果满意,请打赏博主任意金额,感兴趣的在微信转账的时候,备注您的微信或者其他联系方式。添加博主微信哦。

    请下方留言吧。可与博主自由讨论哦

    微信微信公众号支付宝
    微信微信公众号支付宝
    展开全文
  • Hashcode作用

    2021-12-18 16:04:06
    5. Hashcode作用 科普 Hash是散列的意思,就是把任意长度的输入,通过散列算法变换成固定长度的输出,该输出就是散列值。关于散列值,有以下几个关键结论: 如果散列表中存在和散列原始输入K相等的记录,那么K必定...

    以下都是Java的基础面试题,相信大家都会有种及眼熟又陌生的感觉、看过可能在短暂的面试后又马上忘记了。JavaPub在这里整理这些容易忘记的重点知识及解答建议收藏,经常温习查阅


    5. Hashcode作用

    科普
    在这里插入图片描述
    Hash是散列的意思,就是把任意长度的输入,通过散列算法变换成固定长度的输出,该输出就是散列值。关于散列值,有以下几个关键结论:

    • 如果散列表中存在和散列原始输入K相等的记录,那么K必定在f(K)的存储位置上
    • 不同关键字经过散列算法变换后可能得到同一个散列地址,这种现象称为碰撞
    • 如果两个Hash值不同(前提是同一Hash算法),那么这两个Hash值对应的原始输入必定不同

    那么多答案,但是只有一个最关键的点:

    提升查询效率

    相关问题 https://javapub.blog.csdn.net/article/details/122013318


    10道不得不会的Java基础面试题

    https://javapub.blog.csdn.net/article/details/122011870

    手机随时看:微信搜【JavaPub】 JavaPub

    查看更多面试题及答案
    wx

    展开全文
  • Java集合中有两类,一类是List,一类是Set他们之间的区别就在于List集合中的元素师有序的,且可以重复,而Set集合中元素是无序不可重复的。...hashCode提供了解决方案。怎么实现?我们先看hashCode的源码(Object)。
  • Java中hashCode作用

    2020-12-22 21:05:22
    以下是关于HashCode的官方文档定义:  hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。  hashCode 的常规协定是:  在Java应用程序执行期间...
  • HashCode 作用,如何重载hashCode方法前言Object 类提供了一个Native方法public native int hashCode();下面简单介绍下Hash以及HashCode方法的作用HashHash 是散列的意思,就是把任意长度的输入,通过散列算法换成...

    HashCode 作用,如何重载hashCode方法

    前言

    Object 类提供了一个Native方法

    public native int hashCode();

    下面简单介绍下Hash以及HashCode方法的作用

    Hash

    Hash 是散列的意思,就是把任意长度的输入,通过散列算法换成固定长度的输出,概述出就是散列值,关于散列值,有一下几个关键结论:

    如果散列表存在和散列原始输入K相等的记录,那么K必定在f(K)的存储位置上

    不同关键字经过散列算法变换后可能得到同一个散列地址,这种现象称为碰撞

    如果两个Hash值不同(前提是同一个Hash算法),那么两个Hash值对应的原始输入必定不同

    HashCode

    HashCode 的存在主要是为了查找的快捷性,HashCode是用来在散列存储结构种确定对象的存储地址的

    如果两个对象equals 相等,那么这两个对象的HashCode一定也相同

    如果对象的equals方法被重写,那么对象的HashCode方法也尽量重写

    如果两个对象的HashCode相同,不代表两个对象就相同,只能说明两个对象在散列存储结构中,存放于同一个位置

    HashCode作用

    举个栗子

    假设内存中有0 1 2 3 4 5 6 7 8这八个位置,如果我有个字段叫做ID,那么我要把这个字段存在以上8个位置之一,如果不用HashCode而任意存放,那么当查找时就需要到8个位置中去挨个查找

    如果使用HashCode效率则会快很多,把ID的HashCode%8,然后把ID存放在取得余数的那个位置,然后每次查找该类的时候都可以通过ID的HashCode&8 求余数直接找到存放的位置

    如果ID的HashCode%8算出来的位置上有数据怎们办?这个就取决于算法的实现了,比如ThreadLocal中做法就是从算出来的位置向后查找第一个为空的位置,放置数据;HashMap的做法就是通过链式结构连接起来。 反正不论怎样,只要保证放的时候和取的时候的算法一致就行。

    如果ID的HashCode%8相等怎么办?这就对应了上面所说的链式结构中的场景,发生了碰撞,这个时候就需要定义equals了。先通过HashCode%8来判断对象在哪一个位置,再通过equals来在这个位置上寻找需要的对象。对比两个对象的时候也不多,先通过HashCode比较,假如HashCode相等再判断equals。如果两个对象的HashCode 都不一样,那么这两个对象必定不同。

    举个实际的栗子Set。我们知道Set里面的元素是不可以重复的,那么如何做到?Set是根据equals方法来判断两个元素是否相等。比如,Set里面已经有1000个元素了,那个第1001个元素进来的时候,最多可能调用equals方法1000次,那么假如坏一点的情况,equals方法里面写的有点复杂,对比的东西又有点多,考虑一下效率呀,是不是特别慢。使用HashSet就不一样的,底层是通过HashMap实现的,先通过HashCode 取一个模,这样一下子就固定的某一个位置,如果这个位置上没有元素,那么就可以肯定HashSet中必定没有和新添加的元素equals的元素,就可以直接存 放了,都不需要比较;如果这个位置上有元素了,逐一比较,比较的时候先比较HashCode,HashCode都不同接下去都不用比了,肯定不一 样,HashCode相等,再equals比较,没有相同的元素就存,有相同的元素就不存。如果原来的Set里面有相同的元素,只要HashCode的生 成方式定义得好(不重复),不管Set里面原来有多少元素,只需要执行一次的equals就可以了。这样一来,实际调用equals方法的次数大大降低, 提高了效率。

    为什么重写Object的equals(Object obj)方法尽量要重写Object的hashCode()方法

    重写Object的equals(Object obj)方法的时候,应该尽量重写hashCode()方法,这是有原因的

    public class HashCodeClass{

    private String str0;

    private double dou0;

    private int int0;

    public boolean equals(Object obj){

    if (obj instanceof HashCodeClass){

    HashCodeClass hcc = (HashCodeClass)obj;

    if (hcc.str0.equals(this.str0) &&

    hcc.dou0 == this.dou0 &&

    hcc.int0 == this.int0){

    return true;

    }

    return false;

    }

    return false;

    }

    }

    public class TestMain{

    public static void main(String[] args){

    System.out.println(new HashCodeClass().hashCode());

    System.out.println(new HashCodeClass().hashCode());

    System.out.println(new HashCodeClass().hashCode());

    System.out.println(new HashCodeClass().hashCode());

    System.out.println(new HashCodeClass().hashCode());

    System.out.println(new HashCodeClass().hashCode());

    }

    }

    控制台输出如下

    1901116749

    1807500377

    355165777

    1414159026

    1569228633

    778966024

    现在我的HashCodeClass都没有赋初值,那么这6个HashCodeClass应该是全部equals的。如果以HashSet为 例,HashSet内部的HashMap的table本身的大小是16,那么6个HashCode对16取模分别为13、9、1、2、9、8。第一个放入 table[13]的位置、第二个放入table[9]的位置、第三个放入table[1]的位置。。。但是明明是全部equals的6个 HashCodeClass,怎么能这么做呢?HashSet本身要求的就是equals的对象不重复,现在6个equals的对象在集合中却有5份(因 为有两个计算出来的模都是9)。

    那么我们该怎么做呢?重写hashCode方法,根据str0、dou0、int0搞一个算法生成一个尽量唯一的hashCode,这样就保证了 str0、dou0、int0都相等的两个HashCodeClass它们的HashCode是相等的,这就是重写equals方法必须尽量要重写 hashCode方法的原因。看下JDK中的一些类,都有这么做:

    Integer

    public int hashCode() {

    return value;

    }

    public boolean equals(Object obj) {

    if (obj instanceof Integer) {

    return value == ((Integer)obj).intValue();

    }

    return false;

    }

    String

    public int hashCode() {

    int h = hash;

    if (h == 0) {

    int off = offset;

    char val[] = value;

    int len = count;

    for (int i = 0; i < len; i++) {

    h = 31*h + val[off++];

    }

    hash = h;

    }

    return h;

    }

    public boolean equals(Object anObject) {

    if (this == anObject) {

    return true;

    }

    if (anObject instanceof String) {

    String anotherString = (String)anObject;

    int n = count;

    if (n == anotherString.count) {

    char v1[] = value;

    char v2[] = anotherString.value;

    int i = offset;

    int j = anotherString.offset;

    while (n-- != 0) {

    if (v1[i++] != v2[j++])

    return false;

    }

    return true;

    }

    }

    return false;

    }

    HashMap的Entry

    public final int hashCode() {

    return (key==null ? 0 : key.hashCode()) ^

    (value==null ? 0 : value.hashCode());

    }

    public final boolean equals(Object o) {

    if (!(o instanceof Map.Entry))

    return false;

    Map.Entry e = (Map.Entry)o;

    Object k1 = getKey();

    Object k2 = e.getKey();

    if (k1 == k2 || (k1 != null && k1.equals(k2))) {

    Object v1 = getValue();

    Object v2 = e.getValue();

    if (v1 == v2 || (v1 != null && v1.equals(v2)))

    return true;

    }

    return false;

    }

    展开全文
  • hashcode作用

    千次阅读 2021-04-19 21:30:20
    1、hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的; 2、如果两个对象相同,就是适用于equals(java.lang.Object) 方法,那么这两个对象的...
  • 详解Java中hashCode作用以下是关于HashCode的官方文档定义:hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。hashCode 的常规协定是:在 Java ...
  • hashcode作用 hashcode用于返回对象的散列值,用于在散列函数中确定放置的桶的位置 hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的 如果两...
  • hashCode作用

    2020-10-15 16:00:36
    (1)HashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,HashCode经常用于确定对象的存储地址; (2)如果两个对象相同, equals方法一定返回true,并且这两个对象的HashCode一定相同; (3)两个...
  • Java中hashCode方法的作用

    千次阅读 2021-11-12 21:51:30
    hashcode方法返回该对象的哈希码值,其值一般是该对象在内存上的地址。 hashCode的常规协定是: 在Java应用程序执行期间,在同一对象上多次调用hashCode方法时,必须一致地返回相同的整数,前提是对象的equals...
  • HashMap中类的hashCode重写和不重写的区别 hashmap是通过key的hashCode来查找,所以即使我们重写了equals方法,但是如果没有重写hashCode方法,得到的两个对象仍然不相等。如果要使两个实例的对象为一致时,就必须...
  • HashCode作用

    2016-09-05 09:48:00
    作用: 1、HashCode的存在主要是为了查找的快捷性,HashCode是用来在散列存储结构中确定镀锡的存储地址的 2、如果两个对象的equals相等,那么HashCode一定相等,反之不行 3、如果equals被重写,HashCode尽量也...
  • hashcode这个方法是用来鉴定2个对象是否相等的。那你会说,不是还有equals这个方法吗?不错,这2个方法都是用来判断2个对象是否相等的。但是他们是有区别的。一般来讲,equals这个方法是给用户调用的,如果你想判断2...
  • Java & hashCode作用

    2018-01-17 23:06:00
    首先,想要明白hashCode作用,你必须要先知道Java中的集合。 总的来说,Java中的集合(Collection)有两类,一类是List,再有一类是Set。你知道它们的区别吗?前者集合内的元素是有序的,元素可以重复;后者元素...
  • Java中Hashcode作用

    2020-10-19 23:59:42
    Hashcode作用 java的集合有两类,一类是List,还有一类是Set。前者有序可重复,后者无序不重复。当我们在set中 插入的时候怎么判断是否已经存在该元素呢,可以通过equals方法。但是如果元素太多,用这样的方法 就...
  • hashcode作用

    2014-06-21 22:41:51
    HashCode作用 博客分类:   j2se基础 算法 首先,想要明白hashCode作用,你必须要先知道Java中的集合。 总的来说,Java中的集合(Collection)有两类,一类 是List,再有一类是Set。你知道它们的...
  • (1)hashcode()方法的作用 hashcode()方法主要配合基于散列的集合一起使用,比如HashSet、HashMap、HashTable。 当集合需要添加新的对象时,先调用这个对象的hashcode()方法,得到对应的hashcode值,实际上...
  • Java——hashcode作用

    2021-05-08 10:46:33
    hashCode用于返回对象的散列值,用于在散列函数中确定放置的桶的位置。 hashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,hashCode是用来在散列存储结构中确定对象的存储地址的; 如果两个对象相同...
  • java hashcode作用

    2016-12-04 15:49:07
    以下是关于HashCode的官方文档定义:[plain] view plain copyhashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。 hashCode 的常规协定是: 在 Java ...
  • (1)HashCode的存在主要是用于查找的快捷性,如Hashtable,HashMap等,HashCode经常用于确定对象的存储地址; (2)如果两个对象相同, equals方法一定返回true,并且这两个对象的HashCode一定相同; (3)两个...
  • Hashcode作用

    2016-09-09 11:26:58
    在Java的Object类中有一个方法:public native int ...一、hashcode方法的作用hashCode方法的主要作用是为了配合基于散列的集合一起正常运行,这样的散列集合包括HashSet、HashMap以及HashTable。为什么这么说呢?
  • java 中hashcode作用

    2017-02-08 10:22:12
    以下是关于HashCode的官方文档定义: [plain] view plain copy hashcode方法返回该对象的哈希码值。支持该方法是为哈希表提供一些优点,例如,java.util.Hashtable 提供的哈希表。 hashCode 的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 95,418
精华内容 38,167
关键字:

hashcode的作用