数据结构之【 HashMap 】

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {...}

// LinkedHashMap.Entry与HashMap.Node是继承关系
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);
    }
}

/**
 * @param hash            key的hash值
 * @param key             the key
 * @param value           the value to put
 * @param onlyIfAbsent    true时，表示不修改已存在的值
 * @param evict           false时，表示是在初始化HashMap
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // table数组为空，需要resize()
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 确定key要插入的数组位置的元素p，如果不存在则直接放入，(n - 1) & hash==hash%n ，前者效率更高
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 插入的位置元素已存在，则说明发生了hash碰撞（1.key是一样的，覆盖value,2,key不一样，存储在链表或者树中） 
    else {
        Node<K,V> e; K k;
        // 检查数组节点p是否和新插入的节点相等（比较key） 
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果不相等
        // 判断数组节点是否为树节点，如果是则按照树状节点规则插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 不是，则按照链表节点规则插入
        else {
            // 死循环，通过break来终止，这里为寻找下一个链表节点的过程
            for (int binCount = 0; ; ++binCount) {
                // 判断当前节点的下一个节点是null的，则占位，如果发现需要转为树结构，则转换，binCount统计链表长度，从0开始
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
               // 下一个节点不是空，则判断是否和新节点相等（key比较），相等则该位置为要找的位置
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 下一个节点变为当前节点，继续循环
                p = e;
            }
        }
        // 要放入的位置确定后，判断位置上的元素是否存在，如果存在则判断是否替换
        if (e != null) { 
            V oldValue = e.value;
            // 满足替换条件才替换
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 判断是否需要扩容
    if (++size > threshold)
        resize();
    // 插入后的后续处理，HashMap默认=false,不需要
    afterNodeInsertion(evict);
    return null;
}

p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	// 从数组中获取对应位置元素不为null则继续查找
	if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
		// 根节点就是要找的节点，则返回
		if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
			return first;
		// 不是则判断根节点类型
		if ((e = first.next) != null) {
			// 树状节点则按照树结构去查找
			if (first instanceof TreeNode)
			return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			do {
				// 不是则按照列表结构查找
				if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))
				return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

final void treeifyBin(Node<K,V>[] tab, int hash) {
	int n, index; Node<K,V> e;
	// 未达到树状结构的最少容量时(默认64)，只扩容不转换
	if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
		resize();
	// 转换
	else if ((e = tab[index = (n - 1) & hash]) != null) {
		TreeNode<K,V> hd = null, tl = null;
		do {
			TreeNode<K,V> p = replacementTreeNode(e, null);
			if (tl == null)
				hd = p;
			else {
				p.prev = tl;
				tl.next = p;
			}
			tl = p;
		} while ((e = e.next) != null);
		if ((tab[index] = hd) != null)
			hd.treeify(tab);
	}
}

for (String key : arr2) {
    System.out.println(String.format("%s\tsize=16,index=%s \t ", key, hash(key) % 16));
}
-------------------------------------------------------
cg80 size=16,index=2
lo8u size=16,index=2
pqdi size=16,index=2
bbam size=16,index=2
hhc5 size=16,index=2
pnem size=16,index=2
u955 size=16,index=2
p4z7 size=16,index=2
phr0 size=16,index=2

Map<String, Integer> map1 = new HashMap<>(16, 1);
for (String key : arr1) {
map1.put(key, 0);
}
Map<String, Integer> map2 = new HashMap<>(16, 1);
for (String key : arr2) {
map2.put(key, 0);
}

链表内存验证

for (String key : arr4) {
    System.out.println(String.format("%s\t size=32,index=%s \t", key, hash(key) % 32));
}
-------------------------------------------------------
cg80     size=32,index=18     
lo8u     size=32,index=18     
pqdi     size=32,index=18     
bbam     size=32,index=2     
hhc5     size=32,index=2     
pnem     size=32,index=18     
u955     size=32,index=18     
p4z7     size=32,index=18     
phr0     size=32,index=2     
suv8     size=32,index=18     
u4pu     size=32,index=18     
p63n     size=32,index=18     

Map<String, Integer> map3 = new HashMap<>(16, 1);
for (String key : arr3) {
    map3.put(key, 0);
}


Map<String, Integer> map4 = new HashMap<>(16, 1);
for (String key : arr4) {
    map4.put(key, 0);
}

for (String key : arr6) {
    System.out.println(String.format("%s\t size=64,index=%s", key, hash(key) % 64));
}
-------------------------------------------------------
cg80     size=64,index=50
lo8u     size=64,index=50
pqdi     size=64,index=50
bbam     size=64,index=2
hhc5     size=64,index=2
pnem     size=64,index=18
u955     size=64,index=50
p4z7     size=64,index=50
phr0     size=64,index=2
suv8     size=64,index=18
u4pu     size=64,index=18
p63n     size=64,index=18
jaua     size=64,index=50
zth9     size=64,index=50
maxe     size=64,index=50
wymp     size=64,index=50

Map<String, Integer> map5 = new HashMap<>(16, 1);
for (String key : arr5) {
    map5.put(key, 0);
}
Map<String, Integer> map6 = new HashMap<>(16, 1);
for (String key : arr6) {
    map6.put(key, 0);
}

树状数据转换，只针对index=50这个节点，红黑树图示

红黑树内存验证

常见问题

为什么使用HashMap

• HashMap是非synchronized的键值对存储结构，速度快，效率高
• HashMap支持键和值为null存储
• HashMap不保证元素的顺序

HashMap中null的使用

• key可以为null,但只能有一个，index=0,后续会覆盖前者
• value可以为nul，数量不限制

查找效率

• 在数组中 O(1)
• 在链表中 O(N)
• 在树中 O(log N)

为什么采用红黑树而不是AVL树（平衡二叉树）？

• 区别
  • 红黑树特点
    • 每个结点要么是红的要么是黑的。
    • 根结点是黑的。
    • 每个叶结点（叶结点即指树尾端NIL指针或NULL结点）都是黑的。
    • 如果一个结点是红的，那么它的两个儿子都是黑的。
    • 对于任意结点而言，其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。
  • 平衡二叉树特点
    • 它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树
• 原因
  • 二者在查找是都是通过二分法查找，效率差不多
  • 插入与删除是红黑树效率较高，因为AVL树要求绝对的平衡，为保证绝对平衡，进行旋转的次数较多

存在问题

• 在自动调整大小时存在线程安全问题
• 在ForEach遍历时不能删除元素，正确方式为采用Iterator

为什么使用包装类作为键而不是基本类型

• 因为包装类重写了hashCode和equals方法，保证了键的不变性，在查询元素时能查找到正确的元素对象

使用对象作为键需要注意什么

• 注意保证键的不变性，即对象的hashCode和equals方法返回值是确定的

多线程时如何存储

• 使用HashTable或者ConcurrentHashMap
• HashTable是HashMap的synchronized版本，不支持null的键或者值，底层是数组+链表，没有红黑树。ConcurrentHashMap是HashTable的改进版本
• ConcurrentHashMap JDK7之前采用锁分离技术，默认将Hash表分为16段，对每段单独加锁，支持16个线程同时访问，支持读取并发，采用fail-fast迭代器，迭代中删除元素抛异常，JDK8之后使用synchronized+cas技术。原因在于分段锁浪费空间且实际中锁竞争情况出现很少。
• HashTable是采用锁表技术，对每个操作都加锁保证安全，同一时刻只有一个线程能访问，效率低下，大部分情况可以使用ConcurrentHashMap替代，未采用fail-fast迭代器

扩容为什么是2的整数倍

• 保证Node的hash尽量的一致性
• 当n扩容后仍保持2^m时，Node落地点的下标

  i=(n - 1) & hash

  会更优化

为什么负载因子0.75，链表转红黑树阈值=8，红黑树转链表=6

• 作为一般规则，默认的负载因子(0.75)提供了良好的性能权衡时间和空间成本。值越高，空间开销越小，但增加查找成本
• 阈值=8，是因为Hash下标的落地点遵循泊松分布，在负载因子=0.75前提下，忽略计算方差，λ=0.5时，阈值=8的概率为0.00000006，再高概率小于百万分之一，此时性能已经满足需求
• 阈值=6，是因为=8时链表转为树，再由树转链表这阈值一定小于8，所以=6

使用的是头插法还是尾插法

JDK7之前都是头插法，JDK8之后都是尾插法。因为JDK7中HashMap使用的是数组+链表的数据结构，使用头插法效率高，但是容易出现逆序和链表闭环的问题。JDK8中HashMap使用的是数组+链表+红黑树的数据结构，使用尾插法效率更高。