关于java中的容器类别及常⻅容器

题⽬描述

1.java中常⽤的容器有哪些

2.Collection和Collections有什么区别？

• java.util.Collection是⼀个集合接⼝（集合类的⼀个顶级接⼝）。它提供了对集合对象进⾏基本操作的通⽤接⼝⽅法。Collection接⼝在Java类库中有很多具体的实现。Collection接⼝的意义是为各种具体的集合提供了最⼤化的统⼀操作⽅式，其直接继承接⼝有List与Set。
• Collections则是集合类的⼀个⼯具类/帮助类，其中提供了⼀系列静态⽅法，⽤于对集合中元素进⾏排序、搜索以及线程安全等各种操作。

3.说⼀下HashMap的实现原理？

HashMap概述：HashMap是基于哈希表的Map接⼝的⾮同步实现。此实现提供所有可选的映射操作，并允许使⽤null值和null键。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap的数据结构：在java编程语⾔中，最基本的结构就是两种，⼀个是数组，另外⼀个是模拟指针（引⽤），所有的数据结构都可以⽤这两个基本结构来构造的，HashMap也不例外。HashMap实际上是⼀个“链表散列”的数据结构，即数组和链表的结合体。

当我们往Hashmap中put元素时,⾸先根据key的hashcode重新计算hash值,根绝hash值得到这个元素在数组中的位置(下标),如果该数组在该位置上已经存放了其他元素,那么在这个位置上的元素将以链表的形式存放,新加⼊的放在链头,最先加⼊的放⼊链尾.如果数组中该位置没有元素,就直接将该元素放到数组的该位置上。

需要注意Jdk1.8中对HashMap的实现做了优化,当链表中的节点数据超过⼋个之后,该链表会转为红⿊树来提⾼查询效率,从原来的O(n)到O(logn)

4.ArrayList和LinkedList的区别是什么？

最明显的区别是ArrrayList底层的数据结构是数组，⽀持随机访问，⽽LinkedList的底层数据结构是双向循环链表，不⽀持随机访问。使⽤下标访问⼀个元素，ArrayList的时间复杂度是O(1)，⽽LinkedList是O(n)。

数据结构:HashMap

题目描述

HashMap的内部数据结构？

1.面试题分析

根据题目要求我们可以知道：

该题是一个数据结构问题，可以从HashMap的底层数据结构进行分析；

建议从多个不同jdk版本进行分析；

分析需要全面并且有深度

容易被忽略的坑

分析片面

没有深入

2.HashMap数据结构介绍

JDK1.8版本的，内部使用数组 + 链表红黑树

数据结构图：

HashMap的数据插入原理

原理图：

1. 判断数组是否为空，为空进行初始化;
2. 不为空，计算 k 的 hash 值，通过 (n - 1) & hash 计算应当存放在数组中的下标 index;
3. 查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；
4. 存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；
5. 如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)
6. 如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于 8并且数组长度大于64，大于的话链表转换为红黑树；
7. 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的二倍。

HashMap怎么设定初始容量大小？

一般如果 new HashMap() 不传值，默认大小是16，负载因子是0.75， 如果自己传入初始大小k，初始化大小为 大于k的 2的整数次方，例如如果传10，大小为16。（补充说明:实现代码如下）

