基于 JDK1.7 分析 HashMap 与 HashTable 源码实现

发表于 2017-08-07 分类于 Code 阅读次数：

HashMap

HashMap 的数据结构

HashMap 的底层实现是 Entry数组：

public HashMap(int initialCapacity, float loadFactor) {
	//初始容量不能<0
	if (initialCapacity < 0)
		throw new IllegalArgumentException("Illegal initial capacity: "
			+ initialCapacity);
	//初始容量不能 > 最大容量值，HashMap的最大容量值为2^30
	if (initialCapacity > MAXIMUM_CAPACITY)
		initialCapacity = MAXIMUM_CAPACITY;
	//负载因子不能 < 0
	if (loadFactor <= 0 || Float.isNaN(loadFactor))
		throw new IllegalArgumentException("Illegal load factor: "
			+ loadFactor);

	// 计算出大于 initialCapacity 的最小的 2 的 n 次方值。
	int capacity = 1;
	while (capacity < initialCapacity)
		capacity <<= 1;
	this.loadFactor = loadFactor;
	//设置HashMap的容量极限，当HashMap的容量达到该极限时就会进行扩容操作
	threshold = (int) (capacity * loadFactor);
	//初始化table数组
	table = new Entry[capacity];
	init();
}

从 HashMap 构造方法可以看出：

每次实例化一个 HashMap，其内部会自动初始化一个 Entry数组；
HashMap 支持带参构造，int initCapacity（初始化数组大小，默认值是16），另一个是float loadFactor（负载因子，默认值是0.75）。HashMap 内部实现会根据initCapacity 与 loadFactor 计算出一个临界值即threshold = (int) (capacity * loadFactor);，当HashMap 存放的元素数量达到这个临界值时会自动进行扩容。容易得出结论，负载因子是用户用于确定当存储的数量达到存储容量的比例时再进行扩容（后有详细解释）。

static class Entry<K,V> implements Map.Entry<K,V> {
     final K key;
     V value;
     Entry<K,V> next;
     final int hash;

	 ... ...
}

Entry是 HashMap 的内部类，其中 Entry 为 HashMap 的内部类，它包含了键 key、值 value、下一个节点 next，以及 hash 值，正是由于 Entry 才构成了 table 数组的项为链表。

HashMap 的“读与写”

HashMap 添加（put）数据

public V put(K key, V value) {
	//当key为null，调用putForNullKey方法，保存null于table第一个位置中，这是HashMap允许为null的原因
	if (key == null) {
		return putForNullKey(value);
	}

	int hash = hash(key.hashCode());

	int i = indexFor(hash, table.length);

    for (Entry<K, V> e = table[i]; e != null; e = e.next) {
		Object k = null;
		    if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
			V oldValue = e.value;
			e.value = value;
			e.recordAccess(this);
			return oldValue;
         }
     }
     modCount++;

     addEntry(hash, key, value, i);
     return null;
}

由 put()方法源码可见，添加数据时，首先判断 key 是否为 null，若为 null，则直接调用 putForNullKey 方法（这也是 HashMap 不同于 HashTable 支持键值为 null的原因）。若不为空则先计算 key 的 hash 值（hashCode()）得到长度固定的整型值。

然后根据 hash 值搜索在 table 数组中的索引位置，如果 table 数组在该位置处有元素，需要比较是否存在相同的 key 值。若存在，则覆盖之前的 value；若不存在，则直接将数据存放于链表头部（每个节点包括了存放的数据（key、value），指向下一节点的指针。数据保存为”头插入“）。如果 table 数组在该位置处无元素，直接保存。

static int hash(int h) {
	h ^= (h >>> 20) ^ (h >>> 12); // >>> 无符号右移

	return h ^ (h >>> 7) ^ (h >>> 4);
}

1
2
3

static int indexFor(int h, int length) {
	return h & (length - 1);
}

hash() 方法可以保证所求得的 hash 值为正数，HashMap 的底层数组长度总是 2 的 n 次方，在构造函数中存在：capacity <<= 1;这样做总是能够保证 HashMap 的底层数组长度为 2 的 n 次方。当 length 为 2 的 n 次方时，h & (length – 1) 就相当于对 length 取模，从而确保 index 的值一定在 0 ~ length-1 之间。而且速度比直接取模快得多，这是 HashMap 在速度上的一个优化。

实际上，indexFor() 方法中的唯一语句 h & (length - 1) 除了计算下标外还有一个重要作用：加以条件length = 2^n从而均匀分布 table 数据和充分利用空间。如下表:

