Jack Frost

深入Java基础(四)–哈希表(2)HashTable与HashSet应用及源码详解

又突然想看源码了,继续深入Java基础系列。今天是研究JavaAPI的HashTable和HashSet(顺带讨论线程安全问题)。

本系列:

(1)深入Java基础(一)——基本数据类型及其包装类

(2)深入Java基础(二)——字符串家族

(3)深入Java基础(三)–集合(1)集合父类以及父接口源码及理解

(4)深入Java基础(三)–集合(2)ArrayList和其继承树源码解析以及其注意事项

(5)深入Java基础(四)–哈希表(1)HashMap应用及源码详解

文章结构:(1)HashTable和HashSet概述与基本操作(含线程安全讨论);(2)HashTable源码分析;(3)HashSet源码分析。


一、HashTable和HashSet概述与基本操作(含线程安全讨论):

(1)HashTable:

(一)概述(与HashMap对比进行讲述):此概述大部分参考此博客

1)同是散列表,存储的内容是键值对(key-value)映射。(相同点)

HashMap 是基于“拉链法”实现的散列表。

Hashtable 也是基于“拉链法”实现的散列表。

存取的模式也是相同

2)继承与实现的不同:

HashMap 继承于AbstractMap,实现了Map、Cloneable、java.io.Serializable接口。

Hashtable 继承于Dictionary,实现了Map、Cloneable、java.io.Serializable接口。

Dictionary是一个抽象类,它直接继承于Object类,没有实现任何接口。Dictionary类是JDK 1.0的引入的。虽然Dictionary也支持“添加key-value键值对”、“获取value”、“获取大小”等基本操作,但它的API函数比Map少;而且Dictionary一般是通过Enumeration(枚举类)去遍历,Map则是通过Iterator(迭代器)去遍历。 然而由于Hashtable也实现了Map接口,所以,它即支持Enumeration遍历,也支持Iterator遍历。
AbstractMap是一个抽象类,它实现了Map接口的绝大部分API函数;为Map的具体实现类提供了极大的便利。它是JDK 1.2新增的类。

3)线程安全不同:

Hashtable的几乎所有函数都是同步的,即它是线程安全的,支持多线程。

而HashMap的函数则是非同步的,它不是线程安全的。若要在多线程中使用HashMap,需要我们额外的进行同步处理(Collections类提供的synchronizedMap静态方法或者使用ConcurrentHashMap类)。

4)对null的处理不同:(一会源码解析,在put方法里)

HashMap的key、value都可以为null。

Hashtable的key、value都不可以为null。

Hashtable的key或value,都不能为null!否则,会抛出异常NullPointerException。
HashMap的key、value都可以为null。 当HashMap的key为null时,HashMap会将其固定的插入table[0]位置(即HashMap散列表的第一个位置);而且table[0]处只会容纳一个key为null的值,当有多个key为null的值插入的时候,table[0]会保留最后插入的value。

5)支持的遍历种类不同:

HashMap只支持Iterator(迭代器)遍历。

而Hashtable支持Iterator(迭代器)和Enumeration(枚举器)两种方式遍历。

6)通过Iterator迭代器遍历时,遍历的顺序不同:

HashMap是“从前向后”的遍历数组;再对数组具体某一项对应的链表,从表头开始进行遍历。

Hashtabl是“从后往前”的遍历数组;再对数组具体某一项对应的链表,从表头开始进行遍历。

7)容量的初始值 和 增加方式都不一样:

HashMap默认的容量大小是16;增加容量时,每次将容量变为“原始容量x2”。

Hashtable默认的容量大小是11;增加容量时,每次将容量变为“原始容量x2 + 1”。

8)添加key-value时的hash值算法不同

HashMap添加元素时,是使用自定义的哈希算法。

Hashtable没有自定义哈希算法,而直接采用的key的hashCode()。

9)部分API不同:

Hashtable支持contains(Object value)方法,而且重写了toString()方法;

而HashMap不支持contains(Object value)方法,没有重写toString()方法。

但两者都有containsKey()方法

(二)基本操作:

(三)线程安全的讨论(含例子):

1)我们先去测试探讨hashmap

HashMap应用及源码详解本系列上篇文章讲到其源码:

可知大致是三个操作块是会出现并发问题:

1. HashMap中插入数据的时候

假如A线程和B线程同时进入addEntry,然后计算出了相同的哈希值对应了相同的数组位置,因为此时该位置还没数据,然后对同一个数组位置调用createEntry,两个线程会同时得到现在的头结点,然后A写入新的头结点之后,B也写入新的头结点,那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失。

2.HashMap扩容的时候

当多个线程同时进来,检测到总数量超过门限值的时候就会同时调用resize操作,各自生成新的数组并rehash后赋给该map底层的数组table,结果最终只有最后一个线程生成的新数组被赋给table变量,其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候,就会用已经被赋值的table作为原始数组,这样也会有问题。

3. 删除HashMap中数据的时候都容易出现线程安全问题。

删除这一块可能会出现两种线程安全问题,第一种是一个线程判断得到了指定的数组位置i并进入了循环,此时,另一个线程也在同样的位置已经删掉了i位置的那个数据了,然后第一个线程那边就没了。但是删除的话,没了倒问题不大。
再看另一种情况,当多个线程同时操作同一个数组位置的时候,也都会先取得现在状态下该位置存储的头结点,然后各自去进行计算操作,之后再把结果写会到该数组位置去,其实写回的时候可能其他的线程已经就把这个位置给修改过了,就会覆盖其他线程的修改。

