美文网首页
对比Hashtable、HashMap、TreeMap有什么不同

对比Hashtable、HashMap、TreeMap有什么不同

作者: 上官若枫 | 来源:发表于2018-08-12 21:21 被阅读93次

    典型回答

    Hashtable、HashMap、TreeMap都是常见的一些Map实现,是以键值对的形式存储和对操作数据的容器类型。
    • Hashtable,同步,不支持null键和值,很少被推荐
    • HashMap,支持null键和值,不同步,用键值对存取的首选
    • TreeMap基于红黑树的一种访问的Map,存取的时间复杂度都是O(log(n)),且有序

    整体结构

    image.png

    LinkedHashMap和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冲突,都被放置到一个桶内则会形成一个链表,但是链表查询是线性的,严重影响存取性能

    相关文章

      网友评论

          本文标题:对比Hashtable、HashMap、TreeMap有什么不同

          本文链接:https://www.haomeiwen.com/subject/ryfivftx.html