HashMap相关题目

JAVA基础

1.hashMap线程安全吗？

• 不安全

2.怎样达到线程安全？

• 可以使用Collections的方法synchronizedMap方法进行同步
• 使用concurrentHashMap

3.hashMap的数据结构？

• jdk1.7 数组（位桶）+链表
• jdk1.8 数组（位桶）+链表+红黑树

4.hashMap扩容方式？

• 当添加的key位桶数值超过闸值（初始化容量16*负载因子）的时候，进行扩容，扩容时是当前容量翻倍即:capacity*2，然后把旧值放入新的hashMap中，所以扩容的代价是巨大的。所以如果知道hashMap的大概大小，最好给它设定一个合适的初始容量。

为什么不是数组用完的时候扩容？

减小hash碰撞的几率，若数组越大，则hash碰撞的几率越低，所以要控制负载值比数组的长度小。 

5.hashMap怎样去重。(如何处理冲突的？)

• 先对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸，然后根据新的hash值找到对应的桶位置i。
• 如果桶内没有元素，就直接添加；
• 如果已经有元素，则遍历table[i]位置的链表，查找相同的key，若找到则使用新的value替换掉原来的oldValue并返回oldValue；若没有在table[i]位置找到相同的key，则添加key到table[i]位置，新的元素总是在table[i]位置的第一个元素，原来的元素后移。
  ps:hash值不相等，不代表不会放在同一个位置。

6.如果key中放的是Object值，该怎么做？

• 重写hashCode和equals方法。
• 如果别人知道怎么实现的，故意构造相同的hash的字符串进行攻击，怎么处理？
  
  • jdk1.8中如何处理？
    
    • 当链表长度超过TREEIFY_THRESHOLD-1的时候，转换为红黑树
      
      • 此时他的查找时间复杂度为O(logN)而不再是O(N)
  • jdk1.7中如何处理？
    
    • 我们可以自己实现先对字符串进行封装再计算hash值
      或者用一个动态的treeMap来处理

8.如何去重后还能有序？

• 使用linkedHashMap或者TreeMap。

9.与Hashtable有什么区别？

• 1.两者最主要的区别在于Hashtable是线程安全，而HashMap则非线程安全
  Hashtable的实现方法里面都添加了synchronized关键字来确保线程同步，因此相对而言HashMap性能会高一些，我们平时使用时若无特殊需求建议使用HashMap，在多线程环境下若使用HashMap需要使用Collections.synchronizedMap()方法来获取一个线程安全的集合（Collections.synchronizedMap()实现原理是Collections定义了一个SynchronizedMap的内部类，这个类实现了Map接口，在调用方法时使用synchronized来保证线程同步,当然了实际上操作的还是我们传入的HashMap实例，简单的说就是Collections.synchronizedMap()方法帮我们在操作HashMap时自动添加了synchronized来实现线程同步，类似的其它Collections.synchronizedXX方法也是类似原理）
• 2.HashMap可以使用null作为key，而Hashtable则不允许null作为key
  虽说HashMap支持null值作为key，不过建议还是尽量避免这样使用，因为一旦不小心使用了，若因此引发一些问题，排查起来很是费事
• 3.HashMap以null作为key时，总是存储在table数组的第一个节点上
• 4.HashMap是继承自AbstractMap，HashTable和继承Dictionary抽象类
  都实现了map接口
• 5.HashMap的初始容量为16，Hashtable初始容量为11，两者的填充因子默认都是0.75
  HashMap扩容时是当前容量翻倍即:capacity*2，Hashtable扩容时是容量翻倍+1即:capacity*2+1

• 6.两者计算hash的方法不同
  Hashtable计算hash是直接使用key的hashcode对table数组的长度直接进行取模

  int hash = key.hashCode();
  int index = (hash & 0x7FFFFFFF) % tab.length;

  而HashMap计算hash对key的hashcode进行了二次hash，以获得更好的散列值，然后对table数组长度取摸

• 7.HashMap和Hashtable的底层实现都是数组+链表结构实现
• 8.HashMap的迭代器(Iterator)是fail-fast迭代器，而Hashtable的enumerator迭代器不是fail-fast的。
  所以当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException，但迭代器本身的remove()方法移除元素则不会抛出ConcurrentModificationException异常。
  HashMap可以通过下面的语句进行同步：
  Map m = Collections.synchronizeMap(hashMap);

补充：
9.Hashtable 有一个contains方法，容易引起误会，所以在HashMap里面已经去掉了
当然，2个类都用containsKey和containsValue方法。

哈希值的使用不同，HashTable直接使用对象的hashCode。而HashMap重新计算hash值。

Hashtable和HashMap它们两个内部实现方式的数组的初始大小和扩容的方式。HashTable中hash数组默认大小是11，增加的方式是 old*2+1。HashMap中hash数组的默认大小是16，而且一定是2的指数。

10.快速失败(fail-fast)和安全失败(fail-safe)的区别是什么？

java.util包下面的所有的集合类都是快速失败的，而java.util.concurrent包下面的所有的类都是安全失败的。快速失败的迭代器会抛出ConcurrentModificationException异常，而安全失败的迭代器永远不会抛出这样的异常
Iterator的安全失败是基于对底层集合做拷贝，因此，它不受源集合上修改的影响。
fail-fast解决办法
一.使用ConcurrentHashMap来替换HashMap,
使用CopyOnWriteArrayList来替换ArrayList
ArrayList 的一个线程安全的变体，其中所有可变操作（add、set 等等）都是通过对底层数组进行一次新的复制来实现的。 该类产生的开销比较大，但是在两种情况下，它非常适合使用。
1：在不能或不想进行同步遍历，但又需要从并发线程中排除冲突时。
2：当遍历操作的数量大大超过可变操作的数量时。
二、调用Collections.synchronizedXXX方法
如：synchronizedMap该方法返回的是一个SynchronizedMap的实例。
SynchronizedMap类是定义在Collections中的一个静态内部类。它实现了Map接口，通过synchronized关键字进行对Map的每个方法进行同步控制。