static final int tableSizeFor(int cap) {
 int n = cap - 1;
 n |= n >>> 1;
 n |= n >>> 2;
 n |= n >>> 4;
 n |= n >>> 8;
 n |= n >>> 16;
 return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
123456789

补充说明：下图是详细过程，算法就是让初始二进制右移1，2，4，8，16位，分别与自己位或，把高位第一个为1的数通过不断右移，把高位为1的后面全变为1，最后再进行+1操作，111111 +1 = 1000000 = 26

（符合大于50并且是2的整数次幂 ）

HashMap的哈希函数设计

hash函数是先拿到 key 的hashcode，是一个32位的int值，然后让hashcode的高16位和低16位进行异或操作。

这么设计有二点原因：

1. 一定要尽可能降低hash碰撞，越分散越好；
2. 算法一定要尽可能高效，因为这是高频操作, 因此采用位运算；

为什么采用hashcode的高16位和低16位异或能降低hash碰撞？hash函数能不能直接用key的

hashcode？

因为key.hashCode()函数调用的是key键值类型自带的哈希函数，返回int型散列值。int值范围

为-2147483648~2147483647，前后加起来大概40亿的映射空间。只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个40亿长度的数组，内存是放不下的。你想，如果HashMap数组的初始大小才16，用之前需要对数组的长度取模运算，得到的余数才能用来访问数组下标。

源码中模运算就是把散列值和数组长度-1做一个"与"操作，位运算比取余%运算要快。

bucketIndex = indexFor(hash, table.length);
static int indexFor(int h, int length) {
  return h & (length-1);
}
12345

这也正好解释了为什么HashMap的数组长度要取2的整数幂。因为这样（数组长度-1）正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

  10100101 11000100 00100101
& 00000000 00000000 00001111
----------------------------------
  00000000 00000000 00000101   //高位全部归零，只保留末四位
1234

但这时候问题就来了，这样就算我的散列值分布再松散，要是只取最后几位的话，碰撞也会很严重。更要命的是如果散列本身做得不好，分布上成等差数列的漏洞，如果正好让最后几个低位呈现规律性重复。

此时“扰动函数”的价值就体现出来了，说到这里大家应该猜出来了。看下面这个图，

右移16位，正好是32bit的一半，自己的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征，这样高位的信息也被变相保留下来。

最后我们来看一下Peter Lawley的一篇专栏文章《An introduction to optimising a hashing

strategy》里的的一个实验：他随机选取了352个字符串，在他们散列值完全没有冲突的前提下，对它们做低位掩码，取数组下标。

结果显示，当HashMap数组长度为512的时候（29），也就是用掩码取低9位的时候，在没有扰动函数的情况下，发生了103次碰撞，接近30%。而在使用了扰动函数之后只有92次碰撞。碰撞减少了将近10%。看来扰动函数确实还是有功效的。

另外Java1.8相比1.7做了调整，1.7做了四次移位和四次异或，但明显Java 8觉得扰动做一次就够了，做4次的话，多了可能边际效用也不大，所谓为了效率考虑就改成一次了。

下面是1.7的hash代码：

static int hash(int h) {
  h ^= (h >>> 20) ^ (h >>> 12);
  return h ^ (h >>> 7) ^ (h >>> 4);
}
1234

1.8对hash函数做了优化，1.8还有别的优化？

1. 数组+链表改成了数组+链表或红黑树；
2. 链表的插入方式从头插法改成了尾插法，简单说就是插入时，如果数组位置上已经有元素，1.7将新元素放到数组中，原始节点作为新节点的后继节点，1.8遍历链表，将元素放置到链表的最后；
3. 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
4. 在插入时，1.7先判断是否需要扩容，再插入，1.8先进行插入，插入完成再判断是否需要扩容；

优化目的：

1. 防止发生hash冲突，链表长度过长，将时间复杂度由 O(n) 降为 O(logn) ;
2. 因为1.7头插法扩容时，头插法会使链表发生反转，多线程环境下会产生环；

A线程在插入节点B，B线程也在插入，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环，如下图所示：

1.7的扩容调用transfer代码，如下所示：

void transfer(Entry[] newTable, boolean rehash) {
 int newCapacity = newTable.length;
 for (Entry<K,V> e : table) {
  while(null != e) {
   Entry<K,V> next = e.next;
   if (rehash) {
    e.hash = null == e.key ? 0 : hash(e.key);
  }
   int i = indexFor(e.hash, newCapacity);
   e.next = newTable[i]; //A线程如果执行到这一行挂起，B线程开始进行扩容
   newTable[i] = e;
   e = next;
 }
}
}
12345678910111213141516

3. 扩容的时候为什么1.8 不用重新hash就可以直接定位原节点在新数据的位置呢?

这是由于扩容是扩大为原数组大小的2倍，用于计算数组位置的掩码仅仅只是高位多了一个1，怎么理解呢？

扩容前长度为16，用于计算(n-1) & hash 的二进制n-1为0000 1111，扩容为32后的二进制就高位多了1，为0001 1111。

因为是& 运算，1和任何数 & 都是它本身，那就分二种情况，如下图：原数据hashcode高位第4位为0和高位为1的情况；

第四位高位为0，重新hash数值不变，第四位为1，重新hash数值比原来大16（旧数组的容量）

那HashMap是线程安全的吗？

不是，在多线程环境下，1.7 会产生死循环、数据丢失、数据覆盖的问题，1.8 中会有数据覆盖的问题，以1.8为例，当A线程判断index位置为空后正好挂起，B线程开始往index位置的写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了；还有++size这个地方也会造成多线程同时扩容等问题。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
       boolean evict) {
 Node<K,V>[] tab; Node<K,V> p; int n, i;
 if ((tab = table) == null || (n = tab.length) == 0)
  n = (tab = resize()).length;
 if ((p = tab[i = (n - 1) & hash]) == null)  //多线程执行到这里
  tab[i] = newNode(hash, key, value, null);
 else {
  Node<K,V> e; K k;
  if (p.hash == hash &&
   ((k = p.key) == key || (key != null && key.equals(k))))
   e = p;
  else if (p instanceof TreeNode) // 这里很重要
   e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
  else {
   for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
     p.next = newNode(hash, key, value, null);
     if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
      treeifyBin(tab, hash);
     break;
   }
    if (e.hash == hash &&
     ((k = e.key) == key || (key != null && key.equals(k))))
     break;
    p = e;
  }
 }
  if (e != null) { // existing mapping for key
   V oldValue = e.value;
   if (!onlyIfAbsent || oldValue == null)
    e.value = value;
   afterNodeAccess(e);
   return oldValue;
 }
}
 ++modCount;
 if (++size > threshold) // 多个线程走到这，可能重复resize()
  resize();
 afterNodeInsertion(evict);
 return null;
}
123456789101112131415161718192021222324252627282930313233343536373839404142

