在 Java 语言中使用的最多的数据结构大概右两种, 第一种是数组, 比如 Array,ArrayList, 第二种链表, 比如 ArrayLinkedList, 基于数组的数据结构特点是查找速度很快, 时间复杂度为 O(1), 但是删除的速度比较慢, 因为每次删除元素的时候需要把后面的所有的元素都要相应的往前移动一位, 最坏的情况删除第一个元素, 时间复杂度为 O(n). 基于链表实现的数据结构的特点是删除的速度比较快, 但是查找的速度比较慢, 每次查找数据的时候都需要从链表头部开始往下遍历, 链表查找最坏时间是 O(n).HashMap 就整合和了数组和链表的有点而设计出来的, 它的查找速度为 O(1) + O(a),a 为链表长度, 事实上 hashMap 的 hash 算法能够很好的避免了在插入数据的碰撞问题, 所以链表的长度基本不会很长, 所以 hashMap 的查找速度还是很快的. 一般地, 我们平衡一种结构的性能是看平均时间复杂度的, 在 jdk1.8 以前 hashMap 在最糟糕的情况下查找的时间复杂度为 O(1) +O(n) ,n 为数据的大小. 在 jdk1.8 时 sun 公司对 hashMap 进行了优化, hashMap 的存储结构由原来的数组 + 链接的结构改成 数组 + 链表 + 红黑树的形式. 时间复杂度由 O(1) + O(n) 降为 O(1) + O(logn). 下面的源码都是基于 jdk1.8 的.
HashMap 中几个重要的参数:
1,threshold : 数组的大小, 默认长度为 16, 可以在构造函数中指定初始化大小, 但是必须是 2 的 n 次方, 具体原因在下面将会说到. 注意: 该值是指数组的大小, 并不是指 HashMap 中已经存放了的数据量, 存放的数据的大小总是小于等于 threshold * loadFactor.
2,loadFactor: 负载因子, 默认值为 0.75. 当 HashMap 中存储的数据大于阈值 (threshold * loadFactor) 时, threshold 会进行翻倍, 执行 resize 方法, 对原数组中所有的元素进行一次重新 hash 计算, 根据 hash 计算得出的下表放在新的数组中. 负载因子的设计是为了减少在 put 操作时发生的碰撞, 因为当我们 put 的数据越来越多的时候, 数组中空的位置也会越来越少, 那么发生碰撞的概率也随之增大, 碰撞的次数越多对性能由一定的影响. 一般地我们不需要对这个值进行设置, 使用默认值就可以了.
3,TREEIFY_THRESHOLD: 转换红黑树的阈值, 默认值为 8. 即当数组中链表的长度达到这个值之后, 链表就是转换成红黑树, 以提高性能.
4,UNTREEIFY_THRESHOLD: 红黑树转链表的阈值, 默认值为 6.
HashMap 结构
HashMap 是以 key-value 的形式存储数组中, 将数据存在 Node 节点中, 每个 Node 节点存储了一个 key, 对应的 value 和指向下一个 Node 的指针. HashMap 的结构为数组 + 链表(红黑树), 链表为单向链表. 结构如下:
或:
HashMap 原理:
HashMap 在进行 put(key,value)操的时候, 我们看源码
- /**
- * Associates the specified value with the specified key in this map.
- * If the map previously contained a mapping for the key, the old
- * value is replaced.
- *
- * @param key key with which the specified value is to be associated
- * @param value value to be associated with the specified key
- * @return the previous value associated with <tt>key</tt>, or
- * <tt>null</tt> if there was no mapping for <tt>key</tt>.
- * (A <tt>null</tt> return can also indicate that the map
- * previously associated <tt>null</tt> with <tt>key</tt>.)
- */
- public V put(K key, V value) {
- return putVal(hash(key), key, value, false, true);
- }
- /**
- * 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;
- /**
- * 通过位与的方式来确定下标位置, 判断当前下标位置是否为空, 如果为空直接放入到该位置上
- * 不为空则通过 equals 方法来寻找当前位置上面的元素, 如果有相同的 key, 则将覆盖掉, 如果没有则将 node 放置在对应
- * 位置上面
- */
- 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))))// 已存在相同的 key 的数据, 将其覆盖
- e = p;
- else if (p instanceof TreeNode)// 当前位置是红黑树, 将 Node 节点放到红黑树中
- 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))))// 覆盖相同 key 的 node
- 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;
- }
从上面的中 HashMap 在 put 数据的是时候, 可以总结为一下一个步骤:
1, 先判断当前的数组是否为空(即有没有被初始化过), 为空的话则进行扩容操作; 每次扩容的大小为 2 的 n 次方.
2, 通过上面的步骤后数组就已经初始化好了, 然后第二步数组长度与 key 的 hash 值进行与运算, 得出该数据即将放进去的数组的位置, 这里可以分为以下两种情况:
1)当前数组的位置没有数据时, 直接将该数据放进数组中;
2)该位置有数据, 先比较 hash 值再比较 key 值, 如果两个都相等则将旧值替换掉; 否则, 从第一个节点开始一个遍历比较 hash 和 key 的值, 有则替换, 没有则放到最后.
3, 当数据成功插入后, 会进行一次判断当前的数组长度是否需要进行扩容.
当我们当 HashMap 中 put 数据的时候, 首先会对传进来的 key 进行 hash 计算:
- /**
- * Computes key.hashCode() and spreads (XORs) higher bits of hash
- * to lower. Because the table uses power-of-two masking, sets of
- * hashes that vary only in bits above the current mask will
- * always collide. (Among known examples are sets of Float keys
- * holding consecutive whole numbers in small tables.) So we
- * apply a transform that spreads the impact of higher bits
- * downward. There is a tradeoff between speed, utility, and
- * quality of bit-spreading. Because many common sets of hashes
- * are already reasonably distributed (so don't benefit from
- * spreading), and because we use trees to handle large sets of
- * collisions in bins, we just XOR some shifted bits in the
- * cheapest possible way to reduce systematic lossage, as well as
- * to incorporate impact of the highest bits that would otherwise
- * never be used in index calculations because of table bounds.
- */
- static final int hash(Object key) {
- int h;
- return (key == null) ? 0 : (h = key.hashCode()) ^ (h>>> 16);
- }
jdk1.8 开始 hash 的计算比之前的简单一些, 就是对 key 的 hashCode 的高 16 位和低 16 位进行异或运算. 这样做的目的是让 key 的 HashCode 的高位也有计算参与运算, 这样计算出来的 hash 值更加均匀, put 数据时能够减少碰撞, 提供性能.
第二步根据 key 计算出来的值获取到对应的下标, 这里并不是使用取模的方式来确定, 因为取模的方式相对于位与运算来说性能更低下. 下标的计算公式为: 当前数组的长度减一 按位与 hash 值, 得到下标, 比如当前数组长度为 16,hash 值: 54707624, 则计算如下:(注意: 位与的运算规则为, 当两个数均为 1 时结果才为 1, 否则结果为 0)
从上面的运算结果, 可以得到一个规律, 能够参与有效运算的位只有与数组长度减一的位的长度, 比如 数组长度为 16, 那么 16-1 的二进制为 1111, 那么不管 key 的 hash 值有多大, 最终参与运算的只有后 4 位, 根据位与运算规则, 运算结果的最大值为 1111, 转换成十进制后即数组的长度减一, 最小值为 0000, 十进制为 0, 即结果的范围为 0 ~ size - 1, 这个取模的结果是一致的. 又因为数组的长度总是 2 的 n 次方, 对应的二进制 为 1,11,111 ,11111 等等, 这也是为什么每次扩容时都要扩大至原来的两倍的原因. 那么, 另外一个问题又来了, 为什么一定要时 2 的 n 次方呢? 其他的值可以吗? 下面我们来做一个实验:
- public static void main(String[] args) {
- for (int i = 0; i <30; i++) {
- System.out.print((i & 15) + " ");
- }
- }
运算结果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13
当我们使用 2 的 n 次方 - 1 来运算时, 每个余数都有可能得到
- public static void main(String[] args) {
- for (int i = 0; i < 30; i++) {
- System.out.print((i & 13) + " ");
- }
- }
运算结果:
1 0 1 4 5 4 5 8 9 8 9 12 13 12 13 0 1 0 1 4 5 4 5 8 9 8 9 12 13
当我们使用 非 2 的 n 次方运算时, 看运算结果可以看到, 有些值是不可能得到的, 这样数组的某些位置就永远为空, 不仅造成空间的浪费, 同时也会大大的提高碰撞的概率. 根据位与运算规则, 很容易想到其中的原因, 首先将 13 转成二进制: 1101, 在位与运算时, 那个 0 位永远不参与运算, 如上面的结果一样, 2,3,6 等数值是没有的. 当且仅当二进制数字全为 1 的时候, 才有可能所有的位都能计算, 得到的结果才会更加均匀. 这个很容易理解, 想一下就明白了的.
第三步, 根据生成的 index 去数组寻找位置, 如果该位置为空直接将 node 放进去, 如果不为空则调用 equals 方法判断 key 值是否一致, 一致的话就替换成新值, 否则寻找下个节点, 最终在插入链表的时候会判断当前链表长度是否达到了转换成红黑树的条件(默认链表长度达到 8 时会转).
第四步, 数据 put 成功后判断当前存储的数据大小是否超过了 threshold * loadFactor 的值, 超过了就会执行 resize 方法:
- /**
- * Initializes or doubles table size. If null, allocates in
- * accord with initial capacity target held in field threshold.
- * Otherwise, because we are using power-of-two expansion, the
- * elements from each bin must either stay at same index, or move
- * with a power of two offset in the new table.
- *
- * @return the table
- */
- final Node<K,V>[] resize() {
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- if (oldCap> 0) {
- if (oldCap>= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
- oldCap>= DEFAULT_INITIAL_CAPACITY)
- newThr = oldThr <<1; // double threshold
- }
- 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);
- }
- 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) {
- 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 { // preserve order
- 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;
- }
- else {
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- if (loTail != null) {
- loTail.next = null;
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- hiTail.next = null;
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- return newTab;
- }
进行扩容的时候将所有的 node 节点进行 hash 计算 e.hash & (newCap - 1), 这样的结果不是在原来的就是在 当前位置加原来 threshold 长度的位置. 至此整个 put 操作结束.
get(Object key)的原理:
弄懂了 put 操作之后, 其实 get 就很容易理解了, 首先根据传入 key 找到 index, 然后再对应的位置上获取就行了.
最后, 我看了 HashMap 源码之后, 自己也手写了一个 HashMap, 不同之处在于我没有用到红黑树, 而是使用二叉树代替, 经测试插入 1 千万条 uuid 所需时间都差粗多, 都是在二十几秒左右. 关于二叉树与红黑树的区别可以自行百度, 红黑树最主要解决的问题是在极端的情况下二叉树只有一条路径, 时间复杂度位 O(N), 红黑树为了避免这种情况, 每次都会自动调节树的深度, 将最坏的情况的时间复杂度降低到 O(logN).
因为完全是手写的, 所以可能代码的可读性不是很好, 但是基本的功能都能够实现了. 如果大家有兴趣的话, 可以下载过来看一下, 也欢迎大家指出错误或提意见. 项目地址: https://github.com/rainple1860/MyCollection
转载 https://www.noblogs.cn/rainple/blog/17853.html
来源: http://www.bubuko.com/infodetail-3032066.html