Java HashMap与HashTable的性能对比
1. Java集合框架基础回顾
在深入探讨 HashMap 和 HashTable 的性能对比之前，我们先来回顾一下Java集合框架的基础知识。Java集合框架提供了一套丰富的接口和类，用于存储和操作对象集合。其中，Map 接口是用于存储键值对（key - value pairs）的集合，而 HashMap 和 HashTable 是实现 Map 接口的两个重要类。
Map 接口的实现类提供了根据键来快速查找值的功能。键在 Map 中是唯一的，而值可以重复。HashMap 和 HashTable 都是基于哈希表（hash table）的数据结构来实现这种键值对存储和查找功能的。哈希表是一种基于哈希函数（hash function）的数据结构，它通过将键的哈希值映射到一个特定的桶（bucket）中，从而实现快速的查找操作。
2. 底层数据结构分析
2.1 HashMap 的底层数据结构
HashMap 在Java 8 之前，底层数据结构是数组 + 链表。数组用于存储哈希桶，每个桶中可以存放一个键值对节点。当多个键值对的哈希值相同（哈希冲突）时，这些键值对会以链表的形式存储在同一个桶中。
在Java 8 及之后，为了优化哈希冲突的性能，HashMap 在链表长度达到一定阈值（默认为 8）时，会将链表转换为红黑树（Red - Black Tree）。红黑树是一种自平衡的二叉查找树，相比于链表，它在查找、插入和删除操作上具有更好的时间复杂度，平均时间复杂度为 O(log n)，而链表的查找操作平均时间复杂度为 O(n)。
下面是 HashMap 底层数据结构的简单示意代码（非实际 HashMap 源码，仅为示意）：
class Node<K, V> {
final int hash;
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
class MyHashMap<K, V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
Node<K, V>[] table;
int size;
int threshold;
final float loadFactor;
public MyHashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
this.threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
this.table = new Node[DEFAULT_INITIAL_CAPACITY];
}
private int hash(Object key) {
int h;
return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public V put(K key, V value) {
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Node<K, V> e = table[i]; e!= null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key!= null && key.equals(k)))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
addEntry(hash, key, value, i);
return null;
}
private void addEntry(int hash, K key, V value, int bucketIndex) {
if (size >= threshold) {
resize(2 * table.length);
}
createEntry(hash, key, value, bucketIndex);
}
private void createEntry(int hash, K key, V value, int bucketIndex) {
Node<K, V> e = table[bucketIndex];
table[bucketIndex] = new Node<>(hash, key, value, e);
size++;
}
private void resize(int newCapacity) {
Node<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Node<K, V>[] newTable = new Node[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
private void transfer(Node<K, V>[] newTable) {
int newCapacity = newTable.length;
for (Node<K, V> e : table) {
while (null!= e) {
Node<K, V> next = e.next;
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
private int indexFor(int hash, int length) {
return hash & (length - 1);
}
public V get(Object key) {
int hash = hash(key);
int i = indexFor(hash, table.length);
for (Node<K, V> e = table[i]; e!= null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || (key!= null && key.equals(k)))) {
return e.value;
}
}
return null;
}
}
2.2 HashTable 的底层数据结构
HashTable 的底层数据结构与Java 8 之前的 HashMap 类似，也是基于数组 + 链表实现。每个桶中存储一个链表，当发生哈希冲突时，新的键值对会被添加到链表的末尾。
以下是简单示意 HashTable 底层结构的代码（非实际 HashTable 源码，仅为示意）：
class HashEntry<K, V> {
final K key;
V value;
HashEntry<K, V> next;
HashEntry(K key, V value, HashEntry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
class MyHashTable<K, V> {
private static final int DEFAULT_INITIAL_CAPACITY = 11;
private static final float DEFAULT_LOAD_FACTOR = 0.75f;
HashEntry<K, V>[] table;
int size;
int threshold;
final float loadFactor;
public MyHashTable() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
this.threshold = (int) (DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
this.table = new HashEntry[DEFAULT_INITIAL_CAPACITY];
}
private int hash(Object key) {
return key.hashCode() & 0x7FFFFFFF;
}
public synchronized V put(K key, V value) {
int hash = hash(key);
int index = (hash % table.length);
for (HashEntry<K, V> e = table[index]; e!= null; e = e.next) {
if ((e.key.equals(key))) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
addEntry(hash, key, value, index);
return null;
}
private void addEntry(int hash, K key, V value, int bucketIndex) {
if (size >= threshold) {
resize(2 * table.length + 1);
}
createEntry(hash, key, value, bucketIndex);
}
private void createEntry(int hash, K key, V value, int bucketIndex) {
HashEntry<K, V> e = table[bucketIndex];
table[bucketIndex] = new HashEntry<>(key, value, e);
size++;
}
private void resize(int newCapacity) {
HashEntry<K, V>[] oldTable = table;
int oldCapacity = oldTable.length;
HashEntry<K, V>[] newTable = new HashEntry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
private void transfer(HashEntry<K, V>[] newTable) {
int newCapacity = newTable.length;
for (HashEntry<K, V> e : table) {
while (null!= e) {
HashEntry<K, V> next = e.next;
int i = (e.hash % newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
public synchronized V get(Object key) {
int hash = hash(key);
int index = (hash % table.length);
for (HashEntry<K, V> e = table[index]; e!= null; e = e.next) {
if (e.key.equals(key)) {
return e.value;
}
}
return null;
}
}
3. 线程安全性对性能的影响
3.1 HashMap 的线程非安全性
HashMap 是非线程安全的。这意味着在多线程环境下，如果多个线程同时对 HashMap 进行读写操作，可能会导致数据不一致或者其他未定义行为。例如，当一个线程正在扩容 HashMap 时，另一个线程同时进行插入操作，可能会导致链表形成环，进而在获取元素时陷入死循环。
以下是一个简单的多线程操作 HashMap 导致问题的示例代码：
import java.util.HashMap;
import java.util.Map;
public class HashMapThreadExample {
private static Map<Integer, Integer> hashMap = new HashMap<>();
public static void main(String[] args) {
Thread thread1 = new Thread(() -> {
for (int i = 0; i < 10000; i++) {
hashMap.put(i, i);
}
});
Thread thread2 = new Thread(() -> {
for (int i = 10000; i < 20000; i++) {
hashMap.put(i, i);
}
});
thread1.start();
thread2.start();
try {
thread1.join();
thread2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("HashMap size: " + hashMap.size());
}
}
在上述代码中，两个线程同时向 HashMap 中插入数据。由于 HashMap 是非线程安全的，可能会出现数据丢失或者其他不一致的情况。
3.2 HashTable 的线程安全性
HashTable 是线程安全的，它的所有方法（如 put、get、remove 等）都被 synchronized 关键字修饰。这意味着在同一时间，只有一个线程可以访问 HashTable 的方法，从而避免了多线程并发访问导致的数据不一致问题。
以下是 HashTable 中 put 方法的实际源码（简化示意）：
public synchronized V put(K key, V value) {
// 检查键是否为 null，HashTable 不允许键为 null
if (key == null) {
throw new NullPointerException();
}
// 计算哈希值
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % table.length;
for (Entry<?,?> e = table[index]; e!= null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
@SuppressWarnings("unchecked")
V oldValue = (V)e.value;
e.value = value;
return oldValue;
}
}
addEntry(hash, key, value, index);
return null;
}
虽然 HashTable 的线程安全性保证了多线程环境下的数据一致性，但是由于 synchronized 关键字的存在，每次方法调用都需要获取锁，这会带来一定的性能开销。特别是在高并发环境下，锁竞争会成为性能瓶颈，导致整体性能下降。
4. 初始容量和负载因子对性能的影响
4.1 HashMap 的初始容量和负载因子
HashMap 的初始容量是指哈希表在创建时的大小，默认值为 16。负载因子是一个介于 0 和 1 之间的浮点数，默认值为 0.75。负载因子用于衡量哈希表的填满程度，当哈希表中的键值对数量达到 容量 * 负载因子 时，哈希表会进行扩容操作。
例如，如果 HashMap 的初始容量为 16，负载因子为 0.75，那么当哈希表中存储了 16 * 0.75 = 12 个键值对时，就会触发扩容。扩容操作会创建一个新的更大的数组，并将原数组中的所有键值对重新计算哈希值并插入到新数组中，这个过程会消耗较多的时间和空间。
以下是创建 HashMap 时指定初始容量和负载因子的示例代码：
import java.util.HashMap;
import java.util.Map;
public class HashMapCapacityExample {
public static void main(String[] args) {
// 创建一个初始容量为 32，负载因子为 0.8 的 HashMap
Map<Integer, String> hashMap = new HashMap<>(32, 0.8f);
for (int i = 0; i < 25; i++) {
hashMap.put(i, "Value " + i);
}
}
}
合理设置初始容量和负载因子可以减少扩容次数，从而提高 HashMap 的性能。如果能够提前预估 HashMap 中将要存储的元素数量，将初始容量设置为预估数量除以负载因子并向上取整，可以避免在添加元素过程中频繁扩容。
4.2 HashTable 的初始容量和负载因子
HashTable 的初始容量默认值为 11，负载因子默认值也为 0.75。与 HashMap 类似，当 HashTable 中的键值对数量达到 容量 * 负载因子 时，会进行扩容操作。但是，HashTable 的扩容机制略有不同，它每次扩容时新的容量是原容量的 2 倍加 1。
以下是创建 HashTable 并指定初始容量和负载因子的示例代码：
import java.util.Hashtable;
import java.util.Map;
public class HashTableCapacityExample {
public static void main(String[] args) {
// 创建一个初始容量为 23，负载因子为 0.8 的 HashTable
Map<Integer, String> hashTable = new Hashtable<>(23, 0.8f);
for (int i = 0; i < 18; i++) {
hashTable.put(i, "Value " + i);
}
}
}
由于 HashTable 是线程安全的，扩容操作也需要同步，这使得扩容时的性能开销比 HashMap 更大。因此，在使用 HashTable 时，更需要合理设置初始容量和负载因子，以减少不必要的扩容操作。
5. 哈希算法对性能的影响
5.1 HashMap 的哈希算法
HashMap 在Java 8 中的哈希算法做了优化。它首先获取键的 hashCode，然后通过 (h = key.hashCode()) ^ (h >>> 16) 进行扰动计算。这种计算方式将哈希值的高位和低位进行异或运算，使得哈希值的分布更加均匀，减少哈希冲突的发生。
以下是 HashMap 中哈希算法的实际源码：
static final int hash(Object key) {
int h;
return (key == null)? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
良好的哈希算法可以使得键值对在哈希表中分布更均匀，从而减少链表的长度，提高查找、插入和删除操作的性能。例如，对于一些哈希冲突严重的键，如果使用 HashMap 的哈希算法，可以在一定程度上缓解冲突，提高性能。
5.2 HashTable 的哈希算法
HashTable 的哈希算法相对简单，它直接使用键的 hashCode 与 0x7FFFFFFF 进行按位与操作，得到一个非负的哈希值，然后通过取模运算（hash % table.length）确定键值对在哈希表中的位置。
以下是 HashTable 中哈希算法的示意代码：
private int hash(Object key) {
return key.hashCode() & 0x7FFFFFFF;
}
这种简单的哈希算法可能导致哈希值分布不够均匀，在某些情况下，哈希冲突可能会更频繁，从而影响 HashTable 的性能。例如，当键的 hashCode 分布不均匀时，可能会导致大量键值对集中在少数几个桶中，形成较长的链表，增加查找等操作的时间复杂度。
6. 操作性能对比实验
为了更直观地对比 HashMap 和 HashTable 的性能，我们进行一系列的操作性能对比实验，包括插入、查找和删除操作。
6.1 插入操作性能对比
以下是对比 HashMap 和 HashTable 插入操作性能的代码：
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
public class InsertPerformanceTest {
private static final int COUNT = 100000;
public static void main(String[] args) {
Map<Integer, Integer> hashMap = new HashMap<>();
long startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
hashMap.put(i, i);
}
long endTime = System.currentTimeMillis();
System.out.println("HashMap insert time: " + (endTime - startTime) + " ms");
Map<Integer, Integer> hashTable = new Hashtable<>();
startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
hashTable.put(i, i);
}
endTime = System.currentTimeMillis();
System.out.println("HashTable insert time: " + (endTime - startTime) + " ms");
}
}
在上述代码中，我们分别向 HashMap 和 HashTable 中插入 100000 个键值对，并记录插入操作所花费的时间。由于 HashTable 的线程安全性，其插入操作需要获取锁，因此在单线程环境下，HashMap 的插入性能通常会优于 HashTable。
6.2 查找操作性能对比
以下是对比 HashMap 和 HashTable 查找操作性能的代码：
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
public class SearchPerformanceTest {
private static final int COUNT = 100000;
public static void main(String[] args) {
Map<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < COUNT; i++) {
hashMap.put(i, i);
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
hashMap.get(i);
}
long endTime = System.currentTimeMillis();
System.out.println("HashMap search time: " + (endTime - startTime) + " ms");
Map<Integer, Integer> hashTable = new Hashtable<>();
for (int i = 0; i < COUNT; i++) {
hashTable.put(i, i);
}
startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
hashTable.get(i);
}
endTime = System.currentTimeMillis();
System.out.println("HashTable search time: " + (endTime - startTime) + " ms");
}
}
在查找操作中，HashMap 和 HashTable 的性能差异主要取决于哈希冲突的情况。如果哈希冲突较少，两者的查找性能相近；但如果哈希冲突严重，由于 HashMap 在Java 8 中使用了红黑树优化，其查找性能可能会优于 HashTable。
6.3 删除操作性能对比
以下是对比 HashMap 和 HashTable 删除操作性能的代码：
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
public class DeletePerformanceTest {
private static final int COUNT = 100000;
public static void main(String[] args) {
Map<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0; i < COUNT; i++) {
hashMap.put(i, i);
}
long startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
hashMap.remove(i);
}
long endTime = System.currentTimeMillis();
System.out.println("HashMap delete time: " + (endTime - startTime) + " ms");
Map<Integer, Integer> hashTable = new Hashtable<>();
for (int i = 0; i < COUNT; i++) {
hashTable.put(i, i);
}
startTime = System.currentTimeMillis();
for (int i = 0; i < COUNT; i++) {
hashTable.remove(i);
}
endTime = System.currentTimeMillis();
System.out.println("HashTable delete time: " + (endTime - startTime) + " ms");
}
}
在删除操作方面，HashMap 的性能通常也会优于 HashTable。因为 HashTable 的线程安全性使得删除操作需要获取锁，增加了额外的开销。同时，HashMap 在删除节点后，如果链表长度小于一定阈值（默认为 6），会将红黑树转换回链表，这也在一定程度上优化了删除操作的性能。
7. 适用场景分析
7.1 HashMap 的适用场景
由于 HashMap 非线程安全，它适用于单线程环境下，或者在多线程环境中通过其他并发控制机制（如 ConcurrentHashMap）来保证线程安全的场景。在需要高性能的插入、查找和删除操作，并且对线程安全性没有要求的情况下，HashMap 是一个很好的选择。例如，在大多数的单线程应用程序中，或者在多线程环境下仅进行读操作（读多写少）的场景，HashMap 可以提供很好的性能。
7.2 HashTable 的适用场景
HashTable 适用于对线程安全性要求较高，并且对性能要求不是特别苛刻的场景。例如，在一些早期的Java应用程序中，由于当时没有更好的线程安全的哈希表实现，HashTable 被广泛使用。另外，在一些对数据一致性要求极高，且并发访问量不是特别大的场景下，HashTable 也可以满足需求。但在高并发环境下，由于锁竞争的存在，HashTable 的性能会受到较大影响，此时更推荐使用 ConcurrentHashMap。
8. 总结与建议
通过对 HashMap 和 HashTable 的底层数据结构、线程安全性、初始容量和负载因子、哈希算法以及操作性能的对比分析，我们可以得出以下结论：
- 线程安全性：
HashMap非线程安全，HashTable线程安全。在多线程环境下，HashTable虽然保证了数据一致性，但由于锁的存在，性能会受到影响。如果需要在多线程环境下使用哈希表，推荐使用ConcurrentHashMap，它提供了更好的并发性能。 - 性能：在单线程环境或者读多写少的多线程环境下，
HashMap的性能通常优于HashTable。HashMap在Java 8 中通过红黑树优化了哈希冲突的处理，进一步提高了性能。 - 适用场景：根据具体需求选择合适的哈希表实现。如果对线程安全性没有要求，优先选择
HashMap；如果对线程安全性有严格要求且并发量不大，可以考虑HashTable；如果在高并发环境下需要线程安全的哈希表，ConcurrentHashMap是更好的选择。
在实际开发中，我们应该根据应用程序的具体特点和需求，合理选择 HashMap、HashTable 或者其他哈希表实现，以达到最佳的性能和功能平衡。同时，深入理解它们的原理和性能特点，有助于我们写出高效、稳定的代码。
希望通过本文的介绍，读者能够对 HashMap 和 HashTable 的性能对比有更深入的理解，并在实际编程中做出更合适的选择。