HashMap与HashTable

简介

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

区别

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，返回