典型回答
Hashtable、HashMap、TreeMap都是常见的一些Map实现,是以键值对的形式存储和对操作数据的容器类型。
• Hashtable,同步,不支持null键和值,很少被推荐
• HashMap,支持null键和值,不同步,用键值对存取的首选
• TreeMap基于红黑树的一种访问的Map,存取的时间复杂度都是O(log(n)),且有序
整体结构
image.pngLinkedHashMap和TreeMap都能保证某种顺序,但是还不太一样,LinkedHashMap提供的是遍历顺序符合插入顺序,它的实现是通过为条目维护一个双向链表。
HashMap源码分析
HashMap内部结构的结构可以看作是数组和链表结合组成的复合结构,数组被分为一个个桶,通过哈希值决定了键值对在这个数组的寻址;哈希值相同的键值对,则以链表形式存储。如果链表大小超过阈值(8),图中链表就会被改造成树形结构
image.png
HashMap在构造函数的时候,并没有将数组初始化,在调用put方法的时候,在初始化了数组
public V put(K key,V value){
return putVal(hash(key), key, value,false,true);
}
image.png
从putVal方法最初的几行,我们可以发现:
• 如果表格是null,resize会负责初始化它。
• resize方法兼顾两个职责,创建初始存储表格,或者在容量不满足需求的时候,进行扩容
• 具体键值对在哈希表中的位置(数组index)取决于下面的位运算:
i = (n-1)&hash
此处hash取决于hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
首先从这能看出来,hashmap的key是可以为null的,另外首先是拿出key的hash值,另外让key的hash值无条件右移,然后再进行异或。这种方法可以有效保护hash值的高位,因为有些数据计算出的hash值主要差距在高位,而hashmap的 hash寻址是忽略容量以上高位的,可以避免hash碰撞。
• 链表结构(bin)会在达到门限值时,发生树化。
resize()源码
image.png• 门限值(此处门限值指的是扩容的门限值,不是树化的阈值)等于(负载因子)× (容量),如果构建HashMap的时候没有指定它们,那么就是依据相应的默认常量值。门限值大部分都是整数
• 扩展后,需要将老的数组中的元素,重新放置到新的数组,这是扩容的一个主要开销来源。
容量、负载因子和树化
容量和负载因子决定了可用的桶数量,空桶太多会浪费空间,如果使用的太满会影响操作性能。假设只有一个桶,那么它就退化成了链表,完全不能提供所谓的常熟时间存的性能
对于负载因子:
•如果没有特别需求,不要轻易更改,JDK自身的事符合需求的
•如果需要调整,不要设置超过0.75的数值,因为会显著增加冲突,降低HashMap的性能,导致桶太满,链表查找太严重(红黑树的时间复杂度是NlogN,数组的是N,在N比较大的时候,数组更快)
•如果太小会导致频繁扩容,增加无谓的开销
树化的代码
image.png当bin数量也就是链表数量大于TREEIFY_THRESHOLD的时候:
•如果容量小于MIN_TREEIFY_CAPACITY只会进行扩容,如果大于MIN_TREEIFY_CAPACITY的话就会进行树化
在元素放置过程中,如果一个对象hash冲突,都被放置到一个桶内则会形成一个链表,但是链表查询是线性的,严重影响存取性能
网友评论