例子验证:

用这个例子跑多几次,就可以发现:key与value不对应。也可发现,是扩容或者增加键值导致的线程问题。

这里写图片描述

2)我们说过Hashtable是线程安全的,,例子说明,无论跑多少次都是key与value对应

(2)HashSet:

(一)概述:

1)一个没有重复元素的集合。

2)由HashMap实现的,不保证元素的顺序,而且HashSet允许使用 null 元素。

3)HashSet是非同步的。如果多个线程同时访问一个哈希 set,而其中至少一个线程修改了该 set,那么它必须 保持外部同步。这通常是通过对自然封装该 set 的对象执行同步操作来完成的。如果不存在这样的对象,则应该使用 Collections.synchronizedSet 方法来“包装” set。最好在创建时完成这一操作,以防止对该 set 进行意外的不同步访问:

4)HashSet通过iterator()返回的迭代器是fail-fast的。

5)HashSet继承于AbstractSet,并且实现了Set接口。HashSet中含有一个”HashMap类型的成员变量”map,HashSet的操作函数,实际上都是通过map实现的。

(二)基本操作:

(三)关于HashSet线程安全问题讨论:

当我们跑多几次就容易遇到。

如果多个线程同时访问一个哈希 set,而其中至少一个线程修改了该 set,那么就很容易发送以下异常:

这里写图片描述


二、HashTable源码分析:

我们来看下hashtable的重要代码:

其实,跟HashMap差不多,扩容机制,增删原理等等,只不过就是在方法前加了synchronized 进行同步(注意hashtable在jdk1.8还没更新到红黑树结构)。不同的只是做了一些值限定。

再次总结重申与HashMap的的比对:

1)二者的存储结构和解决冲突的方法都是相同的。(jdk1.7之前,jdk1.8后,hashmap加入了结构转化–红黑树)

2)HashTable在不指定容量的情况下的默认容量为11,而HashMap为16,Hashtable不要求底层数组的容量一定要为2的整数次幂,而HashMap则要求一定为2的整数次幂。

3)Hashtable中key和value都不允许为null,而HashMap中key和value都允许为null(key只能有一个为null,而value则可以有多个为null)。但是如果在Hashtable中有类似put(null,null)的操作,编译同样可以通过,因为key和value都是Object类型,但运行时会抛出NullPointerException异常,这是JDK的规范规定的。

源码见上面。

如果value为null,会直接抛出NullPointerException异常,但源码中并没有对key是否为null判断!不过NullPointerException属于RuntimeException异常,是可以由JVM自动抛出的,也许对key的值在JVM中有所限制吧。

4)Hashtable扩容时,将容量变为原来的2倍加1,而HashMap扩容时,将容量变为原来的2倍。

5)Hashtable计算hash值,直接用key的hashCode(),而HashMap重新计算了key的hash值,Hashtable在求hash值对应的位置索引时,用取模运算,而HashMap在求位置索引时,则用与运算,且这里一般先用hash&0x7FFFFFFF后,再对length取模,&0x7FFFFFFF的目的是为了将负的hash值转化为正值,因为hash值有可能为负数,而&0x7FFFFFFF后,只有符号外改变,而后面的位都不变。

6)还有遍历方式,因为与HashMap继承不同。


三、HashSet源码分析:

它是基于HashMap实现的。HashSet底层采用HashMap来保存元素,请先阅读我的另一篇博客:哈希表(1)HashMap应用及源码详解

注意:

对于HashSet中保存的对象,请注意正确重写其equals和hashCode方法,以保证放入的对象的唯一性。

所有放入HashSet中的集合元素实际上由HashMap的key来保存,而HashMap的value则存储了一个PRESENT,它是一个静态的Object对象。

将一个key-value对放入HashMap中时,首先根据key的hashCode()返回值决定该Entry的存储位置,如果两个key的hash值相同,那么它们的存储位置相同。如果这个两个key的equalus比较返回true。那么新添加的Entry的value会覆盖原来的Entry的value,key不会覆盖。因此,如果向HashSet中添加一个已经存在的元素,新添加的集合元素不会覆盖原来已有的集合元素。

再次总结重申与HashMap的的比对:

1)HashMap实现了Map接口,HashSet实现了Set接口

2)HashMap储存键值对,HashSet仅仅存储对象

3)HashMap使用put()方法将元素放入map中,HashSet使用add()方法将元素放入set中

4)HashMap中使用键对象来计算hashcode值,HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false

5)HashMap比较快,因为是使用唯一的键来获取对象;HashSet较HashMap来说比较慢


好了,深入Java基础(四)–哈希表(2)HashTable与HashSet应用及源码详解讲完了,又是一篇源码阅读记录,这是积累的必经一步,我会继续出这个系列文章,分享经验给大家。欢迎在下面指出错误,共同学习!!你的点赞是对我最好的支持!!

更多内容,可以访问JackFrost的博客

码字很辛苦,转载请注明来自JackFrost《深入Java基础(四)–哈希表(2)HashTable与HashSet应用及源码详解》

Leave a Reply

Your email address will not be published. Required fields are marked *