文档章节

HashMap的特性

GGbird
 GGbird
发布于 09/22 09:22
字数 1398
阅读 26
收藏 0

一、hashmap数据结构:哈希表结构:数组+链表

hashmap调用默认构造方法会产生一个默认底层是长度为16的Entry数组,首先调用key的hasCode()方法来得到一个整数, int hash = hash(key.hashCode()); 这个整数就是哈希码,然后把哈希码作为参数传递到hash()函数中来进行运算,即散列运算,得到一个int类型的散列值 int i = indexFor(hash, table.length); (transient Entry[] table;) 把散列值和数组的长度来进行运算,最终得到Entry对象要存放到数组的位置(下标)。 hashmap内部的结构是数组加单向链表结构,因为不同的key有可能计算出相同的散列值,根据散列值计算出来的存放到数组的下标会冲突(同一个下标值),此时, 如果键相同,散列值也一样,说明是同一个对象,此时会将键所对应的旧值用新的键值覆盖掉, 如果散列值一样,键名不一样,说明是不同的对象,此时会把键值对封装成entry对象放到那个散列值对应的下标位置处, 原来那个entry对象会以链表形式链接在新创建的entry对象后面

注:

1)HashMap可以接受null键值和值,而HashTable则不能,HashMap是非synchronized的;存储的是键值对。

2)HashMap负载因子默认是0.75,可设置,当map填满了75%的bucket(entry数组)时候,将会创建原来HashMap大小两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中,这个过程叫做rehashing,因为它调用hash方法找到新的bucket位置。

3) 重新调整map大小可能会发生竞争问题:如果两个线程都发现HashMap需要调整大小了,它们都会尝试进行调整,在调整中,存储在链表中的元素的次序会反过来,因为移动bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历,如果条件竞争发生了,就死循环了。

二、判断存储对象是否重复:重写 hashcode 和 equals 方法

 @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Test1 test1 = (Test1) o;
        return Objects.equals(name, test1.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name);
    }

hash值的算法如下

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

三、HashMap的链表数据结构是用来解决什么问题

解决哈希冲突

  1. JDK1.7的HashMap是由数组+链表构成的,新增一个数通过哈希算法,计算出对应存放在数组的某个位置,如果这个位置已经存在数据了,也就是说存在了哈希冲突,这时候JDK1.7就将新增的数和原来的数构成一个链表放在数组这个位置,后面冲突的数依次都放入链表中。
  2. 通常解决哈希冲突有两种办法,上面所说的通过链表的形式称为链地址法;还有一种方法称为开放地址法,也就是说如果存在哈希冲突了,那么将新增的值在用一个新的哈希算法算出所存的位置插入,但是这还会构成二次冲突,三次冲突.....
  3. JDK1.8的HashMap是由数组+链表+红黑树构成,当链表长度超过8会自动转换成红黑树,红黑树节点个数小于6,又自动转换为链表。这是为了提高检索效率(红黑树检索效率明显是高于链表的)

四、JDK1.8后HashMap 新增特性

java8中HashMap的最大不同是,它利用了红黑树,即由数组+链表+红黑树组成。

在Java8以前的版本中,我们查找一个数据的时候,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)。

为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

当然,上图只是一个结构示意图,主要是描述结构,不会达到这个状态的,因为这么多数据的时候早就扩容了。

Java7 中使用 Entry 来代表每个 HashMap 中的数据节点,Java8 中使用 Node,基本没有区别,都是 key,value,hash 和 next 这四个属性,不过,Node 只能用于链表的情况,红黑树的情况需要使用 TreeNode。

我们根据数组元素中,第一个节点数据类型是 Node 还是 TreeNode 来判断该位置下是链表还是红黑树的。

四、HashMap与HashTable的区别

HashMap允许储存null的key,value值,并且线程是不安全的,因此效率高

HashTable不允许储存null的key,value值,线程安全,因此效率低

© 著作权归作者所有

GGbird
粉丝 1
博文 12
码字总数 4720
作品 0
私信 提问
JDK源码阅读(三)、LinkedHashMap

一、LinkedHashMap原理 LinkedHashMap继承自HashMap,所以,它有hashMap的全部特性,它内部采用存储数据额的节点继承自HashMap的node。有一个before与after用于维护插入或者访问的顺序。它内...

zq17865815296
2018/03/28
0
0
【Java入门提高篇】Day28 Java容器类详解(十)LinkedHashMap详解

  今天来介绍一下容器类中的另一个哈希表———》LinkedHashMap。这是HashMap的关门弟子,直接继承了HashMap的衣钵,所以拥有HashMap的全部特性,并青出于蓝而胜于蓝,有着一些HashMap没有...

弗兰克的猫
2018/08/10
0
0
浅谈HashSet

HashSet结构图 HashSet.png HashSet主要方法 public boolean add(E e) public boolean remove(Object o) HashSet方法解读 public boolean add(E e)源码: public boolean remove(Object o)源......

小鱼嘻嘻
2017/10/28
0
0
HashMap, HashTable, HashSet分析

HashMap分析: 其主要特性:(key-value)存储,key-value可为NULL, 非线程安全。 其主要属性: //默认容量微16static final int DEFAULTINITIALCAPACITY = 1 << 4;//最大容量2^30static fina...

ihaolin
2014/03/11
299
0
Java集合--HashSet

概述 HashSet 实现了 Set 接口,是一个不包含重复元素的集合。通过源代码分析一下 HashSet 是如何做到元素不重复的。 继承关系 继承自 AbstractSet 抽象类,实现了 Set 接口 内部结构 定义了...

gaob2001
2018/11/26
11
0

没有更多内容

加载失败,请刷新页面

加载更多

带你了解 Java内存模型

Java内存模型的规定: 1、所有变量存储在主内存中; 2、每个线程都有自己的工作内存,且对变量的操作都是在工作内存中进行; 3、不同线程之间无法直接访问彼此工作内存中的变量,要想访问只能...

linux-tao
18分钟前
3
0
.net c# datetime转string 时间转字符串

.net c# datetime转string 时间转字符串 .net c# datetime转string 时间转字符串 刚开始接触net 时间转换字符串 一搜索出来的全是 字符串转时间,要么就是系统当前时间转字符串 就没有一个指...

青峰Jun19er
19分钟前
3
0
hbase demo

HbaseDao public class HbaseDao {@Testpublic void insertTest() throws Exception {Configuration conf = HBaseConfiguration.create();conf.set("hbase.zookeeper.qu......

Garphy
29分钟前
2
0
IT兄弟连 HTML5教程 HTML5表单 多样的输入类型2

4 range range类型用于包含一定范围内数字值的输入域,跟number一样,我们还可以对数值设置限定,range类型显示为滑动条用法如下: 上述代码使用了range类型输入框,为该类型设置了数值范围为...

老码农的一亩三分地
29分钟前
2
0
对比不同的数据库连接的异同

博主在学习和使用数据库连接时,遇到的问题, 这个几个数据库连接究竟有什么不同? 到底什么时候该使用哪个会更好一点? 带着这个问题我们先去了解常见的数据库连接 1. 常见的数据库连接有哪些?...

理性思考
31分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部