欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JDK源码学习笔记——HashMap

程序员文章站 2022-06-20 09:47:16
HashMap与Hashtable数据结构几乎是相同的(数组+链表),核心方法的实现也大致相同 主要讨论不同,比较两者不同从JDK源码入手 一、父类不同 HashMap父类AbstractMap Hashtable父类Dictionary Dictionary类源码已注释被弃用 Hashtable类 ......

hashmap与hashtable数据结构几乎是相同的(数组+链表),核心方法的实现也大致相同

主要讨论不同,比较两者不同从jdk源码入手

一、父类不同

hashmap父类abstractmap

hashtable父类dictionary

  dictionary类源码已注释被弃用

  hashtable类源码注释也表明hashtable已被淘汰

 * java collections framework</a>.  unlike the new collection
 * implementations, {@code hashtable} is synchronized.  if a
 * thread-safe implementation is not needed, it is recommended to use
 * {@link hashmap} in place of {@code hashtable}.  if a thread-safe
 * highly-concurrent implementation is desired, then it is recommended
 * to use {@link java.util.concurrent.concurrenthashmap} in place of
 * {@code hashtable}.
// 如果你不需要线程安全,那么使用hashmap,如果需要线程安全,那么使用concurrenthashmap。hashtable已经被淘汰了,不要在新的代码中再使用它。

二、synchronize

hashtable是线程安全的,它的每个方法中都加入了synchronize方法。

hashmap不是线程安全的,在多线程并发的环境下,使用hashmap时就必须要自己增加同步处理。

(虽然hashmap不是线程安全的,但是它的效率会比hashtable要好很多。这样设计是合理的。在我们的日常使用当中,大部分时间是单线程操作的。hashmap把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的concurrenthashmap。concurrenthashmap虽然也是线程安全的,但是它的效率比hashtable要高好多倍。因为concurrenthashmap使用了分段锁,并不对整个数据进行锁定。)

三、初始容量和扩充容量

hashmap初始容量16,扩容默认为原来容量的2倍

hashtable初始容量11,扩容默认为原来容量的2倍+1

四、hash值算法不同

hashmap:  具体原因可参考jdk源码学习笔记——hashmap

  1.int hash = (h = key.hashcode()) ^ (h >>> 16) ;

  2.int index = (table.length - 1) & hash;

  3.tablesizefor()方法保证数组容量一定是2的次幂

hashtable:

  1.int hash = key.hashcode();
  2.int index = (hash & 0x7fffffff) % tab.length;

五、put时的不同

1、hashmap支持key==null value==null,hash方法专门有对key==null的处理

    static final int hash(object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashcode()) ^ (h >>> 16);
    }

hashtable不支持null

    public synchronized v put(k key, v value) {
        // make sure the value is not null
        if (value == null) {// value==null抛异常
            throw new nullpointerexception();
        }

        // makes sure the key is not already in the hashtable.
        entry<?,?> tab[] = table;
        int hash = key.hashcode();// key==null抛异常
        int index = (hash & 0x7fffffff) % tab.length;
        @suppresswarnings("unchecked")
        entry<k,v> entry = (entry<k,v>)tab[index];
        for(; entry != null ; entry = entry.next) {
            if ((entry.hash == hash) && entry.key.equals(key)) {
                v old = entry.value;
                entry.value = value;
                return old;
            }
        }

        addentry(hash, key, value, index);
        return null;
    }

2、jdk1.8 hashmap引入了红黑树,链表超过最大长度(8),将链表改为红黑树再添加元素

3、hash碰撞之后的处理

  hashmap:在链表尾加入元素

  hashtable:在链表头加入元素


 

参考资料:

hashmap 和 hashtable 到底哪不同 ?

hashmap 与hashtable的区别