面试之HashMap与HashTable

布满荆棘的人生 2023-09-28 23:17 2阅读 0赞

HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用concurrent并发包下的concurrentHashMap。

HashMap 实现了Serializable接口，因此它支持序列化，实现了Cloneable接口，能被克隆。

HashMap存数据的过程是：

HashMap内部维护了一个存储数据的Entry数组，HashMap采用链表解决冲突，每一个Entry本质上是一个单向链表。当准备添加一个key-value对时，首先通过hash(key)方法计算hash值，然后通过indexFor(hash,length)求该key-value对的存储位置，计算方法是先用hash&0x7FFFFFFF后，再对length取模，这就保证每一个key-value对都能存入HashMap中，当计算出的位置相同时，由于存入位置是一个链表，则把这个key-value对插入链表头。

HashMap中key和value都允许为null。key为null的键值对永远都放在以table\[0\]为头结点的链表中。

了解了数据的存储，那么数据的读取也就很容易就明白了。

HashMap的存储结构，如下图所示：

![78633fc9b89e059dd31d4a876f60c444.png][]

图中，紫色部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。

HashMap内存储数据的Entry数组默认是16，如果没有对Entry扩容机制的话，当存储的数据一多，Entry内部的链表会很长，这就失去了HashMap的存储意义了。所以HasnMap内部有自己的扩容机制。HashMap内部有：

变量size，它记录HashMap的底层数组中已用槽的数量；

变量threshold，它是HashMap的阈值，用于判断是否需要调整HashMap的容量（threshold = 容量\*加载因子）

变量DEFAULT\_LOAD\_FACTOR = 0.75f，默认加载因子为0.75

HashMap扩容的条件是：当size大于threshold时，对HashMap进行扩容

扩容是是新建了一个HashMap的底层数组，而后调用transfer方法，将就HashMap的全部元素添加到新的HashMap中（要重新计算元素在新的数组中的索引位置）。 很明显，扩容是一个相当耗时的操作，因为它需要重新计算这些元素在新的数组中的位置并进行复制处理。因此，我们在用HashMap的时，最好能提前预估下HashMap中元素的个数，这样有助于提高HashMap的性能。

HashMap共有四个构造方法。构造方法中提到了两个很重要的参数：初始容量和加载因子。这两个参数是影响HashMap性能的重要参数，其中容量表示哈希表中槽的数量（即哈希数组的长度），初始容量是创建哈希表时的容量（从构造函数中可以看出，如果不指明，则默认为16），加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 resize 操作（即扩容）。

下面说下加载因子，如果加载因子越大，对空间的利用更充分，但是查找效率会降低（链表长度会越来越长）；如果加载因子太小，那么表中的数据将过于稀疏（很多空间还没用，就开始扩容了），对空间造成严重浪费。如果我们在构造方法中不指定，则系统默认加载因子为0.75，这是一个比较理想的值，一般情况下我们是无需修改的。

另外，无论我们指定的容量为多少，构造方法都会将实际容量设为不小于指定容量的2的次方的一个数，且最大值不能超过2的30次方。

Hashtable同样是基于哈希表实现的，同样每个元素是一个key-value对，其内部也是通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增长。

Hashtable也是JDK1.0引入的类，是线程安全的，能用于多线程环境中。

Hashtable同样实现了Serializable接口，它支持序列化，实现了Cloneable接口，能被克隆。

## HashTable和HashMap区别 ##

###  1、继承的父类不同 ###

Hashtable继承自Dictionary类，而HashMap继承自AbstractMap类。但二者都实现了Map接口。

###  2、线程安全性不同 ###

javadoc中关于hashmap的一段描述如下：此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。

Hashtable 中的方法是Synchronize的，而HashMap中的方法在缺省情况下是非Synchronize的。在多线程并发的环境下，可以直接使用Hashtable，不需要自己为它的方法实现同步，但使用HashMap时就必须要自己增加同步处理。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 [Collections.synchronizedMap][] 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