怎么解决这个线程不安全的问题？

Java中有HashTable、Collections.synchronizedMap、以及ConcurrentHashMap可以实现线程安全的Map。

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大，

Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；ConcurrentHashMap使用分段锁，降低了锁粒度，让并发度大大提高。

3.扩展内容

• ConcurrentHashMap的分段锁的实现原理吗？
• 链表转红黑树是链表长度达到阈值，这个阈值是多少？为什么？
• HashMap内部节点是有序的吗？
• 讲讲LinkedHashMap怎么实现有序的？
• 讲讲TreeMap怎么实现有序的？
• 通过CAS 和 synchronized结合实现锁粒度的降低，讲讲CAS 的实现以及synchronized的实现原理吗？

HashMap底层原理

题目描述

HashMap的底层原理?

1. 面试题分析

HashMap是Java程序员使用频率最高的用于映射(键值对)处理的数据类型。随着JDK(Java

Developmet Kit)版本的更新,JDK1.8对HashMap底层的实现进行了优化,例如引入红黑

树的数据结构和扩容的优化等。本文结合JDK1.7和JDK1.8的区别,深入探讨HashMap的结构实现和功能原理。

2. 介绍

Java为数据结构中的映射定义了一个接口,此接口主要有四个常用的实现类,分别是 HashMap 、 Hashtable 、LinkedHashMap 和 TreeMap ,类继承关系如下图

所示:

1).HashMap :它根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。 HashMap 最多只允许一条记录的键为 null ,允许多条记录的值为 null 。

HashMap 非线程安全,即任一时刻可以有多个线程同时写 HashMap ,可能会导致数据的不一致。如果需要满足线程安全,可以用Collections 的 synchronizedMap 方法使HashMap 具有线程安全的能力,或者使用ConcurrentHashMap 。

2).Hashtable: Hashtable是遗留类,很多映射的常用功能与 HashMap 类似,不同的是它承自 Dictionary 类,并且是线程安全的,任一时间只有一个线程能写 Hashtable ,并发性不如

ConcurrentHashMap ,因为ConcurrentHashMap 引入了分段锁。

Hashtable 不建议在新代码中使用,不需要线程安全的场合可以用 HashMap 替换,需要线

程安全的场合可以用 ConcurrentHashMap 替换。

3). LinkedHashMap : LinkedHashMap 是HashMap 的一个子类,保存了记录的插入顺

序,在用 Iterator 遍历 LinkedHashMap 时,先得到的记录肯定是先插入的,也可以在构造

时带参数,按照访问次序排序。

4). TreeMap : TreeMap 实现 SortedMap 接口,能够把它保存的记录根据键排序,默认是按键

