什么是HashMap?工作原理?与Hashtable的区别
什么是HashMap?
- HashMap是一个散列的桶(底层结构:数组+链表),以键值对(key-value)方式进行数据存储.
- HashMap采用了数组+链表的数据结构,在查询和修改继承了数组的线性查找和链表的寻址查找.
- HashMap是非synchronized(非线程安全),所以HashMap很快
- HashMap可以接受null键和值,而Hashtable则不能(原因就是equlas()方法需要对象,因为HashMap是后出的API经过处理才可以)
HashMap的工作原理?
HashMap是基于hashing的原理,我们使用put(key, value)存储对象到HashMap中,使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时,我们先对键调用hashCode()方法,计算并返回的hashCode是用于找到Map数组的bucket位置来储存Node 对象。这里关键点在于指出,HashMap是在bucket中储存键对象和值对象,作为Map.Node 。
以下是HashMap初始化 ,简单模拟数据结构
下面是具体的put过程(JDK1.8版)
- 对Key求Hash值,然后再计算下标
- 如果没有碰撞,直接放入桶中(碰撞的意思是计算得到的Hash值相同,需要放到同一个bucket中)
- 如果碰撞了,以链表的方式链接到后面
- 如果链表长度超过阀值( TREEIFY THRESHOLD==8),就把链表转成红黑树,链表长度低于6,就把红黑树转回链表(红黑树下面拓展)
- 如果节点已经存在就替换旧值
- 如果桶满了(容量16*加载因子0.75),就需要 resize(扩容2倍后重排)
以下是具体get过程(考虑特殊情况如果两个键的hashcode相同,你如何获取值对象?)
当我们调用get()方法,HashMap会使用键对象的hashcode找到bucket位置
找到bucket位置之后,会调用keys.equals()方法去找到链表中正确的节点,最终找到要找的值对象。
不同的key计算出的HashCode相同就会发生碰撞以链表存储会减慢速度,那有什么办法减少碰撞呢?
扰动函数 (扰动即Hash方法内部的算法实现,目的是让不同对象返回不同hashcode)可以减少碰撞.原理是如果两个不相等的对象返回不同的hashcode的话,那么碰撞的几率就会小些这就意味着存链表结构减小,因此就不会频繁调用equal方法,这样就能提高HashMap的性能.
使用不可变的、声明作final的对象,并且采用合适的equals()和hashCode()方法将会减少碰撞的发生。不可变性使得能够缓存不同键的hashcode,这提高了整个获取对象的速度,所以使用String,Interger这样的类作为键是非常好的选择。
为什么String, Interger这样的类适合作为键?因为String是final的,而且已经重写了equals()和hashCode()方法了。
不可变性是必要的,因为为了要计算hashCode(),就要防止键值改变,如果键值在放入时和获取时返回不同的hashcode的话,那么就不能从HashMap中找到你想要的对象。
红黑树拓展
- 每个节点非红即黑
- 根节点总是黑色的
- 如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
- 每个叶子节点都是黑色的空节点(NIL节点)
- 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
HashTable
数组 + 链表方式存储
默认容量:11(质数 为宜)
put:- 索引计算 : (key.hashCode() & 0x7FFFFFFF)% table.length
若在链表中找到了,则替换旧值,若未找到则继续
当总元素个数超过容量*加载因子时,扩容为原来 2 倍并重新散列。
将新元素加到链表头部
对修改 Hashtable 内部共享数据的方法添加了 synchronized,保证线程安全
HashMap与Hashtable的区别
- 默认容量不同。扩容不同
- 线程安全性,HashTable 安全
- 效率不同 HashTable 要慢因为加锁