哈希表是一种能够进行快速查找且能够支持高效插入的数据结构,JAVA已经有多个不同的类实现了哈希表,在日常应用中,我们经常会使用哈希表存储一些数据,通过get和push方法实现数据的获取和存储。
先简单看看一些简单的区别
- 大小限制
HashTable和HashMap都有默认的初始化大小,hashTable的默认大小是 11*0.75,hashMap的默认大小是16
- HashTable 继承与Distionary类,使用Entry的数组存储数据,HashMap继承AbstractMap类,使用Entry数组存储数据,可以看到的是,两者的基础bean都是一样的,都包含hash、key、value、next,从数据结构来看,这里应该用到的就是拉链法,拉链法后面会进行详细介绍,简单来说,就是在冲突的时候,通过链表来处理冲突。
- HashTable操作entry数组的时候会使用JAVA的同步关键字,防止多线程的时候,entry数组溢出,而HashMap则无使用,HashTable是线程安全的,而HashMap不是
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快了。
网友评论