值的升序排序,也可以指定排序的比较器,当用 Iterator 遍历 TreeMap 时,得到的记录是

排过序的。如果使用排序的映射,建议使用TreeMap 。在使用 TreeMap 时, key 必须实现

Comparable 接口或者在构造 TreeMap 传入自定义的 Comparator ,否则会在运行时抛出

java.lang.ClassCastException 类型的异常。

3. 存储结构-字段(示意图+源码)

1.从结构实现来讲, HashMap 是数组 + 链表 + 红黑树( JDK1.8 增加了红黑树部分)实现的,

如下如所示。

a.从源码可知,HashMap类中有一个非常重要的字段,就是 Node[] table ,即哈希

桶数组,明显它是一个 Node 的数组。我们来看 Node[JDK1.8] 是何物

static class Node<K,V>
implements Map.Entry<K,V> {
       final int hash;    //用来定位数组索引位置
       final K key;
       V value;
       Node<K,V> next;   //链表的下一个node
       Node(int hash, K key, V value, Node<K,V> next) { ...}
       public final K getKey(){ ... }
       public final V getValue() { ... }
       public final String toString() { ... }
       public final int hashCode() { ... }
       public final V setValue(V newValue) { ... }
       public final boolean equals(Object o) { ... }
}

Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。上图中的每个黑色圆点就是一个Node对象。

b. HashMap就是使用哈希表来存储的。哈希表为解决冲突，可以采用开放地址法和链地址法等来解决问题，Java中HashMap采用了链地址法。链地址法，简单来说，就是数组加链表的结合。在每个数组元素上都一个链表结构，当数据被Hash后，得到数组下标，把数据放在对应下标元素的链表上。

例如程序执行下面代码：

map.put("name", "qixi");

系统将调用"name"这个key的hashCode()方法得到其hashCode 值（该方 法适用于每

个Java对象），然后再通过Hash算法的后两步运算（高位运 算和取模运算，下文有

介绍）来定位该键值对的存储位置，有时两个 key会定位到相同的位置，表示发生了

Hash碰撞。当然Hash算法计算结 果越分散均匀，Hash碰撞的概率就越小，map的存取

效率就会越高。

如果哈希桶数组很大，即使较差的Hash算法也会比较分散，如果哈希桶 数组数组

很小，即使好的Hash算法也会出现较多碰撞，所以就需要在空 间成本和时间成本

之间权衡，其实就是在根据实际情况确定哈希桶数组 的大小，并在此基础上设计好

的hash算法减少Hash碰撞。那么通过什么方式来控制map使得Hash碰撞的概率又小，

哈希桶数组（Node[] table） 占用空间又少呢？答案就是好的Hash算法和扩容机制。

在理解Hash和扩容流程之前，我们得先了解下HashMap的几个字段。 从HashMap的默认构造函数源码可知，构造函数就是对下面几个字段进 行初始化，源码

如下：

int threshold;      
// 所能容纳的key-value对极限
 final float loadFactor; 
// 负载因子
 int modCount; 
 int size;

首先，Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是

0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold =

length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键

值对个数越多。

结合负载因子的定义公式可知，threshold就是在此Load factor和length(数组长度)对应下允许的最大元素数目，超过这个数目就重新resize(扩容)，扩容后的HashMap容量是之前容量的两倍。默认的负载因子0.75是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子Load factor的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子loadFactor的值，这个值可以大于1。

size这个字段其实很好理解，就是HashMap中实际存在的键值对数量。注意和table的长度length、容纳最大键值对数量threshold的区别。而modCount字段主要用来记录HashMap

内部结构发生变化的次数，主要用于迭代的快速失败。强调一点，内部结构发生变化指的是结构发生变化，例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。

在HashMap中，哈希桶数组table的长度length大小必须为2的n次方(一定是合数)，这是一种非常规的设计，常规的设计是把桶的大小设计为素数。相对来说素数导致冲突的概率要小于合数，Hashtable初始化桶大小为11，就是桶大小设计为素数的应用（Hashtable扩容后不能保证还是素数）。HashMap采用这种非常规设计，主要是为了在取模和扩容时做优化，同时为了减少冲

突，HashMap定位哈希桶索引位置时，也加入了高位参与运算的过程。

这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。

4. 功能实现-方法

HashMap的内部功能实现很多，本文主要从根据key获取哈希桶数组索引位置、put方法

