美文网首页
HashMap和HashTable源代码分析

HashMap和HashTable源代码分析

作者: SteveGuRen | 来源:发表于2017-02-15 20:29 被阅读31次

    哈希表是一种能够进行快速查找且能够支持高效插入的数据结构,JAVA已经有多个不同的类实现了哈希表,在日常应用中,我们经常会使用哈希表存储一些数据,通过get和push方法实现数据的获取和存储。

    先简单看看一些简单的区别

    • 大小限制
      HashTable和HashMap都有默认的初始化大小,hashTable的默认大小是 11*0.75,hashMap的默认大小是16
    QQ截图20170215200405.png
    • HashTable 继承与Distionary类,使用Entry的数组存储数据,HashMap继承AbstractMap类,使用Entry数组存储数据,可以看到的是,两者的基础bean都是一样的,都包含hash、key、value、next,从数据结构来看,这里应该用到的就是拉链法,拉链法后面会进行详细介绍,简单来说,就是在冲突的时候,通过链表来处理冲突。
    2.png
    • HashTable操作entry数组的时候会使用JAVA的同步关键字,防止多线程的时候,entry数组溢出,而HashMap则无使用,HashTable是线程安全的,而HashMap不是
    Paste_Image.png

    JDK1.7使用了拉链法

    Paste_Image.png Paste_Image.png
    • 简单来说,拉链法就是数组里面的每一个元素都会作为一个链表的头结点,当通过put方法将数据放进哈希表时,哈希算法计算到的数组位置如果是相同的元素,会组建成链表,从而解决冲突。
    • 拉链法优化性能,都是通过扩大容量来减少冲突,为什么呢?因为每一条链表的长度都会缩短,通过哈希算法计算出数组位置一样的可能性降低了。
    void transfer(Entry[] newTable) {  
     Entry[] src = table;                   //src引用了旧的Entry数组  
     int newCapacity = newTable.length;  
     for (int j = 0; j < src.length; j++) { //遍历旧的Entry数组  
         Entry<K, V> e = src[j];             //取得旧Entry数组的每个元素  
         if (e != null) {  
             src[j] = null;//释放旧Entry数组的对象引用(for循环后,旧的Entry数组不再引用任何对象)  
             do {  
                 Entry<K, V> next = e.next;  
                 int i = indexFor(e.hash, newCapacity); //!!重新计算每个元素在数组中的位置  
                 e.next = newTable[i]; //标记[1]  
                 newTable[i] = e;      //将元素放在数组上 
                 e = next;             //访问下一个Entry链上的元素(访问链表的下一个元素,链表头结点就是newTable[i]) 
             } while (e != null);  
         }  
     }
    }
    

    HashTable是如何解决线程安全的?

    HashTable类的实例,对于不同线程的临界区是entry数组,不同线程之间对该数组进行插入、更新、删除操作可能会造成线程安全问题。由于entry数组里面有很多个元素,如果想对entry数组加synchronized关键字显然不可能,因为你不知道,每一个线程到底什么时候才会对哪个元素进行操作。HashTable使用了最简单的办法,那就是将数组作为一个整体,对于访问该数组的方法,基本上都加了synchronized关键字,。但由于这样锁的粒度会比较大,性能也就没有concurrentHashMap快了。

    相关文章

      网友评论

          本文标题:HashMap和HashTable源代码分析

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