h	length-1	`h & (length - 1)`	index
0	14	`0000 & 1110`	0
1	14	`0001 & 1110`	0
2	14	`0010 & 1110`	2
3	14	`0011 & 1110`	2
4	14	`0100 & 1110`	4
5	14	`0101 & 1110`	4
6	14	`0110 & 1110`	6
7	14	`0111 & 1110`	6
8	14	`1000 & 1110`	8
9	14	`1001 & 1110`	8
…	…	…	…
14	14	`1110 & 1110`	14
15	14	`1111 & 1110`	14
…	…	…	…
容易看出，当length为15时，只有在下标为 0、2、4、6、8……的空间下保存数据，不曾且也不会为下标为 1、3、5、7……分配数据。不仅增大了碰撞的概率，空间也产生了很大程度上的浪费。

而当 length = 16 时，length – 1 = 15 即 1111，那么进行低位 & 运算时，值总是与原来 hash 值相同；而进行高位运算时，其值等于其低位值。所以说当 length = 2^n 时，不同的 hash 值发生碰撞的概率比较小，这样就会使得数据在 table 数组中分布较均匀，查询速度也较快。

void addEntry(int hash, K key, V value, int bucketIndex) {
	//获取bucketIndex处的Entry
	Entry<K, V> e = table[bucketIndex];
    //将新创建的 Entry 放入 bucketIndex 索引处，并让新的 Entry 指向原来的 Entry
    table[bucketIndex] = new Entry<K, V>(hash, key, value, e);
    //扩容
    if (size++ >= threshold) {
	    resize(2 * table.length);
	}
}

以上源码为“链”的产生过程。
HashMap为数据链添加新节点的方式总是“头插入”。即，总是将新的 Entry 添加到数组的bucketIndex 处。如果 bucketIndex 处已有对象，则新添加的 Entry 对象指向原有的 Entry 对象，从而形成一条 Entry 链。若 bucketIndex 处无对象，即 e = null, 那么新添加的 Entry 就指向了 null，也就不会产生 Entry 链了。

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

;;随着 HashMap 中元素越来越多，发生“碰撞”的该与也就越来越高，链表长度也会越来越长，这样势必会影响 HashMap 的速度，为了保证 HashMap 的效率，系统必须在某个临界点对数组进行扩容处理。这个临界点是“ HashMap 中元素的数量等于 table 数组长度 * 加载因子”，及（size >= threshold）。载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度，它衡量的是一个散列表的空间的使用程度，负载因子越大表示散列表的装填程度越高，反之愈小。对于使用链表法的散列表来说，查找一个元素的平均时间是 O(1+a)，因此如果负载因子越大，对空间的利用更充分，然而后果是查找效率的降低；如果负载因子太小，那么散列表的数据将过于稀疏，对空间造成严重浪费。但是需要注意的是扩容处理是一个极为耗时的操作，因为这存在对原有数据位置重新运算、移动、复制。所以当我们能够最大程度上预知存放元素的个数，就可以一定程度上避免这种耗时操作的发生，从而提高效率。

HashMap 读取（get）数据

public V get(Object key) {
	// 若为null，调用getForNullKey方法返回相对应的value
	if (key == null) {
		return getForNullKey();
	}

	// 根据该 key 的 hashCode 值计算它的 hash 码
	int hash = hash(key.hashCode());
	// 取出 table 数组中指定索引处的值
	for (Entry<K, V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) {
		Object k;
		//若搜索的key与查找的key相同，则返回相对应的value
		if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
			return e.value;
		}
	}

	return null;
}

相较 HashMap 的保存（put）数据，取得（get）数据就显得异常简单了。当取得数据时，先判断键值是否为 null，若是 null 则调用 getForNullKey();返回键值为null 所对应的value。若不为 null，则计算键值在数组中的位置下标 bucketIndex，再遍历table数组 bucketIndex 处的链表，比较每个节点（ Entry）的 hash 值与 key 值。若找到则返回对应的 value ,未找到返回 null 。

有关 HashMap 线程并发

在 HashMap 官方文档描述中提到：

it is unsynchronized and permits nulls。

也就是说，如果多个线程同时访问一个 HashMap，而其中至少一个线程从结构上（指添加或者删除一个或多个映射关系的任何操作）修改了，则必须保持外部同步，以防止对映射进行意外的非同步访问。”仅改变与实例已经包含的键关联的值不是结构上的修改。显而易见，HashMap 并不是线程安全的。

解决方案：

这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap(new HashMap()) 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问。
可以在实例化 HashMap 时对其使用 volatile关键字禁止JVM对 HashMap 的内存优化，使得所有线程都直接对“主内存”的空间进行操作，从而保证 HashMap 的数据同步。除此之外，使用synchronized关键字对操作进行加锁。这样就可以保证 HashMap 的线程安全性。

HashTable

HashTable的数据结构

