HashMap 及其类似数据结构 原理分析对比

HashMap简述

HashMap 是数组+ 链表 的数据结构。时间复杂度(理想状态)O(1)。（是数组 查找时间复杂度O(1)，插入时间复杂度O(n)，链表 查找时间复杂度O(n)，插入时间复杂度O(1) 的 中庸选择）

• 链表使用一个next指针维护链表结构的，它的插入和删除的效率比较高，再插入和删除时，不用挪动后面的数据。但是查找每次都得从头结点遍历，所以效率不高
• 数组使用下标维护数据的，所以查找起来，效率会很高。插入和删除，需要移动后面的数据，效率不高。
• 所以，在只需要查找的时候，建议使用数组，而经常需要插入和删除数据，建议使用链表

HashMap主要原理

1、put

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
           boolean evict) {

        Node<K,V>[] tab; Node<K,V> p; int n, i;

    // 1. 若哈希表的数组tab为空，则 通过resize() 创建
    // 所以，初始化哈希表的时机 = 第1次调用put函数时，即调用resize() 初始化创建
    // 关于resize（）的源码分析将在下面讲解扩容时详细分析，此处先跳过
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

    // 2. 计算插入存储的数组索引i：根据键值key计算的hash值 得到
    // 此处的数组下标计算方式 = i = (n - 1) & hash，同JDK 1.7中的indexFor（），上面已详细描述

    // 3. 插入时，需判断是否存在Hash冲突：
    // 若不存在（即当前table[i] == null），则直接在该数组位置新建节点，插入完毕
    // 否则，代表存在Hash冲突，即当前存储位置已存在节点，则依次往下判断：a. 当前位置的key是否与需插入的key相同、b. 判断需插入的数据结构是否为红黑树 or 链表
    if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);  // newNode(hash, key, value, null)的源码 = new Node<>(hash, key, value, next)

else {
    Node<K,V> e; K k;

    // a. 判断 table[i]的元素的key是否与 需插入的key一样，若相同则 直接用新value 覆盖 旧value
    // 判断原则：equals（）
    if (p.hash == hash &&
        ((k = p.key) == key || (key != null && key.equals(k))))
        e = p;

    // b. 继续判断：需插入的数据结构是否为红黑树 or 链表
    // 若是红黑树，则直接在树中插入 or 更新键值对
    else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); ->>分析3

    // 若是链表,则在链表中插入 or 更新键值对
    // i.  遍历table[i]，判断Key是否已存在：采用equals（） 对比当前遍历节点的key 与 需插入数据的key：若已存在，则直接用新value 覆盖 旧value
    // ii. 遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据
    // 注：新增节点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树
    
    else {
        for (int binCount = 0; ; ++binCount) {
            // 对于ii：若数组的下1个位置，表示已到表尾也没有找到key值相同节点，则新建节点 = 插入节点
            // 注：此处是从链表尾插入，与JDK 1.7不同（从链表头插入，即永远都是添加到数组的位置，原来数组位置的数据则往后移）
            if ((e = p.next) == null) {
                p.next = newNode(hash, key, value, null);

                // 插入节点后，若链表节点>数阈值，则将链表转换为红黑树
                if (binCount >= TREEIFY_THRESHOLD - 1) 
                    treeifyBin(tab, hash); // 树化操作
                break;
            }

            // 对于i
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                break;

            // 更新p指向下一个节点，继续遍历
            p = e;
        }
    }

    // 对i情况的后续操作：发现key已存在，直接用新value 覆盖 旧value & 返回旧value
    if (e != null) { 
        V oldValue = e.value;
        if (!onlyIfAbsent || oldValue == null)
            e.value = value;
        afterNodeAccess(e); // 替换旧值时会调用的方法（默认实现为空）
        return oldValue;
    }
}

++modCount;

// 插入成功后，判断实际存在的键值对数量size > 最大容量threshold
if (++size > threshold)
    resize();

afterNodeInsertion(evict);// 插入成功时会调用的方法（默认实现为空）
return null;

}

