the site subtitle

HashMap与HashTable

2019.01.16

简介

HashMap与HashTable均实现了Map接口 HashTable已经过时,HashMap可以通过下面的语句进行同步: Map m = Collections.synchronizeMap(hashMap); 或者使用同步的ConcurrentHashMap

区别

HashMap | HashTable -|- 非线程安全|线程安全 允许null作为键和值|不允许 效率高|较低 非同步|同步,适合多线程环境 fail-fast迭代器|非fail-fast迭代器 不能保证元素次序|- -|提供了对键的列举(Enumeration)。 扩容后是2的次方倍|扩大一倍

JDK1.8之后的HashMap增加了红黑树

红黑树的引入显著提高了Hash的效率,当一个链表太长的时候,HashMap会动态的将它替换成一个红黑树,这话的话会将时间复杂度从O(n)降为O(logn),在Hash极不均匀的情况下,JDK1.7的花费时间是增长的趋势,而JDK1.8是明显的降低趋势,并且呈现对数增长稳定。

什么是同步:

同步sychronized意味着在一次仅有一个线程能够更改Hashtable。就是说任何线程要更新Hashtable时要首先获得同步锁,其它线程要等到同步锁被释放之后才能再次获得同步锁更新Hashtable。

什么是Fail-Safe:

Fail-safe和iterator迭代器相关。如果某个集合对象创建了Iterator或者ListIterator,然后其它的线程试图结构上更改集合对象(即删除或者插入一个元素),将会抛出ConcurrentModificationException异常。但其它线程可以通过set()方法更改集合对象是允许的,因为这并没有从“结构上”更改集合。但是假如已经从结构上进行了更改,再调用set()方法,将会抛出IllegalArgumentException异常。

实现

底层结构

  • jdk1.8以前都是数组+链表
  • jdk1.8,HashMap增加了红黑树,变为数组+链表+红黑树的结构

Hash

  • Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模
  • HashMap计算hash对key的hashcode进行了二次hash,以获得更好的散列值,然后对table数组长度取摸

创建

  • HashMap默认初始化时会创建一个默认容量为16的Entry数组默认加载因子为0.75,同时设置临界值为16*0.75

PUT

  • HashMap会对null值key进行特殊处理,总是放到table[0]位置
  • put过程是先计算hash然后通过hash与table.length取摸计算index值,然后将key放到table[index]位置,当table[index]已存在其它元素时,会在table[index]位置形成一个链表,将新添加的元素放在table[index],原来的元素通过Entry的next进行链接,这样以链表形式解决hash冲突问题,当元素数量达到临界值(capactiy*factor)时,则进行扩容,是table数组长度变为table.length×2
  • 熟悉数据结构的同学很容易发现这就是用拉链法解决冲突的二次Hash
  • 在JDK1.8中,同义词不单单是拉成一条链,在链表太长时还会被组织成红黑树(你又知道了,这个听起来高大上的树,其实就是个二叉查找树)

GET

  • 若key为null,在table[0]的链表上查找key为null的元素
  • 若key不是null,先计算hash然后通过hash与table.length取摸计算index值,然后查找table[index]上的链表,直到找到key,返回