Map m = Collections.synchronizedMap(new HashMap(...));

Hashtable 线程安全很好理解，因为它每个方法中都加入了Synchronize。这里我们分析一下HashMap为什么是线程不安全的：

HashMap底层是一个Entry数组，当发生hash冲突的时候，hashmap是采用链表的方式来解决的，在对应的数组位置存放链表的头结点。对链表而言，新加入的节点会从头结点加入。

我们来分析一下多线程访问：

（1）在hashmap做put操作的时候会调用下面方法：

1.  // 新增Entry。将“key-value”插入指定位置，bucketIndex是位置索引。
2.  void addEntry(int hash, K key, V value, int bucketIndex) \{
3.  // 保存“bucketIndex”位置的值到“e”中
4.  Entry<K,V> e = table\[bucketIndex\];
5.  // 设置“bucketIndex”位置的元素为“新Entry”，
6.  // 设置“e”为“新Entry的下一个节点”
7.  table\[bucketIndex\] = new Entry<K,V>(hash, key, value, e);
8.  // 若HashMap的实际大小 不小于 “阈值”，则调整HashMap的大小
9.  if (size++ >= threshold)
10. resize(2 \* table.length);
11. \}

在hashmap做put操作的时候会调用到以上的方法。现在假如A线程和B线程同时对同一个数组位置调用addEntry，两个线程会同时得到现在的头结点，然后A写入新的头结点之后，B也写入新的头结点，那B的写入操作就会覆盖A的写入操作造成A的写入操作丢失

（2）删除键值对的代码

1.  <span style="font-size: 18px;"> </span>// 删除“键为key”的元素
2.  final Entry<K,V> removeEntryForKey(Object key) \{
3.  // 获取哈希值。若key为null，则哈希值为0；否则调用hash()进行计算
4.  int hash = (key == null) ? 0 : hash(key.hashCode());
5.  int i = indexFor(hash, table.length);
6.  Entry<K,V> prev = table\[i\];
7.  Entry<K,V> e = prev;
8.  
9.  // 删除链表中“键为key”的元素
10. // 本质是“删除单向链表中的节点”
11. while (e != null) \{
12. Entry<K,V> next = e.next;
13. Object k;
14. if (e.hash == hash &&
15. ((k = e.key) == key || (key != null && key.equals(k)))) \{
16. modCount++;
17. size--;
18. if (prev == e)
19. table\[i\] = next;
20. else
21. prev.next = next;
22. e.recordRemoval(this);
23. return e;
24. \}
25. prev = e;
26. e = next;
27. \}
28. 
29. return e;
30. \}

当多个线程同时操作同一个数组位置的时候，也都会先取得现在状态下该位置存储的头结点，然后各自去进行计算操作，之后再把结果写会到该数组位置去，其实写回的时候可能其他的线程已经就把这个位置给修改过了，就会覆盖其他线程的修改

（3）addEntry中当加入新的键值对后键值对总数量超过门限值的时候会调用一个resize操作，代码如下：

1.  // 重新调整HashMap的大小，newCapacity是调整后的容量
2.  void resize(int newCapacity) \{
3.  Entry\[\] oldTable = table;
4.  int oldCapacity = oldTable.length;
5.  //如果就容量已经达到了最大值，则不能再扩容，直接返回
6.  if (oldCapacity == MAXIMUM\_CAPACITY) \{
7.  threshold = Integer.MAX\_VALUE;
8.  return;
9.  \}
10. 
11. // 新建一个HashMap，将“旧HashMap”的全部元素添加到“新HashMap”中，
12. // 然后，将“新HashMap”赋值给“旧HashMap”。
13. Entry\[\] newTable = new Entry\[newCapacity\];
14. transfer(newTable);
15. table = newTable;
16. threshold = (int)(newCapacity \* loadFactor);
17. \}

这个操作会新生成一个新的容量的数组，然后对原数组的所有键值对重新进行计算和写入新的数组，之后指向新生成的数组。

