深入解析HashMap、HashTable

Java集合类是个非常重要的知识点,HashMap、HashTable、ConcurrentHashMap等算是集合类中的重点,可谓“重中之重”,首先来看个问题,如面试官问你:HashMap和HashTable有什么区别,一个比较简单的回答是:
1、HashMap是非线程安全的,HashTable是线程安全的。
2、HashMap的键和值都允许有null值存在,而HashTable则不行。
3、因为线程安全的问题,HashMap效率比HashTable的要高。
能答出上面的三点,简单的面试,算是过了,但是如果再问:Java中的另一个线程安全的与HashMap及其类似的类是什么?同样是线程安全,它与HashTable在线程同步上有什么不同?能把第二个问题完整的答出来,说明你的基础算是不错的了.
一、HashMap的内部存储结构
Java中数据存储方式最底层的两种结构,一种是数组,另一种就是链表,数组的特点:连续空间,寻址迅速,但是在删除或者添加元素的时候需要有较大幅度的移动,所以查询速度快,增删较慢。而链表正好相反,由于空间不连续,寻址困难,增删元素只需修改指针,所以查询慢、增删快。有没有一种数据结构来综合一下数组和链表,以便发挥他们各自的优势?答案是肯定的!就是:哈希表。哈希表具有较快(常量级)的查询速度,及相对较快的增删速度,所以很适合在海量数据的环境中使用。一般实现哈希表的方法采用“拉链法”,我们可以理解为“链表的数组”,如下图:
从上图中,我们可以发现哈希表是由数组+链表组成的,一个长度为16的数组中,每个元素存储的是一个链表的头结点。那么这些元素是按照什么样的规则存储到数组中呢。一般情况是通过hash(key)%len获得,也就是元素的key的哈希值对数组长度取模得到。比如上述哈希表中,12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存储在数组下标为12的位置。它的内部其实是用一个Entity数组来实现的,属性有key、value、next。接下来我会从初始化阶段详细的讲解HashMap的内部结构。
二、HashTable的内部存储结构
HashTable和HashMap采用相同的存储机制,二者的实现基本一致,不同的是:
1、HashMap是非线程安全的,HashTable是线程安全的,内部的方法基本都是synchronized。
2、HashTable不允许有null值的存在。
在HashTable中调用put方法时,如果key为null,直接抛出NullPointerException。其它细微的差别还有,比如初始化Entry数组的大小等等,但基本思想和HashMap一样。
三、HashTable和ConcurrentHashMap的比较
ConcurrentHashMap是线程安全的HashMap的实现。同样是线程安全的类,它与HashTable在同步方面有什么不同呢?
之前我们说,synchronized关键字加锁的原理,其实是对对象加锁,不论你是在方法前加synchronized还是语句块前加,锁住的都是对象整体,但是ConcurrentHashMap的同步机制和这个不同,它不是加synchronized关键字,而是基于lock操作的,这样的目的是保证同步的时候,锁住的不是整个对象。事实上,ConcurrentHashMap可以满足concurrentLevel个线程并发无阻塞的操作集合对象。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据