对于HashMap源码剖析,可以参考: JDK集合源码之HashMap解析(上) 以及 JDK集合源码之HashMap解析(下) , HashMap底层红黑树实现(自己实现一个简单的红黑树)
1. 二者继的承体系有区别
HashTable
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5CZ0QGOzkTM1MWZ4QTO1QWO0UmZ0MmN5EmZmdTYxYjZz8CX5d2bs92Yl1iclB3bsVmdlR2LcNWaw9CXt92Yu4GZjlGbh5yYjV3Lc9CX6MHc0RHaiojIsJye.png)
HashMap
从图中可以对比得出,二者都是源于Map口接口,都实现Cloneable和Serializable接口,二者都可以克隆和序列化。但HashMap的父类是AbstractMap,HashTable父类是Dictionary。
Dictionary 类是一个已经被废弃的类(见其源码中的注释)。父类被废弃,自然其子类Hashtable也用的比较少了。
2. HashTable比HashMap多提供了elments() 和contains() 两个方法
elments()方法继承自父类Dictionnary。elements() 方法用于返回此Hashtable中的value的枚举。
contains()方法判断该Hashtable中是否包含传入的value。它的作用与containsValue()一致。事实上,contansValue()就只是调用了一下contains() 方法。
// 判断HashTable中是否存在value,存在返回true,否则返回false
public synchronized boolean contains(Object value) {
if (value == null) {
throw new NullPointerException();
}
Entry<?,?> tab[] = table;
for (int i = tab.length ; i-- > 0 ;) {
for (Entry<?,?> e = tab[i] ; e != null ; e = e.next) {
if (e.value.equals(value)) {
return true;
}
}
}
return false;
}
public boolean containsValue(Object value) {
return contains(value);
}
3. 二者对Null key 和Null value的支持不同
Hashtable中的Key 和 Value 均不可以为
NULL
,我们可以从其
put()
方法中得出:
public synchronized V put(K key, V value) {
// value不能为null,否则抛出空指针异常
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
// key不可以为null,因为当key为null时候,null调用hashCode()会报空指针异常
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
for(; entry != null ; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
addEntry(hash, key, value, index);
return null;
}
HashMap中,NULL可以作为键,且这样的键只能存在一个。可以有一个或多个键所对应的值为NULL。当get()方法返回NULL值时,可能是 HashMap中没有该键,也可能使该键所对应的值为NULL。因此,在HashMap中不能由get()方法来判断HashMap中是否存在某个键, 而应该用containsKey()方法来判断。
4. HashMap线程不安全,HashTable线程安全
Hashtable是线程安全的,它的每个方法中都加入了synchronize关键字。在多线程并发的环境下,可以直接使用Hashtable,不需要自己为它的方法实现同步
HashMap是线程不安全的,在多线程并发的环境下,可能会产生死锁等问题。使用HashMap时就必须要自己增加同步处。
虽然HashMap不是线程安全的,但是它的效率会比Hashtable要好很多。这样设计是合理的。在我们的日常使用当中,大部分时间是单线程操作的。HashMap把这部分操作解放出来了。当需要多线程操作的时候可以使用线程安全的ConcurrentHashMap。ConcurrentHashMap虽然也是线程安全的,但是它的效率比Hashtable要高好多倍。因为ConcurrentHashMap使用了分段锁,并不对整个数据进行锁定。
5. 二者初始容量大小和每次扩充容量大小的不同
Hashtable默认的初始大小为11,之后每次扩充,容量变为原来的2n+1。
HashMap默认的初始化大小为16。之后每次扩充,容量变为原来的2倍。
创建时,如果给定了容量初始值,那么Hashtable会直接使用你给定的大小,而HashMap会将其扩充为2的幂次方大小。也就是说Hashtable会尽量使用素数、奇数。而HashMap则总是使用2的幂作为哈希表的大小。
之所以会有这样的不同,是因为Hashtable和HashMap设计时的侧重点不同。Hashtable的侧重点是哈希的结果更加均匀,使得哈希冲突减少。当哈希表的大小为素数时,简单的取模哈希的结果会更加均匀。而HashMap则更加关注hash的计算效率问题。在取模计算时,如果模数是2的幂,那么我们可以直接使用位运算来得到结果,效率要大大高于做除法。HashMap为了加快hash的速度,将哈希表的大小固定为了2的幂。当然这引入了哈希分布不均匀的问题,所以HashMap为解决这问题,又对hash算法做了一些改动。这从而导致了Hashtable和HashMap的计算hash值的方法不同。
6. 二者计算hash值的方法不同
为了得到元素的位置,首先需要根据元素的KEY计算出一个hash值,然后再用这个hash值来计算得到最终的位置。
Hashtable直接使用对象的hashCode。hashCode是JDK根据对象的地址或者字符串或者数字算出来的int类型的数值。然后再使用除留余数法来获得最终的位置。
Hashtable在计算元素的位置时需要进行一次除法运算,而除法运算是比较耗时的。
HashMap为了提高计算效率,将哈希表的大小固定为了2的幂,这样在取模预算时,不需要做除法,只需要做位运算。位运算比除法的效率要高很多。
HashMap的效率虽然提高了,但是hash冲突却也增加了。因为它得出的hash值的低位相同的概率比较高。
为了解决这个问题,HashMap重新根据hashcode计算hash值后,又对hash值做了一些运算来打散数据。使得取得的位置更加分散,从而减少了hash冲突。当然了,为了高效,HashMap只做了一些简单的位处理。从而不至于把使用2的幂次方带来的效率提升给抵消掉。
HashTable源码
HashTable的属性
// Entry[]数组类型,Entry代表了“拉链”的节点,每一个Entry代表了一个键值对,哈希表的"key-value键值对"都是存储在Entry数组中的
private transient Entry<?,?>[] table;
// HashTable的大小,注意: 这个大小并不是HashTable的容器大小,而是他所包含Entry键值对的数量
private transient int count;
// Hashtable的阈值,用于判断是否需要调整HashTable的容量。threshold的值=“容量*加载因子”
private int threshold;
// 加载因子
private float loadFactor;
// 用来实现“fail-fast”机制的(也就是快速失败)。所谓快速失败就是在并发集合中,其进行迭代操作时,若有其他线程对其进行结构性的修改,这时迭代器会立马感知到,并且立即抛出ConcurrentModificationException异常,而不是等到迭代完成之后才告诉你(你已经出错了)
private transient int modCount = 0;
HashTable构造函数
public Hashtable(int initialCapacity, float loadFactor) {
// 验证初始容量
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
// 验证加载因子
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal Load: "+loadFactor);
if (initialCapacity==0)
initialCapacity = 1;
this.loadFactor = loadFactor;
// 初始化table,获得大小为initialCapacity的table数组
table = new Entry<?,?>[initialCapacity];
// 计算阀值 ---> threshold的值=“容量*加载因子”
threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}
public Hashtable(int initialCapacity) {
this(initialCapacity, 0.75f);
}
// 空参构造方法,初始容量为11
public Hashtable() {
this(11, 0.75f);
}
// 根据传入的Map集合直接初始化HashTable,容量为传入Map集合容量大小*2与11进行比较,取值较大者
public Hashtable(Map<? extends K, ? extends V> t) {
this(Math.max(2*t.size(), 11), 0.75f);
putAll(t);
}
private int hash(Object k) {
return hashSeed ^ k.hashCode();
}
HashTable几个常用成员方法
1. put方法
// 获取synchronized锁
public synchronized V put(K key, V value) {
// 如果value是空抛出异常
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
// 计算key的哈希值和index
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
// 遍历对应index位置的链表
for(; entry != null ; entry = entry.next) {
// 如果key 已经存在,则更新数据
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
entry.value = value;
return old;
}
}
// 增加新Entry元素
addEntry(hash, key, value, index);
return null;
}
步骤
1.获取synchronized锁。
2.put方法不允许null值,如果发现是null,则直接抛出异常。
3.计算key的哈希值和index
4.遍历对应位置的链表,如果发现已经存在相同的hash和key,则更新value,并返回旧值。
5.如果不存在相同的key的Entry节点,则调用addEntry方法增加节点。
2. addEntry方法
private void addEntry(int hash, K key, V value, int index) {
// 修改次数++
modCount++;
Entry<?,?> tab[] = table;
// 当前容量超过阈值,需要扩容
if (count >= threshold) {
// Rehash the table if the threshold is exceeded
// 重新构建桶数组(相当于扩容方法),并对数组中所有键值对重哈希,耗时
rehash();
tab = table;
// 根据key,获取hash值
hash = key.hashCode();
// 取摸运算(相当于HashMap定位桶的槽位)
// int index = (hash & 0x7FFFFFFF) % tab.length; ???
// (前31一个1代表数值,在计算机中整型最高位(32位)是符号位 0代表正数,1代表负数)
// 0x7FFFFFFF: 16进制表示的整型,是整型里面的最大值
// 0x7FFFFFFF: 0111 1111 1111 1111 1111 1111 1111 1111:除符号位外的所有1
// (hash & 0x7FFFFFFF) 将产生正整数
// (hash & 0x7FFFFFFF) % tab.length 将在标签长度的范围内
// 所有hashtable采用奇数导致的hash冲突会比较少,采用偶数会导致的冲突会增多
// h & (length-1); hashmap采用相与的方法,所有采用2的幂次方的长度会导致的冲突比较少
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
// 获取index槽位的桶中的Entry链表,头节点是e
Entry<K,V> e = (Entry<K,V>) tab[index];
// 生成一个新结点, 将新结点插到链表首部,其下一个结点是e
tab[index] = new Entry<>(hash, key, value, e);
// 有效元素数量++
count++;
}
- 当前容量超过阈值,需要扩容
- 生成一个新结点, 将新结点插到链表首部
3. rehash方法(扩容方法)
相当于hashmap中的
resize()
方法
protected void rehash() {
// 获取当前table数组的容量(数组长度)
int oldCapacity = table.length;
// oldMap: 当前table数组
Entry<?,?>[] oldMap = table;
// 扩容扩为原来的两倍+1 ---> 即:扩容为原来的 2n + 1 这样可以确保容量是奇数
// 奇数有利于index = (hash & 0x7FFFFFFF) % tab.length 求桶位的时候减少hash冲突
// 这种方式类似于HashMap: hash & (tab.length-1),确保容量为2的幂次方,可以减少hash冲突
int newCapacity = (oldCapacity << 1) + 1;
// 判断是否超过最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0) {
if (oldCapacity == MAX_ARRAY_SIZE)
// Keep running with MAX_ARRAY_SIZE buckets
return;
newCapacity = MAX_ARRAY_SIZE;
}
// newMap:新table数组
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
// HashTable结构修改次数++
modCount++;
// 计算下一次rehash的阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;
// 把旧哈希表的键值对重新哈希到新哈希表中去(双重循环,耗时!)
// 这个方法类似于HashMap扩容后,将旧数组数据赋给新数组,
// 在HashMap中会将其旧数组每个桶位进一步‘打散',放置到新数组对应的桶位上(有一个重新计算桶位的过程)
for (int i = oldCapacity ; i-- > 0 ;) {
for (Entry<K,V> old = (Entry<K,V>)oldMap[i] ; old != null ; ) {
Entry<K,V> e = old;
old = old.next;
// 根据新table数组容量newCapacity重新计算桶位
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
// 链表放入该桶中
newMap[index] = e;
}
}
}
- 数组长度增加一倍(如果超过上限,则设置成上限值)。
- 更新哈希表的扩容门限值。
- 遍历旧表中的节点,计算在新表中的index,插入到对应位置链表的头部。
4. get方法
public synchronized V get(Object key) {// 根据键取出对应索引
Entry tab[] = table;
int hash = hash(key);// 先根据key计算hash值
int index = (hash & 0x7FFFFFFF) % tab.length;// 再根据hash值找到索引
for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {// 遍历entry链
if ((e.hash == hash) && e.key.equals(key)) {// 若找到该键
return e.value;// 返回对应的值
}
}
return null;// 否则返回null
}
骤
- 先获取synchronized锁。
- 计算key的哈希值和index。
- 在对应位置的链表中寻找具有相同hash和key的节点,返回节点的value。
- 如果遍历结束都没有找到节点,则返回
。null
5. remove方法
public synchronized V remove(Object key) {
Entry<?,?> tab[] = table;
// 计算key的哈希值和index
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for(Entry<K,V> prev = null ; e != null ; prev = e, e = e.next) {
// 遍历对应位置的链表,寻找待删除节点
if ((e.hash == hash) && e.key.equals(key)) {
modCount++;
// 更新前驱节点的next,指向e的next
if (prev != null) {
prev.next = e.next;
} else {
tab[index] = e.next;
}
count--;
V oldValue = e.value;
e.value = null;
// 返回待删除节点的value值
return oldValue;
}
}
// 如果不存在,返回null
return null;
}
- 遍历对应位置的链表,寻找待删除节点,如果存在,用e表示待删除节点,pre表示前驱节点。如果不存在,返回
null
- 更新前驱节点的next,指向e的next。返回待删除节点的value值。