当多个线程同时检测到总数量超过门限值的时候就会同时调用resize操作，各自生成新的数组并rehash后赋给该map底层的数组table，结果最终只有最后一个线程生成的新数组被赋给table变量，其他线程的均会丢失。而且当某些线程已经完成赋值而其他线程刚开始的时候，就会用已经被赋值的table作为原始数组，这样也会有问题。

###  3、是否提供contains方法 ###

HashMap把Hashtable的contains方法去掉了，改成containsValue和containsKey，因为contains方法容易让人引起误解。

Hashtable则保留了contains，containsValue和containsKey三个方法，其中contains和containsValue功能相同。

我们看一下Hashtable的ContainsKey方法和ContainsValue的源码：

1.  public boolean containsValue(Object value) \{
2.  return contains(value);
3.  \}

1.  // 判断Hashtable是否包含“值(value)”
2.  public synchronized boolean contains(Object value) \{
3.  //注意，Hashtable中的value不能是null，
4.  // 若是null的话，抛出异常!
5.  if (value == null) \{
6.  throw new NullPointerException();
7.  \}
8.  
9.  // 从后向前遍历table数组中的元素(Entry)
10. // 对于每个Entry(单向链表)，逐个遍历，判断节点的值是否等于value
11. Entry tab\[\] = table;
12. for (int i = tab.length ; i-- > 0 ;) \{
13. for (Entry<K,V> e = tab\[i\] ; e != null ; e = e.next) \{
14. if (e.value.equals(value)) \{
15. return true;
16. \}
17. \}
18. \}
19. return false;
20. \}

1.  // 判断Hashtable是否包含key
2.  public synchronized boolean containsKey(Object key) \{
3.  Entry tab\[\] = table;
4.  /计算hash值，直接用key的hashCode代替
5.  int hash = key.hashCode();
6.  // 计算在数组中的索引值
7.  int index = (hash & 0x7FFFFFFF) % tab.length;
8.  // 找到“key对应的Entry(链表)”，然后在链表中找出“哈希值”和“键值”与key都相等的元素
9.  for (Entry<K,V> e = tab\[index\] ; e != null ; e = e.next) \{
10. if ((e.hash == hash) && e.key.equals(key)) \{
11. return true;
12. \}
13. \}
14. return false;
15. \}

下面我们看一下HashMap的ContainsKey方法和ContainsValue的源码：

1.  // HashMap是否包含key
2.  public boolean containsKey(Object key) \{
3.  return getEntry(key) != null;
4.  \}

1.  // 返回“键为key”的键值对
2.  final Entry<K,V> getEntry(Object key) \{
3.  // 获取哈希值
4.  // HashMap将“key为null”的元素存储在table\[0\]位置，“key不为null”的则调用hash()计算哈希值
5.  int hash = (key == null) ? 0 : hash(key.hashCode());
6.  // 在“该hash值对应的链表”上查找“键值等于key”的元素
7.  for (Entry<K,V> e = table\[indexFor(hash, table.length)\];
8.  e != null;
9.  e = e.next) \{
10. Object k;
11. if (e.hash == hash &&
12. ((k = e.key) == key || (key != null && key.equals(k))))
13. return e;
14. \}
15. return null;
16. \}

1.  // 是否包含“值为value”的元素
2.  public boolean containsValue(Object value) \{
3.  // 若“value为null”，则调用containsNullValue()查找
4.  if (value == null)
5.  return containsNullValue();
6.  
7.  // 若“value不为null”，则查找HashMap中是否有值为value的节点。
8.  Entry\[\] tab = table;
9.  for (int i = 0; i < tab.length ; i++)
10. for (Entry e = tab\[i\] ; e != null ; e = e.next)
11. if (value.equals(e.value))
12. return true;
13. return false;
14. \}

通过上面源码的比较，我们可以得到第四个不同的地方

###  4、key和value是否允许null值 ###