的详细执行、扩容过程三个具有代表性的点深入展开讲解。

1. 确定哈希桶数组索引位置不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。前面说过HashMap的数据结构是数组和链表的结合，所以我们当然希望这个HashMap里面的元素位置尽量分布均匀些，尽量使得每个位置上的元素数量只有一个，那么当我们用hash算法求得这个位置的时候，马上就可以知道对应位置的元素就是我们要的，不用遍

历链表，大大优化了查询的效率。HashMap定位数组索引位置，直接决定了hash方法的离散性能。先看看源码的实现(方法一+方法二):

// 法一：
static final int hash(Object key)
{  //jdk1.8 & jdk1.7
  int h;
  // h = key.hashCode() 为第一步 取hashCode值
  // h ^ (h >>> 16) 为第二步 高位参与运算
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
  return h & (length-1);  //第三步 取模运算
}

这里的Hash算法本质上就是三步：取key的hashCode值、高位运算、取模运算。

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的

Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的

分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙，它通过h & (table.length-1)来得到该对象的保存位，而HashMap底层数

组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现

的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

下面举例说明下，n为table的长度。

4. Change变形延伸

• hashmap的扩容

Hash冲突有什么解决方式

题目描述

Hash冲突有什么解决方式

面试题分析

先说出hash表的概念，再说出不同的解决方法，再之处各种方法的优缺点

一.哈希表简介

非哈希表的特点：关键字在表中的位置和它自检不存在一个确定的关系，查找的过程为给定值一次和各个关系自进行比较，查找的效率取决于给定值进行比较的次数。

哈希表的特点：关键字在表中位置和它自检存在一种确定的关系。

哈希函数：一般情况下，需要在关键字与它在表中的存储位置之间建立一个函数关系，以（key）作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数。

hash：翻译为”散列表“，就是把任意长度的输入，通过散列算法，变成固定长度输出，该输出结果是散列值。

这种转换是一种压缩映射，散列表的空间通常小鱼输入的空间，不同的输入可能会散列成相同的输出，所以不能从散列表来唯一的确定输入值。

简单的说就是一种将任意长度的消息压缩到固定长度的消息摘要函数。

hash冲突：就是根据key即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经有人先来了。就是说这个地方要挤一挤啦。这就是所谓的hash冲突啦

二.哈希函数处理冲突的方法

1）开放定址法：

这种方法也称再散列法，其基本思想是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。这种方法有一个通用的再散列函数形式：

Hi=（H（key）+di）% m i=1，2，…，n

其中H（key）为哈希函数，m 为表长，di称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下三种：

线性探测再散列

dii=1，2，3，…，m-1

这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。

二次探测再散列

di=12，-12，22，-22，…，k2，-k2 ( k<=m/2 )

这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。

伪随机探测再散列

di=伪随机数序列。

具体实现时，应建立一个伪随机数发生器，（如i=(i+p) % m），并给定一个随机数做起点。

例如，已知哈希表长度m=11，哈希函数为：H（key）= key % 11，则H（47）=3，H（26）=4，H（60）=5，假设下一个关键字为69，则H（69）=3，与47冲突。

如果用线性探测再散列处理冲突，下一个哈希地址为H1=（3 + 1）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 + 2）% 11 = 5，还是冲突，继续找下一个哈希地址为H3=（3 + 3）% 11 = 6，此时不再冲突，将69填入5号单元。

如果用二次探测再散列处理冲突，下一个哈希地址为H1=（3 + 12）% 11 = 4，仍然冲突，再找下一个哈希地址为H2=（3 - 12）% 11 = 2，此时不再冲突，将69填入2号单元。

如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，……..，则下一个哈希地址为H1=（3+ 2）% 11 = 5，仍然冲突，再找下一个哈希地址为H2=（3 + 5）% 11 = 8，此时不再冲突，将69填入8号单元。

2) 再哈希法

这种方法是同时构造多个不同的哈希函数：

Hi=RH1（key） i=1，2，…，k

当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3）链地址法

这种方法的基本思想是将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。

4）建立公共溢出区

这种方法的基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

优缺点

开放散列表（open hashing）/拉链法（针对桶链结构）