• 首次table数组为null，调用resize方法，生成一个 默认16 大小的数组
• 对 Entry（Node） key的hashCode()做hash，并计算在储蓄数组中的index
• 存储时，判断hash冲突，如果当前index没有值（即当前table[i] == null），直接存value。
• 否则，代表hash冲突。
  • 1、如果当前key与需存储key相同（equals），覆盖当前value。
  • 2、判断存储的数据是红黑树 或 链表
• 若是链表,则在链表中插入 or 更新键值对
  • 遍历table[i]，判断Key是否已存在：采用equals（） 对比当前遍历节点的key 与 需插入数据的key：若已存在，则直接用新value 覆盖 旧value
  • 遍历完毕后仍无发现上述情况，则直接在链表尾部插入数据
  • 注：新增节点后，需判断链表长度是否>8（8 = 桶的树化阈值）：若是，则把链表转换为红黑树

2、get

public V get(Object key) {
    Node<K,V> e;
    // 1. 计算需获取数据的hash值
    // 2. 通过getNode（）获取所查询的数据
    // 3. 获取后，判断数据是否为空
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

 
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;

    // 1. 计算存放在数组table中的位置
    if ((tab = table) != null && (n = tab.length) > 0 &&
    (first = tab[(n - 1) & hash]) != null) {

    // 4. 通过该函数，依次在数组、红黑树、链表中查找（通过equals（）判断）
    // a. 先在数组中找，若存在，则直接返回
    if (first.hash == hash && // always check first node
        ((k = first.key) == key || (key != null && key.equals(k))))
        return first;

    // b. 若数组中没有，则到红黑树中寻找
    if ((e = first.next) != null) {
        // 在树中get
        if (first instanceof TreeNode)
            return ((TreeNode<K,V>)first).getTreeNode(hash, key);

        // c. 若红黑树中也没有，则通过遍历，到链表中寻找
        do {
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        } while ((e = e.next) != null);
    }
}
    return null;
}

• bucket里查找节点，命中返回
• 如果有冲突，则通过key.equals(k)去查找对应的entry
  若为树，则在树中通过key.equals(k)查找，O(logn)；
  若为链表，则在链表中通过key.equals(k)查找，O(n)。

3、resize
存储键值时，发现容量不足，需要扩容，生成一个当前 2倍 的新数组。

/**
 * 分析4：resize（）
 * 该函数有2种使用情况：1.初始化哈希表 2.当前数组容量过小，需扩容
 */
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 扩容前的数组（当前数组）
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 扩容前的数组的容量 = 长度
int oldThr = threshold;// 扩容前的数组的阈值
int newCap, newThr = 0;

// 针对情况2：若扩容前的数组容量超过最大值，则不再扩充
if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }

    // 针对情况2：若无超过最大值，就扩充为原来的2倍
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // 通过右移扩充2倍
}

// 针对情况1：初始化哈希表（采用指定 or 默认值）
else if (oldThr > 0) // initial capacity was placed in threshold
    newCap = oldThr;

else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

// 计算新的resize上限
if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
              (int)ft : Integer.MAX_VALUE);
}

threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

if (oldTab != null) {
    // 把每个bucket都移动到新的buckets中
    for (int j = 0; j < oldCap; ++j) {
        Node<K,V> e;
        if ((e = oldTab[j]) != null) {
            oldTab[j] = null;

            if (e.next == null)
                newTab[e.hash & (newCap - 1)] = e;
            else if (e instanceof TreeNode)
                ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);

            else { // 链表优化重hash的代码块
                Node<K,V> loHead = null, loTail = null;
                Node<K,V> hiHead = null, hiTail = null;
                Node<K,V> next;
                do {
                    next = e.next;
                    // 原索引
                    if ((e.hash & oldCap) == 0) {
                        if (loTail == null)
                            loHead = e;
                        else
                            loTail.next = e;
                        loTail = e;
                    }
                    // 原索引 + oldCap
                    else {
                        if (hiTail == null)
                            hiHead = e;
                        else
                            hiTail.next = e;
                        hiTail = e;
                    }
                } while ((e = next) != null);
                // 原索引放到bucket里
                if (loTail != null) {
                    loTail.next = null;
                    newTab[j] = loHead;
                }
                // 原索引+oldCap放到bucket里
                if (hiTail != null) {
                    hiTail.next = null;
                    newTab[j + oldCap] = hiHead;
                }
            }
        }
    }
}
    return newTab;
}

