作者:兔子东大门一手批发 | 来源:互联网 | 2023-08-21 11:49
HashMap、Hashtable、LinkedHashMap和TreeMap下面针对各个实现类的特点做一些说明:(1)HashMap:它根据键的hashCode值存储数据,大多数
HashMap、Hashtable、LinkedHashMap和TreeMap
下面针对各个实现类的特点做一些说明:
(1) HashMap:它根据键的hashCode值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap最多只允许一条记录的键为null,允许多条记录的值为null。HashMap非线程安全,即任一时刻可以有多个线程同时写HashMap,可能会导致数据的不一致。如果需要满足线程安全,可以用 Collections的synchronizedMap方法使HashMap具有线程安全的能力,或者使用ConcurrentHashMap。
(2) Hashtable:Hashtable是遗留类,很多映射的常用功能与HashMap类似,不同的是它承自Dictionary类,并且是线程安全的,任一时间只有一个线程能写Hashtable,并发性不如ConcurrentHashMap,因为ConcurrentHashMap引入了分段锁。Hashtable不建议在新代码中使用,不需要线程安全的场合可以用HashMap替换,需要线程安全的场合可以用ConcurrentHashMap替换。
(3) LinkedHashMap:LinkedHashMap是HashMap的一个子类,保存了记录的插入顺序,在用Iterator遍历LinkedHashMap时,先得到的记录肯定是先插入的,也可以在构造时带参数,按照访问次序排序。
(4) TreeMap:TreeMap实现SortedMap接口,能够把它保存的记录根据键排序,默认是按键值的升序排序,也可以指定排序的比较器,当用Iterator遍历TreeMap时,得到的记录是排过序的。如果使用排序的映射,建议使用TreeMap。在使用TreeMap时,key必须实现Comparable接口或者在构造TreeMap传入自定义的Comparator,否则会在运行时抛出java.lang.ClassCastException类型的异常。
对于上述四种Map类型的类,要求映射中的key是不可变对象。不可变对象是该对象在创建后它的哈希值不会被改变。如果对象的哈希值发生变化,Map对象很可能就定位不到映射的位置了。
通过上面的比较,我们知道了HashMap是Java的Map家族中一个普通成员,鉴于它可以满足大多数场景的使用条件,所以是使用频度最高的一个。下文我们主要结合源码,从存储结构、常用方法分析、扩容以及安全性等方面深入讲解HashMap的工作原理。
HashMap1.8原理:数组+链表+红黑树
JDK1.8中HashMap的数据结构(数组+链表+红黑树)
一、主要类属性:
默认的初始容量是16
默认的负载因子0.75
当桶上的结点数大于8会转成红黑树
当桶上的结点数小于6红黑树转链表
Node[] table //存储元素的哈希桶数组,总是2的幂次倍
int threshold // 所能容纳的key-value对极限,当put超过这个值的时候就会进行扩容
final float loadFactor // 负载因子
//类属性
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable {
// 序列号
private static final long serialVersiOnUID= 362498820763181265L;
// 默认的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 <<4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 <<30;
// 默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 当桶(bucket)上的结点数大于这个值时会转成红黑树
static final int TREEIFY_THRESHOLD = 8;
// 当桶(bucket)上的结点数小于这个值时树转链表
static final int UNTREEIFY_THRESHOLD = 6;
// 桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
// 存储元素的数组,总是2的幂次倍
transient Node[] table;
// 存放具体元素的集
transient Set> entrySet;
// 存放元素的个数,注意这个不等于数组的长度。
transient int size;
// 每次扩容和更改map结构的计数器
transient int modCount;
// 临界值 当实际大小(容量*填充因子)超过临界值时,会进行扩容
int threshold;
// 填充因子
final float loadFactor;
}
二、在HashMap中,哈希桶数组table的长度length大小必须为2的n次方(一定是合数),HashMap采用这种非常规设计(常规的设计是把桶的大小设计为素数),主要是为了在取模和扩容时做优化。
1、tab[i = (n &#8211; 1) & hash]) 计算索引位置时位运算&速度高于取模运算%
如果length为2的次幂 则length-1 转化为二进制必定是11111……的形式,在与h的二进制与操作效率比较高。扩容的时候只需要看新增的一位的0还是1就可以了。
2、保证元素分布的均匀
而且空间不浪费;如果length不是2的次幂,比如length为15,则length-1为14,对应的二进制为1110,在于h与操作,最后一位都为0,而0001,0011,0101,1001,1011,0111,1101这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率。
三、确定哈希桶数组索引位置
这里的Hash算法本质上就是三步:取key的hashCode值、高位运算、取模运算。
JDK 源码中 HashMap 的 hash 方法原理
右位移16位,正好是32bit的一半,自己的高半区和低半区做异或,就是为了混合原始哈希码的高位和低位,以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征,这样高位的信息也被变相保留下来。
假如没有进行高位运算,那最后参与运算的永远只是取模运算的最后几位,相似性会比较大。
扰动函数
static final int hash(Object key) { //jdk1.8
int h;
// h = key.hashCode() 为第一步 取hashCode值
// h ^ (h >>> 16) 为第二步 高位参与运算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
四、put
了解链表、红黑树转换,扩容的时机
image.png
五、扩容
首次put元素需要进行扩容为默认容量16,阈值16*0.75=12,以后扩容后的table大小变为原来的两倍,接下来就是进行扩容后table的调整:
假设扩容前的table大小为2的N次方,有上述put方法解析可知,元素的table索引为其hash值的后N位确定
那么扩容后的table大小即为2的N+1次方,则其中元素的table索引为其hash值的后N+1位确定,比原来多了一位
因此,table中的元素只有两种情况:
元素hash值第N+1位为0:不需要进行位置调整
元素hash值第N+1位为1:调整至原索引的两倍位置
扩容或初始化完成后,resize方法返回新的table。
总结
(1) 扩容是一个特别耗性能的操作,所以当程序员在使用HashMap的时候,估算map的大小,初始化的时候给一个大致的数值,避免map进行频繁的扩容。
(2) 负载因子是可以修改的,也可以大于1,但是建议不要轻易修改,除非情况非常特殊。
(3) HashMap是线程不安全的,不要在并发的环境中同时操作HashMap,建议使用ConcurrentHashMap。
(4) JDK1.8引入红黑树大程度优化了HashMap的性能,查找的时间复杂度从链表的O(n)优化到O(logn)