HashMap与HashTable的区别以及ConcurrentHashMap的一些底层原理剖析

太过爱你忘了你带给我的痛 2022-05-30 02:40 125阅读 0赞

**一 hashmap和hashtable的区别:**  
1.时间上:  
hashtable是JDK1.1的产物,hashmap是JDK1.2的产物,每个版本都在进化。  
2.公开的方法:  
下面这张图片画出了HashMap和HashTable的类继承体系,并列出了这两个类的可供外部调用的公开方法:  
![这里写图片描述][70]  
从上图中可以看出,两个类的继承体系有些不同。虽然都实现了Map,  
Cloneable(一个标记接口没有什么内容),Serializable三个接口。但是hashmap继承自抽象类AbstractMap,而hashtable继承自抽象类Dictionary。其中 Dictionary类是一个已经被废弃的类。面试的时候不会问这么深的。  
同时我们看到HashTable比HashMap多了两个公开方法。一个是elements，这来自于抽象类Dictionary，鉴于该类已经废弃，所以这个方法也就没什么用处了。另一个多出来的方法是contains，这个多出来的方法也没什么用，因为它跟containsValue方法功能是一样的。

**总结:**  
说了这么多,当你面试的时候怎么说呢?  
1.从实现结构上就是hashtable是单纯的链表数据结构,对应的就是查询效率低,增删快。而hashmap是一种数组与链表兼容的数据结构,相应的数组数据结构查询效率高,增删慢,同时又要引出下面一个问题:  
2.对应的线程安全方面就是速度快线程不安全,速度慢线程安全,为什么这么说呢?速度快的是因为没有加线程锁(synchronized),加入之后就要拿到锁标记的线程才能执行操作,一次这就像是一个过独木桥排队的例子,但是随着技术的不断升级,出现了多个独木桥同时通过原理的ConCurrentHashMap这种设计结构,等下会详细的说明。  
3.HashMap是支持null键和null值的，而HashTable在遇到null时，会抛出NullPointerException异常。这并不是因为HashTable有什么特殊的实现层面的原因导致不能支持null键和null值，这仅仅是因为HashMap在实现时对null做了特殊处理，将null的hashCode值定为了0，从而将其存放在哈希表的第0个bucket中。  
**二 面试只说这些还是不行的,你只是知道了基本理论,下面说一下hashmap的底层实现原理:**  
“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。”这里关键点在于指出，HashMap是在bucket中储存键对象和值对象，作为Map.Entry。这一点有助于理解获取对象的逻辑。如果你没有意识到这一点，或者错误的认为仅仅只在bucket中存储值的话，你将不会回答如何从HashMap中获取对象的逻辑。这个答案相当的正确，也显示出面试者确实知道hashing以及HashMap的工作原理。但是这仅仅是故事的开始,下个问题可能是关于HashMap中的碰撞探测(collision detection)以及碰撞的解决方法：

“当两个对象的hashcode相同会发生什么？” 从这里开始，真正的困惑开始了，一些人会回答因为hashcode相同，所以两个对象是相等的，HashMap将会抛出异常，或者不会存储它们。然后面试官可能会提醒他们有equals()和hashCode()两个方法，并告诉他们两个对象就算hashcode相同，但是它们可能并不相等。一些人可能就此放弃，而另外一些还能继续挺进，他们回答“因为hashcode相同，所以它们的bucket位置相同，‘碰撞’会发生。因为HashMap使用链表存储对象，这个Entry(包含有键值对的Map.Entry对象)会存储在链表中。”这个答案非常的合理，虽然有很多种处理碰撞的方法，这种方法是最简单的，也正是HashMap的处理方法。但故事还没有完结，面试官会继续问：

“如果两个键的hashcode相同，你如何获取值对象？” 面试者会回答：当我们调用get()方法，HashMap会使用键对象的hashcode找到bucket位置，然后获取值对象。面试官提醒他如果有两个值对象储存在同一个bucket，他给出答案:将会遍历链表直到找到值对象。面试官会问因为你并没有值对象去比较，你是如何确定确定找到值对象的？除非面试者直到HashMap在链表中存储的是键值对，否则他们不可能回答出这一题。

其中一些记得这个重要知识点的面试者会说，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点，最终找到要找的值对象。完美的答案！

许多情况下，面试者会在这个环节中出错，因为他们混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现，而equals()方法仅仅在获取值对象的时候才出现。一些优秀的开发者会指出使用不可变的、声明作final的对象，并且采用合适的equals()和hashCode()方法的话，将会减少碰撞的发生，提高效率。不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String，Interger这样的wrapper类作为键是非常好的选择。

如果你认为到这里已经完结了，那么听到下面这个问题的时候，你会大吃一惊。“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”除非你真正知道HashMap的工作原理，否则你将回答不出这道题。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

如果你能够回答这道问题，下面的问题来了：“你了解重新调整HashMap大小存在什么问题吗？”你可能回答不上来，这时面试官会提醒你当多线程的情况下，可能产生条件竞争(race condition)。

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？：）哈哈  
当然到这还是没有结束,因为还有一个重要的知识点就是默认的HashMap的默认初始容量是16,达到负载因子时增加为原来的2倍,具体是怎么实现的我就不太清楚了,百度上有。哈哈…  
**三 HashTable的底层实现原理:**

实际其底层实现原理和hashmap的实现原理大同小异,主要不同的地方是当达到负载因子时,初始容量扩大为原来的2倍+1,具体的内部实现细节只能在网上看了。哈哈….

**四 极其重要的ConCurrentHashMap**

数据结构CnCurrentHashMap的目标是实现支持高并发,高吞吐量的线程安全的HashMap。当然不能直接对整个hashmap加锁,所以在ConCurrentHashMap中,数据的组织结构和HashMap有所区别。  
一个ConCurrentHashMap由多个segment组成,每一个segment都包含了一个HashEntry数组的hashtable,每一个segment包含了对自己hashtable的操作,比如get,put,replace操作等,这些操作进行的时候,对自己的hashtable进行锁定,由于每一个segment写操作只锁定自己的hashtable,所以可能存在多个线程同时写的情况。性能无疑要优于一个hashtable锁定的情况。  
源码分析在ConCurrentHashMap的remove,put操作还是比较简单的,都是将remove或者put操作交给key所对应的segment去做,所以当几个操作不在同一个segment的时候可以并发的进行。

public V remove(Object key){
            int hash = hash(key.hashcode());
            return segmentFor(hash).remove(key)
    }

而segment中的remove操作除了加锁之外和HashMap中的remove操作几乎一样。

[70]: /images/20220530/ef25420a4cec40179f65150493d87e8d.png