java进阶|HashTable源码分析和理解

vlambda
2020-04-09

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 */@Slf4jpublic 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())); }); }}