1）优点：①对于记录总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销） ②由于记录存储在结点中，而结点是动态分配，不会造成内存的浪费，所以尤其适合那种记录本身尺寸（size）很大的情况，因为此时指针的开销可以忽略不计了 ③删除记录时，比较方便，直接通过指针操作即可

2）缺点： ①存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销 ②如果所有的 key-value 对是可以提前预知，并之后不会发生变化时（即不允许插入和删除），可以人为创建一个不会产生冲突的完美哈希函数（perfect hash function），此时封闭散列的性能将远高于开放散列 ③由于使用指针，记录不容易进行序列化（serialize）操作

封闭散列（closed hashing）/ 开放定址法

1）优点： ①记录更容易进行序列化（serialize）操作 ②如果记录总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的

2）缺点： ①存储记录的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷 ②使用探测序列，有可能其计算的时间成本过高，导致哈希表的处理性能降低 ③由于记录是存放在桶数组中的，而桶数组必然存在空槽，所以当记录本身尺寸（size）很大并且记录总数规模很大时，空槽占用的空间会导致明显的内存浪费 ④删除记录时，比较麻烦。比如需要删除记录a，记录b是在a之后插入桶数组的，但是和记录a有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除a，a的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录b在a的位置重新插入数据前不可见，所以不能直接删除a，而是设置删除标记。这就需要额外的空间和操作。

HashMap为什么是线程不安全

解题思路分析

• 先从源码的实现进行分析

• 线程不安全是针对多线程而言，所以需要先来叙述下单线程情况

• 紧跟其后进行一个线程的叙述

HashMap的底层存储结构

HashMap底层是一个Entry数组，一旦发生Hash冲突的的时候，HashMap采用拉链法解决碰撞冲突，Entry内部的变量：

final Object key;
Object value;
Entry next;
int hash

通过Entry内部的next变量可以知道使用的是链表，这时候我们可以知道，如果多个线程，在某一时刻同时操作HashMap并执行put操作，而有大于两个key的hash值相同，如图中a1、a2，这个时候需要解决碰撞冲突，而解决冲突的办法上面已经说过，对于链表的结构在这里不再赘述，暂且不讨论是从链表头部插入还是从尾部初入，这个时候两个线程如果恰好都取到了对应位置的头结点e1，而最终的结果可想而知，a1、a2两个数据中势必会有一个会丢失。

HashMap中put方法

public Object put(Object obj, Object obj1) {
    if(table == EMPTY_TABLE) inflateTable(threshold);
    if(obj == null) return putForNullKey(obj1);
    int i = hash(obj);
    int j = indexFor(i, table.length);
    for(Entry entry = table[j]; entry != null; entry = entry.next) {
        Object obj2;
        if(entry.hash == i && ((obj2 = entry.key) == obj || obj.equals(obj2))) {
            Object obj3 = entry.value;
            entry.value = obj1;
            entry.recordAccess(this);
            return obj3;
        }
    }
    modCount++;
    addEntry(i, obj, obj1, j);
    return null;
}

put方法不是同步的，同时调用了addEntry方法：

void addEntry(int i, Object obj, Object obj1, int j) {
    if(size >= threshold && null != table[j]) {
        resize(2 * table.length);
        i = null == obj ? 0 : hash(obj);
        j = indexFor(i, table.length);
    }
    createEntry(i, obj, obj1, j);
}

addEntry方法依然不是同步的，所以导致了线程不安全出现伤处问题，其他类似操作不再说明，源码一看便知，下面主要说一下另一个非常重要的知识点，同样也是HashMap非线程安全的原因，我们知道在HashMap存在扩容的情况，对应的方法为HashMap中的resize方法：

HashMap中rezise()方法源码

