Java 学习笔记续

Snailclimb

/

JavaGuide

Waiting for api.github.com...

00K

0K

0K

Waiting...

Map

HashMap 和HashTable 的区别

• 线程安全： HashMap 是非线程安全的，HashTable 是线程安全的。
• 效率： 因为线程安全的问题，HashMap 要比 HashTable 效率高一点。另外，HashTable 基本被淘汰，不要在代码中使用它；
• 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 NullPointerException。
• 创建时不指定容量初始值，HashTable 的默认初始大小为11，扩容变为原来的2n+1。HashMap 的初始大小为16，扩容时变为原来的2倍。
• 创建时制定容量初始值，HashTable 会直接使用给定的大小，HashMap则将其扩充至2的幂次方大小。
• 底层数据结构：HashMap 当链表长度大于阈值(默认为8),将链表转化为红黑树(如果当前数组长度小于64，那么会选择先进行数组扩容，而不是转为红黑树。) HashTable 没有这样的机制。
• 哈希函数的实现：HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而 HashTable 直接使用键的 hashCode() 值。

HashMap 和TreeMap 的区别

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap 它还实现了NavigableMap 接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。

NavigableMap 接口提供了丰富的方法来探索和操作键值对:

• 定向搜索: ceilingEntry(), floorEntry(), higherEntry()和 lowerEntry() 等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对。
• 子集操作: subMap(), headMap()和 tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。
• 逆序视图() 方法返回一个逆序的 NavigableMap 视图，使得可以反向迭代整个 TreeMap。
• 边界操作: firstEntry(), lastEntry(), pollFirstEntry()和 pollLastEntry() 等方法可以方便地访问和移除元素。

实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。

综上，相比于HashMap来说， TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

HashMap 的底层实现

JDK1.8之前

此时HashMap 底层使用数组和链表结合，也就是链表散列。HashMap 通过key 的hashcode 经过扰动函数处理后得到hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

HashMap 中的扰动函数（hash 方法）是用来优化哈希值的分布。通过对原始的 hashCode() 进行额外处理，扰动函数可以减小由于糟糕的 hashCode() 实现导致的碰撞，从而提高数据的分布均匀性。

JDK1.8之后

在解决哈希冲突时有了较大的变化，链表长度大于阈值时，将链表转化为红黑树。

这样做的目的是减少搜索时间：链表的查询效率为 O(n)（n 是链表的长度），红黑树是一种自平衡二叉搜索树，其查询效率为 O(log n)。当链表较短时，O(n) 和 O(log n) 的性能差异不明显。但当链表变长时，查询性能会显著下降。

HashMap 的长度为什么是2的幂次方

为了让 HashMap 存取高效并减少碰撞，我们需要确保数据尽量均匀分布。哈希值在 Java 中通常使用 int 表示，其范围是 -2147483648 ~ 2147483647前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但是，问题是一个 40 亿长度的数组，内存是放不下的。所以，这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。

这个算法应该如何设计呢？

我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1) 的前提是 length 是 2 的 n 次方）。” 并且，采用二进制位操作 & 相对于 % 能够提高运算效率。

除了上面所说的位运算比取余效率高之外，我觉得更重要的一个原因是：长度是 2 的幂次方，可以让 HashMap 在扩容的时候更均匀。例如:

• length = 8 时，length - 1 = 7 的二进制位0111
• length = 16 时，length - 1 = 15 的二进制位1111

这时候原本存在 HashMap 中的元素计算新的数组位置时 hash&(length-1)，取决 hash 的第四个二进制位（从右数），会出现两种情况：

• 第四个二进制位为 0，数组位置不变，也就是说当前元素在新数组和旧数组的位置相同。
• 第四个二进制位为 1，数组位置在新数组扩容之后的那一部分。

最后，简单总结一下 HashMap 的长度是 2 的幂次方的原因：

• 位运算效率更高：位运算(&)比取余运算(%)更高效。当长度为 2 的幂次方时，hash % length 等价于 hash & (length - 1)。
• 可以更好地保证哈希值的均匀分布：扩容之后，在旧数组元素 hash 值比较均匀的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。
• 扩容机制变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）。