专栏首页java初学hashMap原理(java8)

hashMap原理(java8)

(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap

(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它继承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。

(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。

(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。

  上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。

  通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。下文我们主要结合源码,从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。

  HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)

(1) 从源码可知,HashMap类中有一个非常重要的字段,就是 Node[] table,即哈希桶数组,明显它是一个Node的数组。我们来看Node[JDK1.8]是何物。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

  Node是HashMap的一个内部类,实现了Map.Entry接口,本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

(2) HashMap就是使用哈希表来存储的。哈希表为解决冲突,可以采用开放地址法和链地址法等来解决问题,Java中HashMap采用了链地址法。链地址法,简单来说,就是数组加链表的结合。在每个数组元素上都一个链表结构,当数据被Hash后,得到数组下标,把数据放在对应下标元素的链表上。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • java — 线程池

    Mister24
  • android入门 — AlertDialog对话框

    Mister24
  • java线程安全— synchronized和volatile

    Mister24
  • JDK源码阅读(八):最简单的HashSet源码分析

    继续分析源码,上一篇文章把HashMap的分析完毕。本文开始分析HashSet简单的介绍一下。

    乱敲代码
  • Java集合总结

    Java集合类主要有2大分支,Collection及Map。 Collection体系如下:

    用户5325874
  • HashMap 与 HashTable的对比

    而负载因子表示一个散列表的空间的使用程度,有这样一个公式:initailCapacity*loadFactor=HashMap的容量。

    desperate633
  • Java 并发(1)AbstractQueuedSynchronizer 源码分析之概要分析

    链接 | http://www.cnblogs.com/liuyun1995/p/8400663.html

    一个优秀的废人
  • 和阿里面试官对线,多亏看完这篇HashSet源码解析

    HashSet 是一个没有重复元素的集合.主要由 HashMap 实现,不保证元素顺序,而允许 null 元素.非线程安全,如果需要安全请自行加锁,或者使用 C...

    JavaEdge
  • 什么是计算机程序?操作系统、指令、进程、线程等

    不管你用了多少技术,框架,模式,实现了怎么样的协议与功能,原理是什么,也只是人类意识层面上的内容,到底层只有指令。

    一个会写诗的程序员
  • 换个姿势学设计模式-策略模式

    前段时间,接到一个需求:开发一个聚合支付服务,对其他内部项目提供统一的接口来实现不同支付平台的支付能力发起,比如支付宝,微信,银联等。为了处理相似的支付操作而各...

    闻人的技术博客

扫码关注云+社区

领取腾讯云代金券