文档章节

hashMap的原理和使用

P
 PanJia丶
发布于 2017/05/04 18:38
字数 1206
阅读 10
收藏 0

hashMap的特点

  • 官方文档:
  • Hash table based implementation of the <tt>Map</tt> interface.  This
      implementation provides all of the optional map operations, and permits
      <tt>null</tt> values and the <tt>null</tt> key.  (The <tt>HashMap</tt>
      class is roughly equivalent to <tt>Hashtable</tt>, except that it is
      unsynchronized and permits nulls.)  This class makes no guarantees as to
      the order of the map; in particular, it does not guarantee that the order
      will remain constant over time.

    

  •  基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作,并允许使用 null 值和 null 键。(除了不同步和允许使用 null 之外,HashMap 类与 Hashtable 大致相同。)此类不保证映射的顺序,特别是它不保证该顺序恒久不变。另外,HashMap是非线程安全的,也就是说在多线程的环境下,可能会存在问题,而Hashtable是线程安全的。

hashmap的工作原理

  • HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,返回的hashCode用于找到bucket位置来储存Entry对象。
  • hash表结构

            

  •  从上图我们可以发现哈希表是由数组+链表组成的,结点一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。如:12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。

hashcode值相同时会怎样,如何获取值对象?

  • 源码:
  •  
    final Entry<K,V> getEntry(Object key) {
            if (size == 0) {
                return null;
            }
            //1.获取hash值
            int hash = (key == null) ? 0 : hash(key);
            //2.获取hash值对应的table的位置
            for (Entry<K,V> e = table[indexFor(hash, table.length)];
                 e != null;
                 e = e.next) {
                Object k;
                //3.keys.equals()方法
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
            return null;
        }

     

  • 如果hashcode相同,它们的bucket位置相同,‘碰撞’会发生。因为HashMap使用链表存储对象,这个Entry(包含有键值对的Map.Entry对象)会存储在链表中.当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。

可以使用自定义的对象作为键值吗?

  • 你可能使用任何对象作为键,只要它遵守了equals()和hashCode()方法的定义规则,并且当对象插入到Map中之后将不会再改变了。如果这个自定义对象是不可变的,那么它已经满足了作为键的条件,因为当它创建之后就已经不能改变了。

concurrentHashMap来代替hashtable吗?

  • 我们知道HashTable是synchronized的,但是ConcurrentHashMap同步性能更好,因为它仅仅根据同步级别对map的一部分进行上锁。所以ConcurrentHashMap可以代替HashTable,但是HashTable提供更强的线程安全性。
  • concurrentHashMap对比hashtable

        从上图可以看出,当HashTable同步的时候要对整个整个hashtable进行lock,而ConcurrentHashMap只对当前要操作的部分进行锁操作,只有在获取size的时候才要对整个ConcurrentHashMap进行lock,ConcurrentHashMap又是读写锁分离的,所以,ConcurrentHashMap比HashTable性能更优.

HashMap的大小超过了负载因子(load factor)定义的容量

  • 当初始化HashMap时,会有两个参数loadFactor(负载因子,默认0.75),capacity(容量,默认16),两个参数都可以调整,但是负载因子不大于1,且容量必须为2的次幂[如果length为2的N次方,取模运算可以变成位与运算,效率显著提高],当一个map填满了75%的bucket时候,和其它集合类(如ArrayList等)一样,将会创建原来HashMap大小的两倍的bucket数组,来重新调整map的大小,并将原来的对象放入新的bucket数组中。这个过程叫作rehashing,因为它调用hash方法找到新的bucket位置.
  • 当重新调整HashMap大小的时候,会存在条件竞争,因为如果两个线程都发现HashMap需要重新调整大小了,它们会同时试着调整大小。在调整大小的过程中,存储在链表中的元素的次序会反过来,因为移动到新的bucket位置的时候,HashMap并不会将元素放在链表的尾部,而是放在头部,这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了,那么就死循环了。

© 著作权归作者所有

P
粉丝 0
博文 2
码字总数 1206
作品 0
海淀
程序员
私信 提问
常见面试题——HashMap工作原理的介绍!

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道HashTable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

欧阳海阳
2018/06/24
0
0
HashMap 工作原理

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

The_flying_pig
2017/09/19
0
0
HashMap的工作原理【文字版】

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

半夏alvin
2016/01/07
21
0
hashmap实现原理浅析

看了下JAVA里面有HashMap、Hashtable、HashSet三种hash集合的实现源码,这里总结下,理解错误的地方还望指正 HashMap和Hashtable的区别 HashSet和HashMap、Hashtable的区别 HashMap和Hashtab...

商者
2016/03/30
37
0
HashMap的工作原理及HashMap和Hashtable的区别

HashMap的工作原理是近年来常见的Java面试题。几乎每个Java程序员都知道HashMap,都知道哪里要用HashMap,知道Hashtable和HashMap之间的区别,那么为何这道面试题如此特殊呢?是因为这道题考...

袁梓皓
2016/03/09
91
0

没有更多内容

加载失败,请刷新页面

加载更多

Jenkins 中文本地化的重大进展

本文首发于:Jenkins 中文社区 我从2017年开始,参与 Jenkins 社区贡献。作为一名新成员,翻译可能是帮助社区项目最简单的方法。 本地化的优化通常是较小的改动,你无需了解项目完整的上下文...

Jenkins中文社区
32分钟前
3
0
Spring中如何使用设计模式

关于设计模式,如果使用得当,将会使我们的代码更加简洁,并且更具扩展性。本文主要讲解Spring中如何使用策略模式,工厂方法模式以及Builder模式。 1. 策略模式 关于策略模式的使用方式,在S...

爱宝贝丶
40分钟前
3
0
前后端分离-前端搭建(vue)

前端使用vue,那么怎么搭建vue呢 先安装nodejs以及npm 现在基本的nodejs都包含有npm,下载安装后, 可以在cmd命令里输入 node -v 和npm -v 分别查看安装的版本 两个都显示了版本就是安装ok ...

咸鱼-李y
今天
3
0
聊聊elasticsearch的DeadlockAnalyzer

序 本文主要研究一下elasticsearch的DeadlockAnalyzer DeadlockAnalyzer elasticsearch-7.0.1/server/src/main/java/org/elasticsearch/monitor/jvm/DeadlockAnalyzer.java public class Dea......

go4it
今天
2
0
微信点击链接,用默认浏览器中打开指定网址链接!

最近有客户咨询,自己的链接在微信种推广,经常会被无缘无故封杀,有没有一种功能,用户在微信中点击我们推广的链接,可以自动强制跳转到手机默认浏览器中打开指定的网址链接?这样我们的网址...

家布朗根
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部