HashMap底层原理是怎么实现的

2021-02-19 10:15发布

13条回答
summer
2楼 · 2021-02-19 16:27

HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

freediandianer
3楼 · 2021-02-19 17:47

在JDK1.6,JDK1.7中,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用位桶+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

简单说下HashMap的实现原理:

首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中


浅浅77
4楼 · 2021-02-20 08:50

在JDK1.6,JDK1.7中,HashMap采用位桶+链表实现,即使用链表处理冲突,同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多,即hash值相等的元素较多时,通过key值依次查找的效率较低。而JDK1.8中,HashMap采用位桶+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树,这样大大减少了查找时间。

简单说下HashMap的实现原理:

首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中

即HashMap的原理图是: 

image.png

熊晓燕
5楼 · 2021-02-20 09:02

HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

思禹小姐姐y
6楼 · 2021-02-20 09:48

简单说下HashMap的实现原理:

首先有一个每个元素都是链表(可能表述不准确)的数组,当添加一个元素(key-value)时,就首先计算元素key的hash值,以此确定插入数组中的位置,但是可能存在同一hash值的元素已经被放在数组同一位置了,这时就添加到同一hash值的元素的后面,他们在数组的同一位置,但是形成了链表,同一各链表上的Hash值是相同的,所以说数组存放的是链表。而当链表长度太长时,链表就转换为红黑树,这样大大提高了查找的效率。

当链表数组的容量超过初始容量的0.75时,再散列将链表数组扩大2倍,把原链表数组的搬移到新的数组中


三岁奶猫
7楼 · 2021-02-20 10:42

hashmap底层原理是HashMap基于hashing原理,通过put和get方法储存和获取对象。当将键值对传递给put方法时,它调用键对象的hashCode方法来计算hashcode,然后找到bucket位置来储存值对象。当获取对象时,通过键对象的equals方法找到正确的键值对,然后返回值对象。HashMap使用链表来解决碰撞问题,当发生碰撞了,对象将会储存在链表的下一个节点中。HashMap在每个链表节点中储存键值对对象。

aijingda
8楼 · 2021-02-20 10:44

 HashMap的主干是一个Entry数组。Entry是HashMap的基本组成单元,每一个Entry包含一个key-value键值对。

//HashMap的主干数组,可以看到就是一个Entry数组,初始值为空数组{},主干数组的长度一定是2的次幂,至于为什么这么做,后面会有详细分析。
transient Entry[] table = (Entry[]) EMPTY_TABLE;

 Entry是HashMap中的一个静态内部类。代码如下

    static class Entry implements Map.Entry {
        final K key;
        V value;
        Entry next;//存储指向下一个Entry的引用,单链表结构
        int hash;//对key的hashcode值进行hash运算后得到的值,存储在Entry,避免重复计算

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }


秀儿
9楼 · 2021-02-20 11:00

HashMap由数组+链表组成的,数组是HashMap的主体,链表则是主要为了解决哈希冲突而存在的,如果定位到的数组位置不含链表(当前entry的next指向null),那么对于查找,添加等操作很快,仅需一次寻址即可;如果定位到的数组包含链表,对于添加操作,其时间复杂度为O(n),首先遍历链表,存在即覆盖,否则新增;对于查找操作来讲,仍需遍历链表,然后通过key对象的equals方法逐一比对查找。所以,性能考虑,HashMap中的链表出现越少,性能才会越好。

相关问题推荐

  • 回答 17
    已采纳

    CSS为HTML标记语言提供了一种样式描述,定义了其中元素的显示方式。CSS在Web设计领域是一个突破。利用它可以实现修改一个小的样式更新与之相关的所有页面元素。总体来说,CSS具有以下特点:丰富的样式定义CSS提供了丰富的文档样式外观,以及设置文本和背景属性...

  • 回答 16
    已采纳

    CSS盒子模型就是在网页设计中经常用到的CSS技术所使用的一种思维模型。 盒子模型(Box Modle)可以用来对元素进行布局,包括内边距,边框,外边距,和实际内容这几个部分。盒子模型分为两种:第一种是W3c标准的盒子模型(标准盒模型)第二种IE标准的盒子模型(怪...

  • 回答 15

    浮动和定位都可以使元素脱离标准文档流,提升层级,  浮动脱离文档流,提高半个层级,不能完全覆盖下面元素(不能覆盖图片文字)定位脱离标准文档流,提升一个层级,可以完全覆盖下面元素及其内容...

  • 回答 19

    递归做为一种算法在程序设计语言中广泛应用.是指函数/过程/子程序在运行过程中直接或间接调用自身而产生的重入现象

  • 回答 3

    一段文字在标签的宽度内是不会自动换行的,可以给标签设置小一点的宽度,碰到标签的右边缘就会自动换行了

  • 回答 13
    已采纳

    内联样式,如: style= ,权值为1000。ID选择器,如:#content,权值为0100。类,伪类和属性选择器,如.content,权值为0010。类型选择器和伪元素选择器,如div p,权值为0001。通配符、子选择器、相邻选择器等的。如*、>、+,权值为0000。继承的样式没有权值。...

  • 回答 17

    定位:1、相对定位 position:relative; 兼容2、绝对定位 absolut 兼容3、固zhuan定定位 fixed ie6不兼容

  • 回答 15
    已采纳

    css中有很多选择器,比如类别选择器、标签选择器、ID选择器、后代选择器、子选择器、伪类选择器、通用选择器、群组选择器等,常见的选择器有id选择器、类选择器、标签选择器三大类。...

  • 回答 4

    如果一个元素覆盖在另外一个元素之上,而你想显示下面的元素,这时你就需要把上面这个元素的background设置为transparent transparent在 不同 css版

  • 回答 4

    怎样在CSS样式中设置背景的透明度,下面一个具体的实例。把类为box的层设为透明。.box{width:300px;height:200px;margin:0auto;boxder:1pxsolid#ccc;background:#000;filter:alpha(opacity:30);opacity:0.3;-moz-opacity:0.3;-khtml-o...

  • 回答 6

    解决方案You can check if the image's color model includes an alpha channel:BufferedImage img = ImageIO.read(/* from somewhere */);if (img.getColorModel().hasAlpha()) {undefined// img has alpha channel...

  • 回答 5

    找到 eclipse 的安装目录 进入到 plugins 文件夹下,这个文件是管理 eclipse样式相关的文件夹然后我们进入它的子目录 org.eclipse.ui.themes_1.2.1.v20170809-1435 文件夹,去里面找 与 eclipse 相关的样式设置,继续寻找来到 这个界面。 考到css 文件夹,与...

  • 回答 6

    css问题filter: alpha(opacity=100,finishopacity=0,style=2)alpha是来设置透明度的,它的基本属性是filter:alpha(opacity,finishopacity,style,startX,startY,finishX,finishY).opacity代表透明度数,选值0-100,0是完全透明,100是不透明.finishopacit...

  • 回答 4

    设置背景颜色:要设置背景颜色,直接使用background:颜色值;即可。如:body{background:#000}将body的背景颜色设置为黑色。 设置背景图片:1.规律背景图片。不如我们要设置一个渐变的背景图片,这种背景只需要切出1像素宽,高度合适的图片作为背景即可。body...

  • 回答 2

    原因分析: 使用css的opcity属性改变某个元素的透明度,但是其元素下的子元素的透明度也会被改变,即便重定义也没有用,不过有个方法可以实现,大家可以看看。 可以使用一张透明的图片做背景可以达成效果...

  • 回答 3

    用css 隐藏掉overflow在用div 模拟重画滚动条,用div和z-index配合模拟滚动条

没有解决我的问题,去提问