HashMap、HashTable和HashSet

HashMap的实现机制，怎么样让HashMap线程安全

1、Java语言数据结构

在 Java 编程语言中，最基本的结构就是两种，一个是数组，另外一个是指针（引用），
HashMap 就是通过这两个数据结构进行实现。HashMap 就是通过这两个数据结构进行实现。HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。

2、HashMap数据结构示意图

2、HashMap构造函数

HashMap(int initialCapacity, float loadFactor)：以指定初始容量、指定的负载因子创建一个 HashMap。

1. loadFactor如果不指定，默认是0.75，
2. threshold = (int)(capacity * loadFactor);如果容量超过threshold（阈值），则会自动扩容为2*initialCapacity大小

3、Fail-Fast 机制

快速失败， 当多个线程对同一个集合的内容进行操作时，就可能会产生 fail-fast 事件。
会抛出ConcurrentModificationException异常。通过一个modeCount和迭代器的expectedModCount比较来判断是否进行了多线程的操作。如果不等，就会抛出ConcurrentModificationException异常。modCount 声明为 volatile，保证线程之间修改的可见性。

4、最佳实践

HashMap 的两种遍历方式：
1. 遍历entrySet

Map map = new HashMap();
　　Iterator iter = map.entrySet().iterator();
　　while (iter.hasNext()) {
　　Map.Entry entry = (Map.Entry) iter.next();
　　Object key = entry.getKey();
　　Object val = entry.getValue();
　　}
　　//效率高,要使用此种方式！

2.通过keyset遍历

Map map = new HashMap();
　　Iterator iter = map.keySet().iterator();
　　while (iter.hasNext()) {
　　Object key = iter.next();
　　Object val = map.get(key);
　　}
　　//效率低,以后尽量少使用！

5、如何让HashMap变得线程安全

我们都知道。HashMap是非线程安全的（非同步的）。那么怎么才能让HashMap变成线程安全的呢？

1. 替换成Hashtable，Hashtable通过对整个表上锁实现线程安全，因此效率比较低
2. 使用Collections类的synchronizedMap方法包装一下。方法如下：
   public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) 返回由指定映射支持的同步（线程安全的）映射
3. 使用ConcurrentHashMap，它使用分段锁来保证线程安全

6、HashMap和HashTable的区别

1. HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实 现，它以最大限度地减少实现此接口所需的工作。
2. HashMap 的 key 和 value 都允许为 null，而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候，调用 putForNullKey 方法进行处理，而对 value 没有处理；Hashtable遇到 null，直接返回 NullPointerException。
3. Hashtable 方法是同步，而HashMap则不是。

7、HashSet的实现机制

1. 对于 HashSet 而言，它是基于 HashMap 实现的，底层采用 HashMap 来保存元素
2. 对于 HashSet 中保存的对象，请注意正确重写其 equals 和 hashCode 方法，以保证放入的对象的唯一性。
3. HashSet是将要存入的值作为key，存入hashmap,PRESENT作为value。所有的value都是PRESENT。
4. HashSet可以存入一个null值

8、总结

简单地说，HashMap 在底层将 key-value 当成一个整体进行处理，这个整体就是一个 Entry 对象。HashMap 底层采用一个 Entry[] 数组来保存所有的 key-value 对，当需要存储一个 Entry 对象时，会根据 hash 算法来决定其在数组中的存储位置，如果数组的该位置上没有Entry,则直接添加，否则再根据 equals 方法决定其在该数组位置上的链表中的存储位置，如果equals找到了想同的key,则替换value的值，否则将新元素加入链表的头部；当需要取出一个Entry 时，也会根据 hash 算法找到其在数组中的存储位置，再根据 equals 方法从该位置上的链表中取出该Entry。