总结

HashMap 采用数组和链表的方式解决hash冲突，（Java 8 添加红黑树）。允许存储null。

hashmap流程图

参考：

• HashMap源码分析

动态扩容问题详见： HashMap扩容

扩展

LinkedHashMap

基本和HashMap实现类似，多了一个链表来维护元素插入的顺序，因此维护的效率会比HashMap略低。但是因为有链表的存在，遍历效率会高于HashMap。
get()操作后，会把当前数据移动到链表尾部。所以基于这个属性，可以实现 Lru缓存

详见：

• LinkedHashMap

ConCurrentHashMap

结构图

线程安全，而且采用分段锁的方式进行数据同步，因此相对于Hashtable来说，效率要高。但是因为引入了段的概念，所以ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部，因此效率会低于HashMap。不过在多线程情况下，这种性能的牺牲换取数据安全是非常值得的。因此在多线程的情况下应该首选ConcurrentHashMap。（HashMap ConCurrentHashMap 对比）

详见：ConCurrentHashMap

SparseArray

private int[] mKeys;//int 类型key数组
private Object[] mValues;//value数组


public SparseArray() {
    this(10);
}

public SparseArray(int initialCapacity) {
    if (initialCapacity == 0) {
        mKeys = EmptyArray.INT;
        mValues = EmptyArray.OBJECT;
    } else {
        mValues = ArrayUtils.newUnpaddedObjectArray(initialCapacity);
        mKeys = new int[mValues.length];
    }
    mSize = 0;
}

SparseArray 如果不设置置顶容量大小，会默认初始一个 容量10 的大小内容。

内部通过 两个数组 来存储数据，一个存储key，一个存储value。key 只支持int类型，避免了装箱

put get 时，都会使用二分查找。所以在数据量大的情况下性能并不明显，将降低至少50%

扩容 当currentSize(当前存储的值的个数)小于等于4的时候，扩容至8，否则扩容至两倍的currentSize

所以用 SparseArray 代替 HashMap 最好是：

• 数据量不大，最好在千级以内
• key必须为int类型，这中情况下的HashMap可以用SparseArray代替

ArrayMap

public class ArrayMap<K, V> extends SimpleArrayMap<K, V> implements Map<K, V> {
MapCollections<K, V> mCollections;  


int[] mHashes;
Object[] mArray;

ArrayMap继承自SimpleArrayMap实现了Map接口。ArrayMap内部是两个数组（都为 空数组），一个存放hash值，一个存放键值对 key value。

put
首先就是判段key是否null，是null，hash值直接置为0，如果不为null，通过Obejct的hashCode()方法计算出hash值。然后通过indexfOf方法计算出index的值。indexfOf 内部则是使用二分查找。

扩容

• 如果我们的osize(已经存储的多少value个数)大于等于两倍的BASE_SIZE(常量为4)我们就在原来osize的基础上扩容0.5倍

• 如果我们的osize小于8(两个BASE_SIZE)并且大于4（一个BASE_SIZE），我们将数组扩容到8，否则我们将数组大小扩容到4

ArrayMap 与 HashMap 对比：

• 插入基于二分查找，效率不如HashMap
• 比HashMap占用内存少，更省空间， 时间换空间

选择使用：

• 在数据量小的时候一般认为1000以下，当你的key为int的时候，使用 SparseArray 确实是一个很不错的选择，内存大概能节省30%，相比用HashMap，因为它key值不需要装箱，所以时间性能平均来看也优于HashMap，建议使用
• ArrayMap相对于SparseArray，特点就是key值类型不受限，任何情况下都可以取代HashMap，但是通过研究和测试发现，ArrayMap的内存节省并不明显，也就在10%左右，但是时间性能确是最差的，当然了，1000以内的如果key不是int 可以选择 ArrayMap