HashMap 涉及的技术点非常多, 典型的数据结构和算法有机结合, JDK 对 HashMap 优化变化中不断权衡时间复杂和空间复杂度.
一. 存储结构
1.JDK1.8 之前 HashMap = 数组(O(1))+ 单向链表(O(n))
2.JDK1.8 之后 HashMap = 数组(O(1))+ 单向链表(O(n))+ 红黑树(O(log n)
HashMap 结构图. PNG
关于结构的几个关键数字:
1. 默认初始化数组容量大小是 16.
2. 数组扩容刚好是 2 的次幂.
3. 默认的加载因子是 0.75.
4. 链表长度超过 8 时将链表转化成红黑树结构.
5. 红黑树节点数减少到 6 的时候退化成链表.
以上几个数字关系, 又为什么是上边的几个数字接下来一个个分析.
二. 操作原理
1. put 储存流程
1计算桶的位置, 根据 key 的 hashcode 求出 hash 值, 位置 index = hash%length.
2判断是否达到扩容条件, threshold=DEFAULT_INITIAL_CAPACITY * loadFactor(16*0.75=12)大于这个阀门值就需要扩容, 否则下一步.
3判断桶位置是否为空, 如果为空直接在数据插入数据. 如果不为空, 下一步.
4判断是链表还是红黑树, 链表是否到达转化红黑树, 当前链表节点数<=8, 插入节点; 如果是红黑树插入节点, 否则下一步.
5链表转化成红黑树, 插入节点.
6插入节点后计算当前 size 是否需要扩容, 如果大于阀门值需要扩容 resize.
- /**
- * Implements Map.put and related methods
- *
- * @param hash hash for key
- * @param key the key
- * @param value the value to put
- * @param onlyIfAbsent if true, don't change existing value
- * @param evict if false, the table is in creation mode.
- * @return previous value, or null if none
- */
- final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
- boolean evict) {
- Node<K,V>[] tab; Node<K,V> p; int n, i;
- if ((tab = table) == null || (n = tab.length) == 0)
- n = (tab = resize()).length;
- if ((p = tab[i = (n - 1) & hash]) == null)
- tab[i] = newNode(hash, key, value, null);
- else {
- Node<K,V> e; K k;
- 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 {
- for (int binCount = 0; ; ++binCount) {
- if ((e = p.next) == null) {
- p.next = newNode(hash, key, value, null);
- if (binCount>= TREEIFY_THRESHOLD - 1) // -1 for 1st
- treeifyBin(tab, hash);
- break;
- }
- if (e.hash == hash &&
- ((k = e.key) == key || (key != null && key.equals(k))))
- break;
- p = e;
- }
- }
- if (e != null) { // existing mapping for key
- V oldValue = e.value;
- if (!onlyIfAbsent || oldValue == null)
- e.value = value;
- afterNodeAccess(e);
- return oldValue;
- }
- }
- ++modCount;
- if (++size> threshold)
- resize();
- afterNodeInsertion(evict);
- return null;
- }
以上是 JDK1.8 的 HashMap 的 get 调用关键方法源码.
2. get 获取过程
1计算桶的位置, 根据 key 的 hashcode 求出 hash 值, 位置 index = hash%length.
2无论是数组, 链表还是红黑树, for 循环判断 hash 值冲突就比对 key 是否相等, 相等就返回对应的 value.
- /**
- * Implements Map.get and related methods
- *
- * @param hash hash for key
- * @param key the key
- * @return the node, or null if none
- */
- final Node<K,V> getNode(int hash, Object key) {
- Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
- if ((tab = table) != null && (n = tab.length)> 0 &&
- (first = tab[(n - 1) & hash]) != null) {
- if (first.hash == hash && // always check first node
- ((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;
- }
以上是 JDK1.8 的 HashMap 的 put 调用关键方法源码.
三. 数据结构和算法思考
1. 为什么选择数组和链表结构?
1数组内存连续块分配, 效率体现查询更快. HashMap 中用作查找数组桶的位置, 利用元素的 key 的 hash 值对数组长度取模得到.
2链表效率体现增加和删除. HashMap 中链表是用来解决 hash 冲突, 增删空间消耗平衡.
扩展: 为什么不是 ArrayList 而是使用 Node<K,V>[] tab? 因为 ArrayList 的扩容机制是 1.5 倍扩容, 而 HashMap 扩容是 2 的次幂.
2. 为什么扩容是 2 次幂, 根据 key 的 hashcode 再求 hash 值?
1key 的 hash 值计算
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
代码意思是 hash = hashcode 的高 16 位异化低 16 位, 而不是直接 hashcode.
2计算桶的位置代码
index = (n - 1) & hash
思想:
一是, 为了减少 hash 冲突使用 hash%length 计算, 求模计算保证了得到的结果一定在 0-length 范围之内.
二是, 为了提高运算速度, 模运算比不上位运算, 当 n 是 2 的次幂才满足 hash%length == (n-1)&hash.
确定公式中 (n-1) 符合最优等式, 剩下考虑 hash 值的最优, hash 值这个因子考虑影响结果尽可能不冲突.
因为计算速度体现在位运算上, 条件 n 是 2 的次幂, 那么 n-1 的换算成二进制前边都是连续的 0, 后边都是连续的 1,. 比如 n=16, 则 n-1=15,15 的二进制 1111.hash & 1111 = 只要关注的 hash 的二进制的最后四位数进行 & 运算.
(n-1)& length.PNG
如上图, 最终会与 15 的二进制进行 1111 四位运算, 如果与 key.hashcode 进行与运算的话, 只要 key 的 hashcode 最后四位为 0000 前边无论是什么都没关系, 这样出现相同值的概率高很多. 所以, 引入 hashcode 先高低 16 位进行异或运算, 减少 hash 冲突.
扩展:
hashcode 与 equals 相等判断对比:
两个 key 的 hashcode 相等, key 不一定 equals.
两个 key 的 equals,hashcode 一定相等.
3. 为什么加载因子为 0.75, 链表长度大于 8 转成红黑树?
思想:
上边问题不是两个独立问题而是相互相关, 目的尽量减少冲突前提提高空间利用率和减少查询成本的折中.
加载因子决定了 HashMap 的扩容的阀门值, 如果桶是 16, 那么扩容值 16* 0.75=12, 也就是 12 的时候就要考虑扩容, 还有 4 个没有被利用到, 牺牲的空间. 如果加载因子是 1, 空间利用率高, 但是查询速度变慢.
原理:
权衡依据是以上情况符合泊松分布 (一种统计与概率学里常见到的离散概率分布, 适合于描述单位时间(或空间) 内随机事件发生的次数), 用 0.75 作为加载因子, 每个碰撞位置的链表长度超过8个概率非常低, 少于千万分之一.
源码说明:
- * Because TreeNodes are about twice the size of regular nodes, we
- * use them only when bins contain enough nodes to warrant use
- * (see TREEIFY_THRESHOLD). And when they become too small (due to
- * removal or resizing) they are converted back to plain bins. In
- * usages with well-distributed user hashCodes, tree bins are
- * rarely used. Ideally, under random hashCodes, the frequency of
- * nodes in bins follows a Poisson distribution
- * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
- * parameter of about 0.5 on average for the default resizing
- * threshold of 0.75, although with a large variance because of
- * resizing granularity. Ignoring variance, the expected
- * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
- * factorial(k)). The first values are:
- *
- * 0: 0.60653066
- * 1: 0.30326533
- * 2: 0.07581633
- * 3: 0.01263606
- * 4: 0.00157952
- * 5: 0.00015795
- * 6: 0.00001316
- * 7: 0.00000094
- * 8: 0.00000006
- * more: Less than 1 in ten million
扩展:
为什么不一开始选择红黑树?
红黑树近乎于平衡二叉树, 结构适合均匀分布节点, 减少树的深度像链表长度情况. 原因主要是插入效率上, 红黑树增加节点很可能需要进行左旋, 右旋, 着色操作, 这些时间效率并没有链表形式高.
4.HashMap 的 key 选择
1)选择不可变的对象, 比如字符串或 int 类型.
2)如果要用一个自定义实体类作为 key:
1类添加 final 修饰符, 保证类不被继承.
2保证所有成员变量必须私有, 并且加上 final 修饰.
3不提供改变成员变量的方法, 包括 setter.
4通过构造器初始化所有成员, 进行深拷贝(deep copy).
5.String 类中的 hashcode 计算
- public int hashCode() {
- int h = hash;
- if (h == 0 && value.length> 0) {
- char val[] = value;
- for (int i = 0; i < value.length; i++) {
- h = 31 * h + val[i];
- }
- hash = h;
- }
- return h;
- }
哈希计算公式: s[0]31^(n-1) + s[1]31^(n-2) + ... + s[n-1]
四. 横向扩展
1.HashMap 出现线程问题
1多线程扩容, 引起的死循环问题(jdk1.8 中, 死循环问题已经解决).
2多线程 put 的时候可能导致元素丢失
3put 非 null 元素后 get 出来的却是 null
2. 使用线程安全 Map
1HashMap 并不是线程安全, 要实现线程安全可以用 Collections.synchronizedMap(m)获取一个线程安全的 HashMap.
2CurrentHashMap 和 HashTable 是线程安全的. CurrentHashMap 使用分段锁技术, 要操作节点先获取段锁, 在修改节点.
3.Android 提倡使用 ArrayMap
1ArrayMap 数据结构是两个数组, 一个存放 hash 值, 另一个存放 key 和 value.
2根据 key 的 hash 值利用二分查找在 hash 数组中找出 index.
3根据 index 在 key-value 数组中对应位置查找, 如果不相等认为冲突了, 会以 key 为中心, 分别上下展开, 逐一查找.
优势, 数据量少时 (少于 1000) 相比 HashMap 更节省内存. 劣势, 删除和插入时效率要比 HashMap 要低.
来源: http://www.jianshu.com/p/bbb06bd75db5