--- title: 'HashMap、HashSet、Hashtable的区别' pubDate: 2018-05-07 tags: - '面试' description: 'HashMap、HashSet、Hashtable的区别' --- **_突然发现整理了很多笔记，应该放这里做备用_** ## Hashtable和HashMap **主要区别：线程安全性，同步(synchronization)，以及速度。** HashMap几乎可以等价于Hashtable，除了HashMap是非synchronized的，并可以接受null。Hashtable是线程安全的，多个线程可以共享一个Hashtable。 HashMap的同步问题可通过Collections的一个静态方法得到解决，`Map Collections.synchronizedMap(Map m)` 返回一个同步的Map。 HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。fail-fast结构上更改时（删除或者插入一个元素），将会抛出ConcurrentModificationException异常。 HashMap不能保证随着时间的推移Map中的元素次序是不变的。 ## HashSet和HashMap的区别 HashSet实现了Set接口，它不允许集合中有重复的值，当我们提到HashSet时，第一件事情就是在将对象存储在HashSet之前，要**先确保对象重写equals()和hashCode()方法**，这样才能比较对象的值是否相等，以确保set中没有储存相等的对象。如果我们没有重写这两个方法，将会使用这个方法的默认实现。 Map中不允许重复的键。Map接口有两个基本的实现，HashMap和TreeMap。TreeMap保存了对象的排列次序，而HashMap则不能。HashMap允许键和值为null。 HashSet 和 HashMap 之间有很多相似之处，对于 HashSet 而言，系统采用 Hash 算法决定集合元素的存储位置，这样可以保证能快速存、取集合元素；对于 HashMap 而言，系统 key-value 当成一个整体进行处理，系统总是根据 Hash 算法来计算 key-value 的存储位置，这样可以保证能快速存、取 Map 的 key-value 对。 ## HashMap ```java public V put(K key, V value) { // 如果 key 为 null，调用 putForNullKey 方法进行处理 if (key == null) return putForNullKey(value); // 根据 key 的 keyCode 计算 Hash 值 int hash = hash(key.hashCode()); // 搜索指定 hash 值在对应 table 中的索引 int i = indexFor(hash, table.length); // 如果 i 索引处的 Entry 不为 null，通过循环不断遍历 e 元素的下一个元素 for (Entry e = table[i]; e != null; e = e.next) { Object k; // 找到指定 key 与需要放入的 key 相等（hash 值相同 // 通过 equals 比较放回 true） if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry modCount++; // 将 key、value 添加到 i 索引处 addEntry(hash, key, value, i); return null; } ``` Map.Entry，每个 Map.Entry 其实就是一个 key-value 对。 当系统决定存储 HashMap 中的 key-value 对时，完全没有考虑 Entry 中的 value，仅仅只是根据 key 来计算并决定每个 Entry 的存储位置。可以把 Map 集合中的 value 当成 key 的附属。 indexFor(int h, int length) 方法来计算该对象应该保存在 table 数组的哪个索引处。 根据上面 put 方法的源代码可以看出，当程序试图将一个 key-value 对放入 HashMap 中时，程序首先根据该 key 的 hashCode() 返回值决定该 Entry 的存储位置：如果两个 Entry 的 key 的 hashCode() 返回值相同，那它们的存储位置相同。如果这两个 Entry 的 key 通过 equals 比较返回 true，新添加 Entry 的 value 将覆盖集合中原有 Entry 的 value，但 key 不会覆盖。如果这两个 Entry 的 key 通过 equals 比较返回 false，新添加的 Entry 将与集合中原有 Entry 形成 Entry 链，而且新添加的 Entry 位于 Entry 链的头部。 Map提供了一些常用方法，如keySet()、entrySet()等方法，keySet()方法返回值是Map中key值的集合；entrySet()的返回值也是返回一个Set集合，此集合的类型为Map.Entry，接口中有getKey()、getValue方法。 ### 内部实现 HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结构，但是在jdk1.8里 ，加入了红黑树的实现，当链表的长度大于8时，转换为红黑树的结构。 ![](https://source.mkshell.com/15256749922452.jpg) 少于8个的时候，Java中HashMap采用了链地址法。 通过什么方式来控制map使得Hash碰撞的概率又小，哈希桶数组（Node\[\] table）占用空间又少呢？答案就是好的Hash算法和扩容机制。即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。 而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能。 indexFor方法一般想到的是把hash值对数组长度取模运算，但运算较大，因此1.7中使用以下方法，&比%具有更高的效率： ```java static int indexFor(int h, int length) { return h & (length-1); //第三步 取模运算 } ``` 在JDK1.8的实现中，优化了高位运算的算法：`(h = k.hashCode()) ^ (h >>> 16)` ### 红黑树 红黑树（Red Black Tree） 是一种自平衡二叉查找树。红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。 ## equals()和hashCode() 两个obj，如果equals()相等，hashCode()一定相等。 两个obj，如果hashCode()相等，equals()不一定相等（Hash散列值有冲突的情况，虽然概率很低）。 equals()和hashcode()这两个方法都是从object类中继承过来的。equals()是对两个对象的地址值进行的比较（即比较引用是否相同），hashCode()是一个本地方法，它的实现是根据本地机器相关的。 ### hashCode()在new的用途 JVM每new一个Object,它都会将这个Object丢到一个Hash哈希表中去,这样的话,下次做Object的比较或者取这个对象的时候,它会根据对象的hashcode再从Hash表中取这个对象。这样做的目的是提高取对象的效率。 如果不同的对象确产生了相同的hash值,也就是发生了Hash key相同导致冲突的情况,那么就在这个Hash key的地方产生一个链表,将所有产生相同hashcode的对象放到这个单链表上去,串在一起。比较两个对象的时候,首先根据他们的hashcode去hash表中找他的对象，当两个对象的hashcode相同，只能根据Object的equal方法来比较这个对象是否equal。 ### 重写equals()的原因 Object的equal方法默认是两个对象的引用的比较，意思就是指向同一内存。 但是，String对象中equals方法是判断值的，而==是地址判断（因为JDK重写了）。 我们很大部分时间都是进行两个对象的比较（而不是比较引用），这个时候Object的equals()方法就不可以了，所以才会有String这些类对equals方法的改写，依次类推Double、Integer、Math等等这些类都是重写了equals()方法的，从而进行的是内容的比较。 ### 重写equals()后要重写hashCode()的理由 java.lnag.Object中对hashCode的约定： 1. 在一个应用程序执行期间，如果一个对象的equals方法做比较所用到的信息没有被修改的话，则对该对象调用hashCode方法多次，它必须始终如一地返回同一个整数。 2. 如果两个对象根据equals(Object o)方法是相等的，则调用这两个对象中任一对象的hashCode方法必须产生相同的整数结果。 3. 如果两个对象根据equals(Object o)方法是不相等的，则调用这两个对象中任一个对象的hashCode方法，不要求产生不同的整数结果。但如果能不同，则可能提高散列表的性能。 只要改写了就会违约，所以要继续改写。 ## Hashtable与ConcurrentHashMap区别 ConcurrentHashMap融合了hashtable和hashmap二者的优势。hashmap在单线程情况下效率较高；hashtable在的多线程情况下，同步操作能保证程序执行的正确性。 hashtable每次同步执行的时候都要锁住整个结构： ![](https://source.mkshell.com/15256750113128.jpg) ConcurrentHashMap锁的方式是稍微细粒度的。 更令人惊讶的是ConcurrentHashMap的读取并发，因为在读取的大多数时候都没有用到锁定，所以读取操作几乎是完全的并发操作，而写操作锁定的粒度又非常细，比起之前又更加快速（这一点在桶更多时表现得更明显些）。**只有在求size等操作时才需要锁定整个表。** 在迭代时，使用**弱一致迭代器**，不再是抛出 ConcurrentModificationException，在改变时new新的数据从而不影响原有的数据，iterator完成后再将头指针替换为新的数据。 ## 常见问题 ### HashMap的工作原理，HashMap的get()方法的工作原理 答：“HashMap是基于hashing的原理，我们使用put(key, value)存储对象到HashMap中，使用get(key)从HashMap中获取对象。当我们给put()方法传递键和值时，我们先对键调用hashCode()方法，返回的hashCode用于找到bucket位置来储存Entry对象。” 关键：HashMap是在bucket中储存键对象和值对象，作为Map.Entry。 ### 当两个对象的hashcode相同会发生什么 因为hashcode相同，所以它们的bucket位置相同，发生冲突，Entry(包含有键值对的Map.Entry对象)会存储在链表中。 ### hashcode相同如何获取值对象 遍历链表直到找到Entry对象，找到bucket位置之后，会调用keys.equals()方法去找到链表中正确的节点。 ### 超过了负载因子(load factor)定义的容量 默认的负载因子大小为0.75，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小（rehashing）。当多线程的情况下，可能产生条件竞争(race condition)，两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。 _先这样吧_ 若有错误之处请指出，更多地关注[煎鱼](http://www.jianyujianyu.com)。