java进阶|HashTable源码分析和理解
键值对集合Map,HashTable都是我们常用的，但是随着多线程环境以及代码的普及，ConcurrentHashMap这样的并发集合也常用了起来，今天我们先来分析一下HashTable的源码。
HashTable的结构图如下，以及我们可以去看下类继承关系图。便于自己理解，这里指的都是自己分析的。
public class Hashtable<K,V>
extends Dictionary<K,V>
implements Map<K,V>, Cloneable, java.io.Serializable {}首先我们先看下HashTable的put()方法，毕竟使用一个集合就是为了存取数据的。
public synchronized V put(K key, V value) {
//判断传入的value值是否为null，若为null直接抛出空NPE异常
if (value == null) {
throw new NullPointerException();
}
// Makes sure the key is not already in the hashtable.
Entry<?,?> tab[] = table;
int hash = key.hashCode();//获取键key的hash值
int index = (hash & 0x7FFFFFFF) % tab.length;//获取hash槽的位置，之所以&上是为了使hash分布更均匀
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];//获取指定索引位置的entry，然后进行循环判断
for(; entry != null ; entry = entry.next) {
//若hash值相等且查询出的key与put进去的值相等，则进行值替换
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;
}
步骤一:
private void addEntry(int hash, K key, V value, int index) {
modCount++;
Entry<?,?> tab[] = table;
//首先判断当前hashTable的元素个数是否大于阈值threashold，若大于则需要rehash()
//接下来再看如何rehash()的
if (count >= threshold) {
rehash();
tab = table;
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;
}
// Creates the new entry.
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>) tab[index];
tab[index] = new Entry<>(hash, key, value, e);//步骤一
count++;
}
步骤一:这里面主要是定义一个内部类用于将元素进行数据的保存
private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
public String toString() {
return key.toString()+"="+value.toString();
}
}private static class Entry<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Entry<K,V> next;
protected Entry(int hash, K key, V value, Entry<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
@SuppressWarnings("unchecked")
protected Object clone() {
return new Entry<>(hash, key, value,
(next==null ? null : (Entry<K,V>) next.clone()));
}
// Map.Entry Ops
public K getKey() {
return key;
}
public V getValue() {
return value;
}
public V setValue(V value) {
if (value == null)
throw new NullPointerException();
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return (key==null ? e.getKey()==null : key.equals(e.getKey())) &&
(value==null ? e.getValue()==null : value.equals(e.getValue()));
}
public int hashCode() {
return hash ^ Objects.hashCode(value);
}
public String toString() {
return key.toString()+"="+value.toString();
}
}接下来我们分析一下rehash()方法，看下是如何扩容的。
protected void rehash() {
//首先获取原来hashTable容量的大小
int oldCapacity = table.length;
Entry<?,?>[] oldMap = table;
//然后计算新容量大小,2倍+1的容量大小
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;
}
Entry<?,?>[] newMap = new Entry<?,?>[newCapacity];
modCount++;
//计算阈值
threshold = (int)Math.min(newCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
table = newMap;//将新的entry数据引用指向原来的table
//循环遍历旧的数据，然后将旧的entry数据复制到新的entry里面，额，又是数据的拷贝
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;
int index = (e.hash & 0x7FFFFFFF) % newCapacity;
e.next = (Entry<K,V>)newMap[index];
newMap[index] = e;
}
}
}
步骤一:
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;以上就是rehash()的过程，是不是也很简单呢。
接下来我们看下HashTable如何获取键的集合keySet()。
public Set<K> keySet() {
if (keySet == null)//若keySet为null，则直接new一个空的集合进行返回
keySet = Collections.synchronizedSet(new KeySet(), this);
return keySet;
}继续看下HashTable如何获取值的集合valueSet()方法。
public Collection<V> values() {
if (values==null)
values = Collections.synchronizedCollection(new ValueCollection(),
this);
return values;
}判断HashTable集合数据是否为空isEmpty()方法。
public synchronized boolean isEmpty() {
return count == 0;
}获取HashTable集合数据元素个数的size()方法。
public synchronized int size() {
return count;
}判断HashTable集合数据是否包含指定的value值contains()方法。
public synchronized boolean contains(Object value) {
//若传入的值为null直接抛出NPE，因为put进去的时候value值是不能为空的，所以查询的时候自然不能包含为null的数据
if (value == null) {
throw new NullPointerException();
}
//将table的引用赋值新的tab[]数组，然后循环遍历entry，获取entry的value进行一一比较，若相等，直接返回true
//若不相等，则直接返回false
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;
}判断HashTable集合数据是否包含指定的key,containsKey()。
public synchronized boolean containsKey(Object key) {
Entry<?,?> tab[] = table;//将table引用直接新的tab[]
int hash = key.hashCode();//获取key的hashCode，然后获取hashTable的索引位置做准备
int index = (hash & 0x7FFFFFFF) % tab.length;
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
//若循环遍历判断hash值以及key相等，则直接返回true，否则直接返回false
if ((e.hash == hash) && e.key.equals(key)) {
return true;
}
}
return false;
}获取HashTable集合数据的值，根据key获取value的get()方法。
public synchronized V get(Object key) {
Entry<?,?> tab[] = table;//将table引用赋值新的tab[]引用
int hash = key.hashCode();//计算key的hash值，然后为确定hashTable的索引值做准备
int index = (hash & 0x7FFFFFFF) % tab.length;
//循环遍历tab的每一个entry元素，判断hash值是否相等以及key是否相等
//相等则直接返回true，否则返回false
for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
return (V)e.value;
}
}
return null;
}判断HashTable集合数据是否包含value值,containsValue()方法，这个方法是复用了contains()方法。
public boolean containsValue(Object value) {
return contains(value);
}如何清空HashTable集合数据的元素信息:clear()方法。
public synchronized void clear() {
Entry<?,?> tab[] = table;
modCount++;
for (int index = tab.length; --index >= 0; )
tab[index] = null;//let's gc to collect
count = 0;//元素个数赋值为0
}根据key获取HashTable集合数据的值，若没有直接获取默认值getOrDefault()。
public synchronized V getOrDefault(Object key, V defaultValue) {
V result = get(key);//根据key获取value值
return (null == result) ? defaultValue : result;//若获取的值为null，则直接返回默认值defaultValue
}进行HashTable集合数据的遍历操作forEach()操作。
public synchronized void forEach(BiConsumer<? super K, ? super V> action) {
Objects.requireNonNull(action); //首先判断要传入的action是否为null
final int expectedModCount = modCount;
Entry<?, ?>[] tab = table;//将table直接赋值新的tab，然后进行循环遍历
for (Entry<?, ?> entry : tab) {
//while循环判断entry是否为null
while (entry != null) {
//accept操作，关于Consumer的操作，自己可以看下怎么操作的
action.accept((K)entry.key, (V)entry.value);
entry = entry.next;
if (expectedModCount != modCount) {
throw new ConcurrentModificationException();
}
}
}
}HashTable集合数据的putIfAbsent()方法，若key存在，则直接更新，否则新增一条数据。
public synchronized V putIfAbsent(K key, V value) {
Objects.requireNonNull(value);//判断value值是否为null，若value为null则直接抛出NPE
Entry<?,?> tab[] = table;
int hash = key.hashCode();//计算key的hashCode，计算hash槽的位置做准备
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> entry = (Entry<K,V>)tab[index];
//循环遍历entry集合，判断hash值是否相等以及key是否相等，若相等，则直接更新，否则新增
for (; entry != null; entry = entry.next) {
if ((entry.hash == hash) && entry.key.equals(key)) {
V old = entry.value;
if (old == null) {
entry.value = value;
}
return old;
}
}
addEntry(hash, key, value, index);
return null;
}进行HashTable集合数据的替换replace()方法。
public synchronized V replace(K key, V value) {
Objects.requireNonNull(value);
Entry<?,?> tab[] = table;
int hash = key.hashCode();
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
Entry<K,V> e = (Entry<K,V>)tab[index];
for (; e != null; e = e.next) {
if ((e.hash == hash) && e.key.equals(key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
return null;
}HashTable集合数据的替换操作replace()方法。
public synchronized V replace(K key, V value) {
Objects.requireNonNull(value);//首先判断value值是否为null，若为null直接抛出NPE
Entry<?,?> tab[] = table;//将table赋值到新的tab[]然后进行后面的操作
int hash = key.hashCode();//定位key的hashCode，为下面的定位hash槽进行位置确定做准备
int index = (hash & 0x7FFFFFFF) % tab.length;
@SuppressWarnings("unchecked")
//获取指定index位置的entry值
Entry<K,V> e = (Entry<K,V>)tab[index];
for (; e != null; e = e.next) {
//找到对应的hash值相等以及key相等的entry，然后获取旧值，将value进行赋值，然后返回旧值
if ((e.hash == hash) && e.key.equals(key)) {
V oldValue = e.value;
e.value = value;
return oldValue;
}
}
return null;
}到这里，想对HashTable这个键值对集合源码分析的方法就结束了，其它的部分方法就不分析了，用到的很少，接下来继续按照以往的风格贴上一张HashTable的结构图，以及自己源码走读所用到的部分示例程序。
package com.wpw.springbootjuc.java8.map;
import lombok.extern.slf4j.Slf4j;
import java.util.Collection;
import java.util.Hashtable;
import java.util.Set;
/**
* 源码走读
*
* @author wpw
*/
@Slf4j
public class HashTableTest {
public static void main(String[] args) {
Hashtable<String, String> hashtable = new Hashtable<>();
hashtable.put("姓名", "张三");
hashtable.put("年龄", "10");
hashtable.entrySet().forEach(entry -> {
System.out.println(String.format("键:%s，值:%s", entry.getKey(), entry.getValue()));
});
System.out.println();
Set<String> keySet = hashtable.keySet();
keySet.stream().forEach(x -> System.out.print(String.format("键:%s", x)));
System.out.println();
log.info("获取HashTable的值集合数据");
Collection<String> values = hashtable.values();
values.forEach(x -> System.out.print(x + "\t"));
System.out.println();
boolean empty = hashtable.isEmpty();
System.out.println("empty = " + empty);
int size = hashtable.size();
System.out.println("size = " + size);
boolean flag = hashtable.contains("10");
System.out.println("flag = " + flag);
boolean containsValue = hashtable.containsValue("张三");
System.out.println("containsValue = " + containsValue);
log.info("清空HashTable的数据信息");
hashtable.clear();
log.info("获取HashTable数据集合的元素个数");
int count = hashtable.size();
System.out.println("count = " + count);
String defaultValue = hashtable.getOrDefault("李四", "浙江");
System.out.println("defaultValue = " + defaultValue);
log.info("HashTable的putIfAbsent()方法的使用");
//如果存在，则更新，不存在则直接新增
hashtable.putIfAbsent("年龄", "张三2");
hashtable.put("区域", "浙江");
hashtable.entrySet().forEach(entry -> {
System.out.println(String.format("键:%s，值:%s", entry.getKey(), entry.getValue()));
});
System.out.println();
hashtable.replace("区域", "北京");
hashtable.entrySet().forEach(entry -> {
System.out.println(String.format("键:%s，值%s", entry.getKey(), entry.getValue()));
});
}
}
到这里就结束了，后面慢慢去分析自己喜欢文章了。喜欢的可以分享和在看呗。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-04-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读