HashMap和HashTable源代码分析

哈希表是一种能够进行快速查找且能够支持高效插入的数据结构，JAVA已经有多个不同的类实现了哈希表，在日常应用中，我们经常会使用哈希表存储一些数据，通过get和push方法实现数据的获取和存储。

先简单看看一些简单的区别

• 大小限制
  HashTable和HashMap都有默认的初始化大小,hashTable的默认大小是 11*0.75，hashMap的默认大小是16

QQ截图20170215200405.png

• HashTable 继承与Distionary类，使用Entry的数组存储数据，HashMap继承AbstractMap类，使用Entry数组存储数据，可以看到的是，两者的基础bean都是一样的，都包含hash、key、value、next，从数据结构来看，这里应该用到的就是拉链法，拉链法后面会进行详细介绍，简单来说，就是在冲突的时候，通过链表来处理冲突。

2.png

• HashTable操作entry数组的时候会使用JAVA的同步关键字，防止多线程的时候，entry数组溢出，而HashMap则无使用，HashTable是线程安全的，而HashMap不是

Paste_Image.png

JDK1.7使用了拉链法

Paste_Image.png Paste_Image.png

• 简单来说，拉链法就是数组里面的每一个元素都会作为一个链表的头结点，当通过put方法将数据放进哈希表时，哈希算法计算到的数组位置如果是相同的元素，会组建成链表，从而解决冲突。
• 拉链法优化性能，都是通过扩大容量来减少冲突，为什么呢？因为每一条链表的长度都会缩短，通过哈希算法计算出数组位置一样的可能性降低了。

void transfer(Entry[] newTable) {  
 Entry[] src = table;                   //src引用了旧的Entry数组  
 int newCapacity = newTable.length;  
 for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组  
     Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素  
     if (e != null) {  
         src[j] = null;//释放旧Entry数组的对象引用（for循环后，旧的Entry数组不再引用任何对象）  
         do {  
             Entry<K, V> next = e.next;  
             int i = indexFor(e.hash, newCapacity); //！！重新计算每个元素在数组中的位置  
             e.next = newTable[i]; //标记[1]  
             newTable[i] = e;      //将元素放在数组上 
             e = next;             //访问下一个Entry链上的元素(访问链表的下一个元素，链表头结点就是newTable[i]) 
         } while (e != null);  
     }  
 }
}

HashTable是如何解决线程安全的？

HashTable类的实例，对于不同线程的临界区是entry数组，不同线程之间对该数组进行插入、更新、删除操作可能会造成线程安全问题。由于entry数组里面有很多个元素，如果想对entry数组加synchronized关键字显然不可能，因为你不知道，每一个线程到底什么时候才会对哪个元素进行操作。HashTable使用了最简单的办法，那就是将数组作为一个整体，对于访问该数组的方法，基本上都加了synchronized关键字，。但由于这样锁的粒度会比较大，性能也就没有concurrentHashMap快了。