• <i id='NkWBU'><tr id='NkWBU'><dt id='NkWBU'><q id='NkWBU'><span id='NkWBU'><b id='NkWBU'><form id='NkWBU'><ins id='NkWBU'></ins><ul id='NkWBU'></ul><sub id='NkWBU'></sub></form><legend id='NkWBU'></legend><bdo id='NkWBU'><pre id='NkWBU'><center id='NkWBU'></center></pre></bdo></b><th id='NkWBU'></th></span></q></dt></tr></i><div id='NkWBU'><tfoot id='NkWBU'></tfoot><dl id='NkWBU'><fieldset id='NkWBU'></fieldset></dl></div>
  • <small id='NkWBU'></small><noframes id='NkWBU'>

        <tfoot id='NkWBU'></tfoot>

          <bdo id='NkWBU'></bdo><ul id='NkWBU'></ul>
        <legend id='NkWBU'><style id='NkWBU'><dir id='NkWBU'><q id='NkWBU'></q></dir></style></legend>
      1. Java面试题之HashMap 的 hash 方法原理是什么

        在了解HashMap的原理之前, 我们先看看hash散列表是怎么工作的, 他的原理是什么。

          <small id='zuC66'></small><noframes id='zuC66'>

              <legend id='zuC66'><style id='zuC66'><dir id='zuC66'><q id='zuC66'></q></dir></style></legend>
                <tbody id='zuC66'></tbody>

            • <tfoot id='zuC66'></tfoot>
                <bdo id='zuC66'></bdo><ul id='zuC66'></ul>
                <i id='zuC66'><tr id='zuC66'><dt id='zuC66'><q id='zuC66'><span id='zuC66'><b id='zuC66'><form id='zuC66'><ins id='zuC66'></ins><ul id='zuC66'></ul><sub id='zuC66'></sub></form><legend id='zuC66'></legend><bdo id='zuC66'><pre id='zuC66'><center id='zuC66'></center></pre></bdo></b><th id='zuC66'></th></span></q></dt></tr></i><div id='zuC66'><tfoot id='zuC66'></tfoot><dl id='zuC66'><fieldset id='zuC66'></fieldset></dl></div>

                  HashMap 的 hash 方法原理是什么

                  在了解HashMap的原理之前, 我们先看看hash散列表是怎么工作的, 他的原理是什么。

                  散列表的原理是将关键字通过散列函数映射到固定的位置上, 并对原始值进行处理, 最终得到的值就是我们所说的哈希值, 即在HashMap中所表现出来的值。在JDK1.7之前,HashMap的内部实现方式是数组 + 链表,数组的下标就是哈希值,而链表则是解决哈希冲突的方案。而在JDK1.8之后,由于链表会引起频繁的GC,会对性能有影响,而添加了红黑树的设计,对冲突的解决更加高效。

                  比如在HashMap中,我们put一个新的键值对时,便会对新的key生成一个哈希值(hashCode),这个hashCode将会指导他在数组中的大致位置, 但有可能会存在相同的hashCode(即hash冲突),因此会通过拉链法(或者是红黑树)来使链表在当前位置上依次挂起来,这样既能保证查询时的O(1)速度,又能避免产生很多碰撞。

                  具体来说,当我们使用HashMap的put方法时,HashMap首先会对key进行hash计算,得到一个hash值。然后,HashMap会将这个hash值用来决定key-value存放在数组中的位置。

                  hash方法的实现原理

                  接下来是讲解hash方法的实现原理,hash方法是用来计算hashCode的,接下来是hash方法的代码实现:

                  static final int hash(Object key) {
                      int h;
                      // key.hashCode()计算出key的哈希值h
                      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
                  }
                  

                  在上面的实现中, 首先对键值调用key.hashCode()方法,确定键值的哈希值h。hashCode()的具体实现可以看做是从对象的物理地址、时间等因素来生成唯一标识。

                  在key为null的情况下,哈希值设为0。
                  为什么要进行以下位运算呢,在进行哈希值计算的时候借助到了以下位运算:

                  h ^ (h >>> 16)

                  这里是采用了hash分流算法, 具体步骤如下:

                  • 按照hashcode和右移16的结果做异或,生成新的哈希值
                  • 将新的哈希值除以容量size的余数,得到下标index
                  • 如果当前下标没有hash冲突,则直接将其放入slots[index]中;
                  • 如果当前下标有hash冲突,则将当前的键值对添加到当前下标对应的链表的最后;

                  然而hash散列并不是完美的算法, 在极端情况下可能出现hash冲突,即不同的两个key所对应的hash值是相同的,这就需要采取一些特殊处理的策略,例如拉链法或者是一些替代性的算法,这些算法都有其优劣性。对于比较简单的key值集合来说,HashMap可以将一个键值的HashCode直接映射为一个下标,这种情况下性能最好。

                  下面再举个栗子: 我们以五个关键字生成的hashCode为例,说一下在HashMap中如何定位分组的过程。

                  String s1= "name";
                  String s2 = "gender";
                  String s3 = "age";
                  String s4 = "addr";
                  String s5 = "phone";
                  System.out.println(s1.hashCode());
                  System.out.println(s2.hashCode());
                  System.out.println(s3.hashCode());
                  System.out.println(s4.hashCode());
                  System.out.println(s5.hashCode());
                  
                  //分别输出如下, 
                  //名字(hashCode): 3373707
                  //性别(hashCode): 1967188755
                  //年龄(hashCode):95458899
                  //地址(hashCode): 3009914
                  //电话(hashCode): 3081039
                  
                  

                  所以, 当存储出现哈希冲突,我们可以通过维护链表的方式解决。例如, 有两个键值对[key1, value1]和[key2, value2],他们都对应了相同的哈希值h。那么,HashMap就将其存储在[h]位置的链表的尾部。这样,查询哈希表中任一键值对时,HashMap首先对该键值计算哈希值,然后找到[h]位置并遍历链表,在链表中找到一个哈希值和要查询的键值的哈希值相同的键值对。 haMap的hash方法原理和hash算法通过详细的讲解,我们已经能够对HashMap有了较全面的认识。

                  本站部分内容来源互联网,如果有图片或者内容侵犯了您的权益,请联系我们,我们会在确认后第一时间进行删除!

                  相关文档推荐

                  Lambda表达式是Java 8中引入的新特性之一,它是一个匿名函数,可以捕获参数并表现为一个代码块,而不像方法一样需要一个固定的名称。它主要用于传递行为或代码块以及事件处理等操作。
                  下面为您详细讲解基于Java的回调函数。
                  在Java中,equals()是用来比较两个对象是否相等的函数。equals()方法是Object类中的方法,因此所有Java类都包含equals()方法。在默认情况下,equals()方法比较对象的引用地址是否相同,即两个对象是否是同一个实例。但是,我们可以覆盖equals()方法,来定义自
                  JavaWeb是Java在Web领域的应用,是目前非常热门的技术之一。但是JavaWeb涉及到的技术非常广泛,初学者很容易迷失方向。本文总结了JavaWeb的基础知识,为初学者提供了一份学习笔记分享,希望能够帮助大家快速入门。
                  在Java编程中,字符串操作是很常见的,而替换字符串是其中常用的操作之一。Java提供了三种函数用于替换字符串:replace、replaceAll和replaceFirst。这篇文章将为您详细介绍它们的用法。
                  进制是数学中一种表示数值大小的方法,常见的进制有10进制、2进制、16进制等。
                    <legend id='Leud5'><style id='Leud5'><dir id='Leud5'><q id='Leud5'></q></dir></style></legend>

                  • <tfoot id='Leud5'></tfoot>
                      <tbody id='Leud5'></tbody>
                    <i id='Leud5'><tr id='Leud5'><dt id='Leud5'><q id='Leud5'><span id='Leud5'><b id='Leud5'><form id='Leud5'><ins id='Leud5'></ins><ul id='Leud5'></ul><sub id='Leud5'></sub></form><legend id='Leud5'></legend><bdo id='Leud5'><pre id='Leud5'><center id='Leud5'></center></pre></bdo></b><th id='Leud5'></th></span></q></dt></tr></i><div id='Leud5'><tfoot id='Leud5'></tfoot><dl id='Leud5'><fieldset id='Leud5'></fieldset></dl></div>
                      <bdo id='Leud5'></bdo><ul id='Leud5'></ul>

                        <small id='Leud5'></small><noframes id='Leud5'>