final Node < K, V > [] resize() {
    Node < K, V > [] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if(oldCap > 0) {
        if(oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold
    } else if(oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {
        // 第一次插入值的时候，table=null,所以给数组进行初始化，设置容量，阈值
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if(newThr == 0) {
        float ft = (float) newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    @SuppressWarnings({
        "rawtypes",
        "unchecked"
    })
    Node < K, V > [] newTab = (Node < K, V > []) new Node[newCap];
    table = newTab;
    if(oldTab != null) {
        for(int j = 0; j < oldCap; ++j) {
            Node < K, V > e;
            if((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if(e.next == null) newTab[e.hash & (newCap - 1)] = e;
                else if(e instanceof TreeNode)
                    ((TreeNode < K, V > ) e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node < K, V > loHead = null, loTail = null;
                    Node < K, V > hiHead = null, hiTail = null;
                    Node < K, V > next;
                    do {
                        next = e.next;
                        //如果异或运算=0，则位置不变
                        if((e.hash & oldCap) == 0) {
                            if(loTail == null) loHead = e;
                            else loTail.next = e;
                            loTail = e;
                        } else {
                            if(hiTail == null) hiHead = e;
                            else hiTail.next = e;
                            hiTail = e;
                        }
                    } while((e = next) != null);
                    if(loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if(hiTail != null) {
                        hiTail.next = null;
                        //如果这个数据是在table[2]上，并且此时数组的容量是16.
                        //那么新的位置将变成new_index=2+16
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

HashMap初始容量大小为16,一般来说，当有数据要插入时，都会检查容量有没有超过设定的thredhold=负载因子*16，如果超过，需要增大Hash表的尺寸，但是这样一来，整个Hash表 里的元素都需要被重算一遍。这叫rehash，这个成本相当的大。

对索引数组中的元素for循环遍历：

对链表上的每一个节点遍历：用 next 取得要转移那个元素的下一个，将 e 转移到新 Hash 表的头部，使用头插法插入节点。

循环2，直到链表节点全部转移

循环1，直到所有索引数组全部转移

经过这几步，我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。

这时候就有点头绪了，死锁问题不就是因为1->2的同时2->1造成的吗？所以，HashMap 的死锁问题就出在这个for循环遍历。

单线程的rezise

• 假设hash算法就是最简单的 key mod table.length（也就是数组的长度）。

• 最上面的是old hash 表，其中的Hash表的 size = 2, 所以 key = 3, 7, 5，在 mod 2以后碰撞发生在table[1]

• 接下来的三个步骤是 Hash表 resize 到4，并将所有的 <key,value> 重新rehash到新 Hash 表的过程

多线程rezise

• 因为是单向链表，如果要转移头指针，一定要保存下一个结点，不然转移后链表就丢
• e 要插入到链表的头部，所以要先用 e.next 指向新的 Hash 表第一个元素（为什么不加到新链表最后？因为复杂度是 O（N））
• 现在新 Hash 表的头指针仍然指向 e 没转移前的第一个元素，所以需要将新 Hash 表的头指针指向e
• 转移 e 的下一个结点

现在的状态：

从上面的图我们可以看到，因为线程1的 e 指向了 key(3)，而 next 指向了 key(7)，在线程2 rehash后，就指向了线程2 rehash 后的链表。

然后线程1被唤醒了：

• 执行e.next = newTable[i]，于是 key(3)的 next 指向了线程1的新 Hash 表，因为新 Hash 表为空，所以e.next = null，

• 执行newTable[i] = e，所以线程1的新 Hash 表第一个元素指向了线程2新 Hash 表的 key(3)。好了，e 处理完毕。

• 执行e = next，将 e 指向 next，所以新的 e 是 key(7)

然后该执行 key(3)的 next 节点 key(7)了:

• 现在的 e 节点是 key(7)，首先执行Entry<K,V> next = e.next,那么 next 就是 key(3)了

• 执行e.next = newTable[i]，于是key(7) 的 next 就成了 key(3)

• 执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(7)

• 执行e = next，将 e 指向 next，所以新的 e 是 key(3)

这时候的状态

然后又该执行 key(7)的 next 节点 key(3)了：

• 现在的 e 节点是 key(3)，首先执行Entry<K,V> next = e.next,那么 next 就是 null

• 执行e.next = newTable[i]，于是key(3) 的 next 就成了 key(7)

• 执行newTable[i] = e，那么线程1的新 Hash 表第一个元素变成了 key(3)

• 执行e = next，将 e 指向 next，所以新的 e 是 key(7)

这时候状态为

很明显，环形链表出现了！！当然，现在还没有事情，因为下一个节点是 null，

所以就遍历完成了，等put()的其余过程搞定后，HashMap 的底层实现就是线程1的新 Hash 表了。

如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

使用建议

对有多线程应用的功能，或需要考虑线程安全的功能，建议使用ConcurrentHashMap 类来代替HashMap

总结

在并发执行put操作时会发生数据覆盖的情况。