HashTable 内部实现与 HashMap 几乎相同。同样采用“拉链法”实现散列表，在数据结构上同样使用“Entry 数组”。

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 = new Entry<?,?>[initialCapacity];
    threshold = (int)Math.min(initialCapacity * loadFactor, MAX_ARRAY_SIZE + 1);
}

private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;

		... ...
}

可以看出，构造方法执行过程也几乎与 HashMap 完全相同。Entry 是HashTable 的内部类，与 HashMap 相同。

HashTable 的“读”与“写”

HashTable添加（put）数据

public synchronized V put(K key, V value) {
    // 确保value不为null
    if (value == null) {
        throw new NullPointerException();
    }

    /*
     * 确保key在table[]是不重复的
     * 处理过程：
     * 1、计算key的hash值，确认在table[]中的索引位置
     * 2、迭代index索引位置，如果该位置处的链表中存在一个一样的key，则替换其value，返回旧值
     */
    Entry<?,?> tab[] = table;
    int hash = key.hashCode(); // 计算key的hash值
    int index = (hash & 0x7FFFFFFF) % tab.length; // 计算key的索引位置
    //迭代，寻找该key，替换
    @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;
}

private void addEntry(int hash, K key, V value, int index) {
	modCount++;

   Entry<?,?> tab[] = table;
   if (count >= threshold) {
       //如果容器中的元素数量已经达到阀值，则进行扩容操作
       rehash();

       tab = table;
       hash = key.hashCode();
       index = (hash & 0x7FFFFFFF) % tab.length;
   }

   // 在索引位置处插入一个新的节点
   @SuppressWarnings("unchecked")
   Entry<K,V> e = (Entry<K,V>) tab[index];
   tab[index] = new Entry<>(hash, key, value, e);
   count++;
}

protected void rehash() {
  int oldCapacity = table.length;
    Entry<?,?>[] oldMap = table;

    // 扩容后容量扩大两倍 + 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;

    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;
        }
    }
}

可以看到与 HashMap 不同的是，HashTable中的 put() 方法是有synchronized关键词修饰的。其计算 key 索引地址index 的方式也有所不同，(hash & 0x7FFFFFFF) % tab.length，将 hash 与 0x7FFFFFFF按位与相当于给 hash 取绝对值，再与length进行取模运算。

在这个 rehash() 方法中同时需要将原来 HashTable 中的元素一一复制到新的 HashTable 中，这个过程是比较消耗时间的。这里对阀值啰嗦一下：比如初始值 11、加载因子默认 0.75，那么这个时候阀值 threshold=8，当容器中的元素达到 8 时，HashTable 进行一次扩容操作，容量 = 8 * 2 + 1 =17，而阀值 threshold=17*0.75 = 13，当容器元素再一次达到阀值时，HashTable 还会进行扩容操作，一次类推。

HashTable 取得（get）数据

 public synchronized V get(Object key) {
	Entry<?,?> tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            return (V)e.value;
        }
    }
    return null;
}

分析可见 HashMap get() 方法。唯一不同的是HashTable中的 get() 方法有synchronized关键词修饰。

有关 HashTable线程并发

对 HashTable 进行的绝大多数的方法都有synchronized关键词修饰，这也就使得所有对 HashTable 的操作都是同步的，这样就保证了，在多线程访问HashTable时，不需要开发人员对其进行同步。也就是说，HashTable 是线程安全的。

HashMap 与 HashTable 的区别

HashMap 可以允许存在一个为 null 的 key 和任意个为 null 的 value，但是 HashTable 中的 key 和 value 都不允许为 null。
;;当HashMap 遇到为 null 的键值：
1
2
if (key == null)
return putForNullKey(value);
;;而当 HashTable 遇到 null 的键值:
1
2
3
if (value == null) {
throw new NullPointerException();
}
HashTable 的方法是同步（对数据的操作是同步写入“堆内存”），而 HashMap 的方法不是。这也就意味着，HashTable在性能方面会逊色于HashMap。
HashMap中不再使用HashTable的contains() 方法，取而代之的是，containsValue() 和 containsKey()方法，在语义和实用性上都有了质的提升。
两者的迭代容器不同。HashTable为Enumeration，HashMap为Iterator。

本篇文章与笔者另一篇关于散列表的学习笔记本是同属一篇，现在为了明确其分类将两者分开。

另外，由于笔者写这篇文章时是基于 JDK7 的源码，所以其 HashMap 与
HashTable 的实现方案同为“Entry数组”。后来当我查看 JDK8 的源码时，发现 HashTable仍然是“Entry数组”，但HashMap 似乎更改了实现方案。但由于笔者自己对 “红黑树” 的数据结构不是很了解也就没有再重新写关于新实现方案的分析，以后会更新。

如果您发现了文章中的错误、漏洞以及需要补充的地方，欢迎留言交流。