飞利浦·斯塔克|重温数据结构经典:HashMap原理

飞利浦·斯塔克|重温数据结构经典:HashMap原理

文章图片


昨天难得没那么多扯淡的会议 , 有时间好好重温一下数据结构的知识 , 在此跟大家一起重温一下数据结构经典:hashCode及HashMap原理
一、HashCode为什么使用31作为乘数1、选择数字31是因为它是一个奇质数 , 如果选择一个偶数会在乘法运算中产生溢出 , 导致数值信息丢失 , 因为乘二相当于移位运算 。 选择质数的优势并不是特别的明显 , 但这是一个传统 。
2、数字31有一个很好的特性 , 即乘法运算可以被移位和减法运算取代 , 来获取更好的性能:31 * i == (i << 5) - i , 现代的 Java 虚拟机可以自动地完成这个优化 。
二、数组与链表的特点数组的特点是:寻址容易 , 插入和删除困难
链表的特点是:寻址困难 , 插入和删除容易
三、HashMap原理

  • 允许null健及null值 , null健 , 值为0
  • HashMap 不保证键值对的顺序 , 操作时 , 键值对的顺序会发生变化
  • HashMap是非线程安全类 , 在多线程环境下会发生问题
  • HashMap是JDK 1.2时推出的 , 底层基于散列算法实现
  • 在JDK 1.8中涉及比较多:1、散列表实现、2、扰动函数、3、初始化容量、4、负载因子、5、扩容元素拆分、6、链表树化、7、红黑树、8、插入、9、查找、10、删除、11、遍历、12、分段锁等
(1) 扰动函数static final int hash(Object key) {
   int h;
   return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);


  • 扰动函数就是为了增加随机性 , 让数据元素更加均衡地散列 , 减少碰撞 。
(2) 负载因子static final float DEFAULT_LOAD_FACTOR = 0.75f;
负载因子 , 可以理解成一辆车可承重重量超过某个阀值时 , 把货放到新的车上 。 在 HashMap 中 , 负载因子决定了数据量多少了以后进行扩容
0.75 是一个默认构造值 , 在创建 HashMap 也可以调整 , 如何希望用更多的空间换取时间 , 可以把负载因子调得更小一些 , 减少碰撞 。
(3) 扩容元素拆分扩容最直接的问题 , 就是需要把元素拆分到新的数组中 , 在JDK1.7中 , 会重新计算哈希值 , 但在JDK1.8后 , 进行了优化 ,
  1. 扩容时计算出新的newCap、newThr , 这是两个单词的缩写 , 一个是Capacity, 另一个是阀Threshold
  2. newCap用于创新的数组桶 new Node[newCap
    ;
  3. 随着扩容后 , 原来那些因为哈希碰撞 , 存放成链表和红黑树的元素 , 都需要进行拆分存放到新的位置中
(4) 数据迁移(5) 数据插入
  1. 首先进行哈希值的扰动 , 获取一个新的哈希值 。 (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  2. 判断tab是否为空或者长度为0 , 如果是则进行扩容操作 。
  3. if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length;
  4. 根据哈希值计算下标 , 如果对应小标正好没有存放数据 , 则直接插入即可否则需要覆盖 。 tab[i = (n - 1) & hash
    )
  5. 判断tab[i
    是否为树节点 , 否则向链表中插入数据 , 否则向树中插入节点 。
  6. 如果链表中插入节点的时候 , 链表长度大于等于8 , 则需要把链表转换为红黑树 。 treeifyBin(tab hash);
  7. 最后所有元素处理完成后 , 判断是否超过阈值;threshold , 超过则扩容 。
  8. treeifyBin是一个链表转树的方法 , 但不是所有的链表长度为8后都会转成树 , 还需要判断存放key值的数组桶长度是否小于64 MIN_TREEIFY_CAPACITY 。 如果小于则需要扩容 , 扩容后链表上的数据会被拆分散列的相应的桶节点上 , 也就把链表长度缩短了 。