其中key和value都是对象，并且不能包含重复key，但可以包含重复的value。

通过上面的ContainsKey方法和ContainsValue的源码我们可以很明显的看出：

Hashtable中，key和value都不允许出现null值。但是如果在Hashtable中有类似put(null,null)的操作，编译同样可以通过，因为key和value都是Object类型，但运行时会抛出NullPointerException异常，这是JDK的规范规定的。  
HashMap中，null可以作为键，这样的键只有一个；可以有一个或多个键所对应的值为null。当get()方法返回null值时，可能是 HashMap中没有该键，也可能使该键所对应的值为null。因此，在HashMap中不能由get()方法来判断HashMap中是否存在某个键， 而应该用containsKey()方法来判断。

###  5、两个遍历方式的内部实现上不同 ###

Hashtable、HashMap都使用了 Iterator。而由于历史原因，Hashtable还使用了Enumeration的方式 。

###  6、hash值不同 ###

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

hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值。

Hashtable计算hash值，直接用key的hashCode()，而HashMap重新计算了key的hash值，Hashtable在求hash值对应的位置索引时，用取模运算，而HashMap在求位置索引时，则用与运算，且这里一般先用hash&0x7FFFFFFF后，再对length取模，&0x7FFFFFFF的目的是为了将负的hash值转化为正值，因为hash值有可能为负数，而&0x7FFFFFFF后，只有符号外改变，而后面的位都不变。

###  7、内部实现使用的数组初始化和扩容方式不同 ###

HashTable在不指定容量的情况下的默认容量为11，而HashMap为16，Hashtable不要求底层数组的容量一定要为2的整数次幂，而HashMap则要求一定为2的整数次幂。  
Hashtable扩容时，将容量变为原来的2倍加1，而HashMap扩容时，将容量变为原来的2倍。

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

### 解决[hash][]冲突（哈希冲突）有以下四种方法： ###

> 链地址法  
> 再[哈希][Link 1]法  
> 建立公共溢出区  
> 开放定址法

法1：链地址法  
对于相同的哈希值，使用[链表][Link 2]进行连接。（HashMap使用此法）

优点

处理冲突简单，无堆积现象。即非同义词决不会发生冲突，因此平均查找长度较短；  
适合总数经常变化的情况。（因为拉链法中各链表上的结点空间是动态申请的）  
占空间小。装填因子可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计  
删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。  
缺点

查询时效率较低。（存储是动态的，查询时跳转需要更多的时间）  
在key-value可以预知，以及没有后续增改操作时候，开放定址法性能优于链地址法。  
不容易序列化  
法2：再哈希法  
提供多个哈希函数，如果第一个哈希函数计算出来的key的哈希值冲突了，则使用第二个哈希函数计算key的哈希值。

优点

不易产生聚集  
缺点

增加了计算时间  
法3：建立公共溢出区  
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

法4：开放定址法  
当关键字key的哈希地址p =H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，若p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi ，将相应元素存入其中。

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

开放定址法有下边三种方式：

线性探测再散列  
顺序查看下一个单元，直到找出一个空单元或查遍全表  
di=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号单元。

优点

容易序列化  
若可预知数据总数，可以创建完美哈希数列  
缺点

占空间很大。（开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间）  
删除节点很麻烦。不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。

[78633fc9b89e059dd31d4a876f60c444.png]: https://img-blog.csdnimg.cn/img_convert/78633fc9b89e059dd31d4a876f60c444.png
[Collections.synchronizedMap]: http://write.blog.csdn.net/postedit/51556314#synchronizedMap%28java.util.Map%29
[hash]: https://so.csdn.net/so/search?q=hash&spm=1001.2101.3001.7020
[Link 1]: https://so.csdn.net/so/search?q=%E5%93%88%E5%B8%8C&spm=1001.2101.3001.7020
[Link 2]: https://so.csdn.net/so/search?q=%E9%93%BE%E8%A1%A8&spm=1001.2101.3001.7020