HashMap与HashTable区别以及原理解析

前言

需要知道的是，HashMap在Java8里发生了比较大的变化。在Java8中，table的桶（bucket）中，每个桶跟之前一样，是维护一个链表。但是如果链表大小超过阈值（TREEIFY_THRESHOLD=8），链表就会被改造为红黑树结构。
这是因为，在大量hash碰撞下，Map就会被弱化为类似链表的结构（全部存在一个bucket中），这样会大大降低性能。在超过阈值以后，改为红黑树的方式，可以提高查找性能。

本文最下方还介绍了 LinkedHashMap 和 TreeMap 的区别。

Map整体结构

Map通常被包含在集合框架里，但是Map并不继承自 Collection 接口，最底层接口是Map。
类的继承结构可以参考下图：

Map整体结构图

HashMap和HashTable区别

最主要区别在于线程安全，HashMap不是线程安全的，而HashTable是线程安全的。
hashtable内部添加了synchronized关键字来确保线程同步。而HashMap没有，因此性能上来说，HashMap会相对高一些。
我们平时使用一般情况下是用HashMap，而如果要在多线程情况下使用HashMap，可以使用Collections.synchronizedMap()来获取一个线程安全的集合。

Collections.synchronizedMap() 的实现原理是，Collections内部定义了一个SynchronizedMap的内部类，这个类实现了Map接口，使用synchronized关键字在复写的方法中实现线程安全，然后操作传入的实例对象。

//以下是Collections.SynchronizedMap 内部的put方法实现
public V put(K key, V value) {
    synchronized (mutex) {return m.put(key, value);}
}

HashMap可以使用null作为key，而HashTable不允许这样做。
虽然HashMap支持null作为key，但一般不建议这样做。因为这样做比较坑╮(╯▽╰)╭。另外HastTable已经不建议在代码中使用，如果需要线程安全的场景，建议使用ConcurrentHashMap
顺便说一下，如果HashMap以null作为key的话，Entry节点对象总是存在table数组的第一个节点上
HashMap是对Map接口的实现，HashTable在实现了Map接口的同时，继承了Dictionary抽象类。
这俩都实现了 Map Coneable 和 Serializable 接口，但是没有实现Collection接口。
构造器有两个可选参数：int initialCapacity, float loadFactor。分别表示初始容量 和，加载因子。
两个默认的加载因子都是0.75。如果容量达到荷载因子*size的话，就要进行扩容(resize)，扩容的同时要重新计算每个元素在新数组中的位置，因此性能开销较大。
HashMap的初始容量是16，扩容时按2的指数幂扩容。
HashTable的初始容量是11，扩容时按2的指数幂+1扩容
而关于加载因子为什么选用0.75

Hash表为解决冲突，可以使用开放地址法和链地址法来解决，Java的HashTable采用了链地址法，即数组+链表。荷载因子就是一个特别重要的参数，应该严格限制在0.7~0.8以下。超过0.8查表时CPU缓存不命中概率将按照指数级上升，严重降低性能。hash表的平均查找长度，是关于荷载因子a的函数

两者计算hash的方法不同
都是根据key进行hash运算后确定存储地址index。
HashTable计算hash是用key的hash对数组长度进行取模运算

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

而hashMap为了减少Hash碰撞概率，进行了二次hash
以下是源码实现。注意jdk1.7和jdk1.8的实现方法不一样

//JDK1.7 方法一：
final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }

        h ^= k.hashCode();

        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
}

//JDK1.8 方法一：
static final int hash(Object key) {   //jdk1.8
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的
     return h & (length-1);  //第三步 取模运算
}

这里要注意，为什么这里需要将高位数据移位到低位进行异或运算呢？
这是因为有些数据计算出的哈希值差异主要在高位，而 HashMap 里的哈希寻址是忽略容量以上的高位的，那么这种处理就可以有效避免类似情况下的哈希碰撞。

为了分布均匀，我们首先想到的就是把hash值对数组长度取模运算，这样元素的分布相对均匀。但是取模运算对于性能消耗还是比较大的。
在HashMap中是这样做的，调用方法二来计算index。
这个方法非常巧妙。它通过h & (table.length -1)得到该对象的保存位，而HashMap低层数组的长度总是2的n次方，这是HashMap在速度上的优化。而当length总是等2的n次方时，h & (table.length -1) 运算等价于对length取模，也就是h%table.length，但是&操作更有效率。

HashMap和HashTable都是 使用链地址法解决Hash碰撞，使用 数组+链表 的方式存储。（JDK1.8中链表改为了红黑树）
如果hash碰撞，则会用equals()比较key到底是否相同。相同则覆盖，如果不相同，则会放到相同的bukectIndex下面，用链表存储下一个元素的位置。
Entry是HashMap的一个静态内部类，实现一个链表结构，保存了之前的Enrty对象为next元素。
以下为JDK1.7的Map部分源码。

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

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }
}

//put源码 JDK1.7
public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            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;
    }

//校验并扩容
void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

//创建Entry节点，相同bucketIndex创建为链表节点
void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

HashMap和HashTable的实现原理

resize()方法
由第6点可以看到，在addEntry()方法内，每次执行createEntry()之前，都需要校验一遍是否需要扩容。
(size >= threshold) && (null != table[bucketIndex])
如果size达到了临界值，并且当前要添加的节点不为null。就要进行扩容。
具体过程为：
先创建一个容量为table.length*2（也就是2次方翻倍）的新table，修改临界值。然后把HashMap里的所有元素根据新的length重新计算index放入新的table中。
这里要注意，是用 每个元素的hash重新计算Index，而不是简单的把原table的index放到新table中。（因为计算index时，是根据length长度均匀分布的）所以resize()是比较消耗性能的操作。如果在创建map时能大概预见到大小，那么设置一个相对大点的初始容量是一个不错的选择。
resize()源码就不放了。JDK1.8有新实现
hash() 和 indexFor()
hash()是方法是为了对key.hashCode()进行二次散列，以获得更好的散列值，减少碰撞概率。
indexFor()是根据散列值计算出存储在table中的下标，与table.length取模。均匀分布。

LinkedHashMap 和 TreeMap

这两种Map都可以保证某种顺序，但是实现原理是不同的。

LinkedHashMap

提供的是遍历顺序符合插入顺序，它的实现是通过为Entry（键值对）维护一个双向链表。
部分源码如下：

/**
 * HashMap.Node subclass for normal LinkedHashMap entries.
 */
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

TreeMap
它的整体顺序是由键来确定的，通过 Comparator 或 Comparable（自然顺序）来决定。

最后说一下HashSet

内部实现是一个HashMap，只不过value是一个固定对象。
HashSet部分源码如下

private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

参考资料:
HashMap原理解析(较全面)
HashMap与HashTable实现原理浅析
 Java8系列之重新认识HashMap(深度解析)